Article ID Journal Published Year Pages File Type
434238 Theoretical Computer Science 2014 14 Pages PDF
Abstract

•We analyze the descriptional power of Quantum Finite Automata with control language.•We show an exponential size cost conversion from QFAs with control language to DFAs.•We simulate Latvian QFAs by QFAs with control languages.•We obtain size lower bounds for several models of QFAs.

We compare the descriptional power of quantum finite automata with control language (qfcs) and deterministic finite automata (dfas). By suitably adapting Rabin's technique, we show how to convert any given qfc to an equivalent dfa, incurring in an at most exponential size increase. This enables us to state a lower bound on the size of qfcs, which is logarithmic in the size of equivalent minimal dfas. In turn, this result yields analogous size lower bounds for several models of quantum finite automata in the literature.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,