Search results for "AUTOMATA"
showing 10 items of 453 documents
DEFECT THEOREMS FOR TREES
2000
We generalize different notions of a rank of a set of words to sets of trees. We prove that almost all of those ranks can be used to formulate a defect theorem. However, as we show, the prefix rank forms an exception.
Quantum Finite Multitape Automata
1999
Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This …
Probabilistic Reversible Automata and Quantum Automata
2002
To study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. We also propose a classification of reversible finite 1-way automata.
Implications of quantum automata for contextuality
2014
We construct zero error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded error probabilistic finite automata (PFAs). Here is a summary of our results: There is a promise problem solvable by an exact two way QFA in exponential expected time but not by any bounded error sublogarithmic space probabilistic Turing machine (PTM). There is a promise problem solvable by an exact two way QFA in quadratic expected time but not by any bounded error o(loglogn) space PTMs in polynomial expected time. The same problem can be solvable by a one way Las Vegas (or exact two way) QFA with quantum head in linear (expected) time. There is a promise problem solvable by a Las …
Marked systems and circular splicing
2007
Splicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. In this paper we introduce a special class of finite circular splicing systems named marked systems. We prove that a marked system S generates a regular circular language if and only if S satisfies a special (decidable) property. As a consequence, we show that we can decide whether a regular circular language is generated by a marked system and we characterize the structure of these regular circular languages.
On a Non-periodic Shrinking Generator
2011
We present a new non-periodic random number generator based on the shrinking generator. The A-sequence is still generated using a LFSR, but the S-sequence is replaced by a finitely generated bi-ideal - a non-periodic sequence. The resulting pseudo-random sequence performs well in statistical tests. We show a method for the construction of an infinite number of finitely generated bi-ideals from a given A-sequence, such that the resulting sequence of the shrinking generator is nonperiodic. Further we prove the existence of what we call universal finitely generated bi-ideals that produce non-periodic words when used as the S-sequence of a shrinking generator for all non-trivial periodic A-sequ…
Quantum Finite State Transducers
2001
We introduce quantum finite state transducers (qfst), and study the class of relations which they compute. It turns out that they share many features with probabilistic finite state transducers, especially regarding undecidability of emptiness (at least for low probability of success). However, like their 'little brothers', the quantum finite automata, the power of qfst is incomparable to that of their probabilistic counterpart. This we show by discussing a number of characteristic examples.
Improved constructions of quantum automata
2008
We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use \frac{4}{\epsilon} \log 2p + O(1) states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of \log p than the previously known construction of Ambainis and Freivalds (quant-ph/9802062). Similarly to Ambainis and Freivalds, our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction.
Improved constructions of mixed state quantum automata
2009
Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A. Ambainis and R. Freivalds that quantum finite automata with pure states can have an exponentially smaller number of states than deterministic finite automata recognizing the same language. There was an unpublished ''folk theorem'' proving that quantum finite automata with mixed states are no more super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We prove that there is an infinite sequence of distinct int…
Circular sturmian words and Hopcroft’s algorithm
2009
AbstractIn order to analyze some extremal cases of Hopcroft’s algorithm, we investigate the relationships between the combinatorial properties of a circular sturmian word (x) and the run of the algorithm on the cyclic automaton Ax associated to (x). The combinatorial properties of words taken into account make use of sturmian morphisms and give rise to the notion of reduction tree of a circular sturmian word. We prove that the shape of this tree uniquely characterizes the word itself. The properties of the run of Hopcroft’s algorithm are expressed in terms of the derivation tree of the automaton, which is a tree that represents the refinement process that, in the execution of Hopcroft’s alg…