International Journal of Foundations of Computer Science
Latvian Quantum Finite State Automata for Unary Languages
Carlo Mereghetti, Beatrice Palano, Priscilla Raucci
Abstract
We design Latvian quantum finite state automata (lqfas) recognizing unary regular languages with isolated cut point [Formula: see text]. From an architectural viewpoint, we suitably combine two lqfas recognizing with isolated cut point, respectively, the finite part and the ultimately periodic part any given unary regular language [Formula: see text] consists of. In particular, both these lqfas incorporate a sub-module discriminating strings on the basis of their length. Both the number of basis states and the isolation around the cut point of the resulting lqfa for [Formula: see text] exponentially depend on the size of the minimal deterministic finite state automaton for [Formula: see text]. Moreover, the recognition of [Formula: see text] tends to becoming deterministic as the number of the basis states employed in the length-discriminating sub-module grows.