Search results for " Automata"
showing 10 items of 436 documents
Hopcroft’s Algorithm and Cyclic Automata
2008
Minimization of deterministic finite automata is a largely studied problem of the Theory of Automata and Formal Languages. It consists in finding the unique (up to isomorphism) minimal deterministic automaton recognizing a set of words. The first approaches to this topic can be traced back to the 1950’s with the works of Huffman and Moore (cf. [12,15]). Over the years several methods to solve this problem have been proposed but the most efficient algorithm in the worst case was given by Hopcroft in [11]. Such an algorithm computes in O(n log n) the minimal automaton equivalent to a given automaton with n states. The Hopcroft’s algorithm has been widely studied, described and implemented by …
Hopcroft's algorithm and tree-like automata
2011
Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard words, have running time with the same asymptotic growth rate. In particular, we provide a lower and upper bound for the running time of the algorithm expressed in terms of combinatorial properties of the trees…
Postselection Finite Quantum Automata
2010
Postselection for quantum computing devices was introduced by S. Aaronson[2] as an excitingly efficient tool to solve long standing problems of computational complexity related to classical computing devices only. This was a surprising usage of notions of quantum computation. We introduce Aaronson's type postselection in quantum finite automata. There are several nonequivalent definitions of quantumfinite automata. Nearly all of them recognize only regular languages but not all regular languages. We prove that PALINDROMES can be recognized by MM-quantum finite automata with postselection. At first we prove by a direct construction that the complement of this language can be recognized this …
On the size of transducers for bidirectional decoding of prefix codes
2012
In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [ IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this method is defined. It is proved also that this transducer is minimal. Here we consider the number of states of such a transducer, related to some features of the considered prefix code X . We find some bounds of such a number of states in relation wi…
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 …
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.