1,720,979 research outputs found
Behaviours of Unary Quantum Automata
No full textWe study the stochastic events induced by MM-qfa's working on unary alphabets. We give two algorithms for unary MM-qfa's: the first computes the dimension of the ergodic and transient components of the non halting subspace, while the second tests whether the induced event is d-periodic. These algorithms run in polynomial time whenever the MM-qfa given in input has complex amplitudes with rational components. We also characterize the recognition power of unary MM-qfa's, by proving that any unary regular language can be accepted by a MM-qfa with constant cut point and isolation. Yet, the amount of states of the resulting MM-qfa is linear in the size of the corresponding minimal dfa. We also single out families of unary regular languages for which the size of the accepting MM-qfa's can be exponentially decreased
DESCRIPTIONAL COMPLEXITY OF CLASSICAL AND QUANTUM UNARY AUTOMATA
Full text linkIn this thesis, we study some problems on classical and quantum one-way finite state automata working on a unary input alphabet. The central issue of this work is the descriptional complexity of different models of automata on families of languages defined through periodicity conditions on the length of the input. However, along the way many other issues on automata, such as computational power and decidability, are taken into consideration.
The work is organised into two parts. In the first one, we focus on three types of classical one-way finite automata, namely deterministic (DFAs), nondeterministic (NFAs) and probabilistic (PFAs), which differ from each other for the way evolution is defined. We present a normal form for unary PFAs, which extends the Chrobak normal form for NFAs and guarantees minimality on periodic languages. We then use this probabilistic normal form to obtain descriptional complexity results: we analyze several families of unary languages, characterized by periodicity conditions. We show that, for some of those families, all classical models require the same number of states while, for some other families, PFAs can be smaller than NFAs (sometimes reaching the theoretical lower bound), which in turn can be smaller than DFAs.
In the second part of this thesis, we focus on the quantum paradigm, considering three variants of one-way quantum automata (QFAs): measure-once QFAs (MO-QFAs), measure-many QFAs (MM-QFAs), and the hybrid model of QFA with control language (QFC). The computational power of MM-QFAs, unlike the one of MO-QFAs and QFCs, is still not fully characterised. In this thesis, we provide an explicit construction for MM-QFAs to recognize any unary regular language.
We then focus on the descriptional complexity of QFAs: first, we present families of unary languages for which MM-QFAs require an exponentially smaller number of states with respect to their deterministic equivalent. Then, we prove that this is very close to the (asymptotically) biggest size gap we can achieve between the two models, by showing a more general conversion lower bound on the number of states required by a DFA to simulate a QFC working on an alphabet of arbitrary size. This bound carries over to the other two quantum models, since both MO-QFAs and MM-QFAs can be simulated by QFCs without increasing the number of quantum states. Finally, we discuss periodicity problems on the behavior of MM-QFAs, presenting polynomial algorithmic solutions
On the Power of One-Way Automata with Quantum and Classical States
No full textWe consider the model of one-way automata with quantum and classical states (QCFAs) introduced in [28]. We show, by a direct approach, that QCFAs with isolated cut-point accept regular languages only, thus characterizing their computational power. Concerning descriptional power, we quickly overview a size lower bound for QCFAs accepting regular languages, and address its optimality. Then, we explicitly build QCFAs accepting the word quotients and inverse homomorphic images of languages accepted by given QCFAs with isolated cut-point, maintaining the same cut-point, isolation, and only polynomially increasing the size
Quantum finite automata : advances on Bertoni's ideas
No full textWe first outline main steps and achievements along Bertoni's research path in quantum finite automata theory - from the very basic definitions of the models of quantum finite automata throughout the investigation of their computational and descriptional power. Next, we choose to focus on Bertoni's studies on quantum finite automata descriptional complexity. In particular, we expand on a statistical framework for the synthesis of succinct quantum finite automata, discussing its adaptation to the case of multiperiodic events and languages. We then improve such a framework to obtain even more succinct quantum finite automata for some multiperiodic languages. Finally, we introduce some promise problems for multiperiodic inputs, showing that even on this class of problems the descriptional power of quantum finite automata greatly outperforms that of equivalent classical finite automata
Size lower bounds for quantum automata
No full textWe 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
Normal forms for unary probabilistic automata
No full textWe investigate the possibility of extending Chrobak normal form to the probabilistic case.
While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the probabilistic case of Chrobak normal form, obtained by replacing nondeterministic choices with probabilistic choices.
We then propose a different kind of normal form, the cyclic normal form, which does not suffer from the same problem: we prove that each unary probabilistic automaton can be simulated by a probabilistic automaton in cyclic normal form, with at most the same number of ergodic states. In the nondeterminstic case there are trivial simulations between Chrobak normal form and cyclic normal form, preserving the total number of the states in the automata and in their cycles
Normal forms for unary probabilistic automata
Full text linkWe investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the probabilistic case of Chrobak normal form, obtained by replacing nondeterministic choices with probabilistic choices. We then propose a different kind of normal form, namely, cyclic normal form, which does not suffer from the same problem: we prove that each unary probabilistic automaton can be simulated by a probabilistic automaton in cyclic normal form, with at most the same number of ergodic states. In the nondeterministic case there are trivial simulations between Chrobak normal form and cyclic normal form, preserving the total number of states in the automata and in their cycles
On the size of unary probabilistic and nondeterministic automata
No full textWe investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pfa accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa's which, in turn, are smaller than deterministic automata
Regularity of languages defined by formal series with isolated cut point
No full textA formal power series φ with a real cut point λ defines the language L_{φ,λ} = {ω ∈ Σ∗ | |φ(ω) > λ};
λ is called isolated if inf_ω |φ(ω) − λ| > 0. In this paper we give conditions for guaranteeing the regularity of L_{φ,λ}, with λ isolated, for two classes of formal series: rational series and Hadamard quotients of rational series. Finally, we provide an explicit representation of the behavior of a subclass of two-way weighted automata in terms of Hadamard quotient of rational series
- …
