DESCRIPTIONAL COMPLEXITY OF CLASSICAL AND QUANTUM UNARY AUTOMATA

In 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.