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.
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.
We design Latvian quantum finite state automata (LQFAs for short) recognizing unary regular languages with isolated cut point 1 2 .From an architectural point of view, we combine two LQFAs recognizing with isolated cut point, respectively, the finite part and the ultimately periodic part of any given unary regular language L. In both modules, we use a component addressed in the literature and here suitably adapted to the unary case, to discriminate strings on the basis of their length.The number of basis states and the isolation around the cut point of the resulting LQFA for L exponentially depends on the size of the minimal deterministic finite state automaton for L.
We study quantum finite automata with control language (qfcs), a theoretical model for finite memory hybrid systems coupling a classical computational framework with a quantum component. We constructively show how to simulate measure-once, measure-many, reversible, and Latvian qfas by qfcs, emphasizing the size cost of such simulations. Next, we prove the decidability of testing the periodicity of the stochastic event induced by a given qfc. Thanks to our qfa simulations, we can extend such a decidability result to measure-once, measure-many, reversible, and Latvian qfas as well. Finally, we focus on comparing the size efficiency of quantum and classical finite state automata on unary regular language recognition. We show that unary regular languages can be recognized by isolated cut point qfcs for which the size is generally quadratically smaller than the size of equivalent dfas.
The computational model of Quantum Finite Automata has been introduced by multiple authors (e.g. [38, 44]) with some variations in definition. The objective of this thesis is to understand what class of languages can be recognized by these different variations, and how many states are required. We begin by showing that we can use algebraic automata theory to characterize the language recognition power of QFAs. Algebraic automata theory associates to each language a canonical syntactic monoid, and the algebraic structure of this monoid becomes a meaningful parameter in describing language classes. We show that the class of languages recognized by Latvian QFAs [3] corresponds exactly to boolean combinations of languages recognized by Brodsky and Pippenger's QFA model [20], which correspond exactly to those languages whose syntactic monoid is in the class BG. Known results give us a decision procedure for testing membership in this language class. We also use algebraic automata theory to give nearly tight upper and lower bounds on the class of languages recognized by Brodsky and Pippenger's QFAs. We then extend a number of lower bound techniques known for Kondacs and Watrous' 1-way QFA model to Nayak's Generalized QFA. Both of these models are related in that they are permitted to halt before reading the entire input, allowing them to recognize certain languages whose syntactic monoid lies outside of BG. Finally, we investigate the question of QFA succinctness. It is known that QFAs can recognize some languages using exponentially fewer states compared to deterministic finite automata. We extend results from [16] to show that the word problem over abelian groups has this property. We also give example of interesting noncommutative languages with this property.
In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.
We show that there are quantum devices that accept all regular languages and that are exponentially more concise than deterministic finite automata (DFA). For this purpose, we introduce a new computing model of {\it one-way quantum finite automata} (1QFA), namely, {\it one-way quantum finite automata together with classical states} (1QFAC), which extends naturally both measure-only 1QFA and DFA and whose state complexity is upper-bounded by both. The original contributions of the paper are the following. First, we show that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. Second, we prove that 1QFAC are at most exponentially more concise than DFA. Third, we show that the previous bound is tight for families of regular languages that are not recognized by measure-once (RMO), measure-many (RMM) and multi-letter 1QFA. % More concretely we exhibit regular languages L0(m) for m prime such that: (i) L0(m) cannot be recognized by measure-once, measure-many and multi-letter 1QFA; (ii) the minimal DFA that accepts L0(m) has O(m) states; (iii) there is a 1QFAC with constant classical states and O(log(m)) quantum basis that accepts L0(m). Fourth, we give a polynomial-time algorithm for determining whether any two 1QFAC are equivalent. Finally, we show that state minimization of 1QFAC is decidable within EXPSPACE. We conclude the paper by posing some open problems.
One-way quantum finite automata together with classical states (1QFAC) proposed in [Journal of Computer and System Sciences 81(2) (2015) 359--375] is a new one-way quantum finite automata (1QFA) model that integrates quantum finite automata (QFA) and deterministic finite automata (DFA). This model uses classical states to control the evolution and measurement of quantum states. As a quantum-classical hybrid model, 1QFAC recognize all regular languages. It was shown that the state complexity of 1QFAC for some languages is essentially superior to that of DFA and other 1QFA. In this paper, our goal is to clarify state complexity problems for 1QFAC. We obtain the following results: (1) We optimize the bound given by Qiu et al. that characterizes the relationship between quantum basis state number and classical state number of 1QFAC as well as the state number of its corresponding minimal DFA for recognizing any given regular language. (2) We give an upper bound showing that how many classical states are needed if the quantum basis states of 1QFAC are reduced without changing its recognition ability. (3) We give a lower bound of the classical state number of 1QFAC for recognizing any given regular language, and the lower bound is exact if the given language is finite. (4) We show that 1QFAC are exponentially more succinct than DFA and probabilistic finite automata (PFA) for recognizing some regular languages that can not be recognized by measure-once 1QFA (MO-1QFA), measure-many 1QFA (MM-1QFA) or multi-letter 1QFA. (5) We reveal essential relationships between 1QFAC, MO-1QFA and multi-letter 1QFA, and induce a result regarding a quantitative relationship between the state number of multi-letter 1QFA and DFA.