1. Latvian Quantum Finite State Automata for Unary Languages.
- Author
-
Mereghetti, Carlo, Palano, Beatrice, and Raucci, Priscilla
- Subjects
- *
QUANTUM states , *FINITE state machines , *ROBOTS , *LANGUAGE & languages - Abstract
We design
Latvian quantum finite state automata (LQFAs) recognizing unary regular languages with isolated cut point 1 2. 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 L 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 LQFAs for L exponentially depend on the size of the minimal deterministic finite state automaton for L. Moreover, the recognition of L tends to becoming deterministic as the number of the basis states employed in the length-discriminating sub-module grows. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF