# Invited Speakers

- Andris Ambainis (University of Riga, Latvia)

**On Quantum Automata.**Quantum finite automata (QFAs) are quantum counterparts of the usual finite automata. 1-way QFAs recognize the same languages as conventional finite automata but can be exponentially more space-efficient. In this talk, we describe the main results about quantum finite automata and some possible areas for future work. In particular, we will discuss: (i) the languages for which QFAs can be smaller than conventional finite automata, (ii) the models of QFAs that are between 1-way and 2-way QFAs, and (iii) the connections between QFAs and quantum Markov chains.

- Viliam Geffert (University of Kosice, Slovak Rep.)

**An Alternating Hierarchy for Finite Automata.**Let $2\Sigma_k$ and $2\Pi_k$ denote, for k > 0 the classes of language families that can be recognized by two-way alternating finite automata (2AFAs) with a polynomial number of states making at most k - 1 alternations between existential and universal states, starting in an existential or universal state, respectively. We show that this hierarchy is infinite: for each k > 1, both $2\Sigma_{k-1}$ and $2\Pi_{k-1}$ are proper subsets of $2\Sigma_k$ and of $2\Pi_k$. The conversion of a one-way $2\Sigma_k$- or $\Pi_k$-alternating automaton with n states into a two-way automaton with a smaller number of alternations requires, in the worst case, at least $2^{n/4-k/4-3/2} - 1$ states. The same exponential blow-up is required for converting a $\Sigma_k$-alternating 2AFAs into a $\Pi_k$-alternating 2AFAs or vice versa, that is, the state complexity classes $2\Sigma_k$ and $2\Pi_k$ are incomparable. In the case of $2\Sigma_k$-alternating 2AFAs, the exponential gap applies also for intersection, while for $\Pi_k$-alternating 2AFAs for union. The same hierarchy results are established for one-way alternating finite automata. This solves several open problems raised by in the literature.

# Program Committee

- Christian Choffrut (Université Paris Diderot, France)
- Erzsebet Csuhaj-Varju (Academy of Sciences, Hungary)
- Mark Daley (University of Western Ontario, Canada)
- Jerome Durand-Lose (Université d'Orléans, France)
- Rusins Freivalds (University of Riga, Latvia)
- Rudolf Freund (Technische Universitaet Wien, Austria) (co-chair)
- Mika Hirvensalo (University of Turku, Finland)
- Markus Holzer (Universitaet Giessen, Germany) (co-chair)
- Andreas Malcher (Universitaet Giessen, Germany)
- Carlo Mereghetti (University of Milano, Italy) (co-chair)
- Nelma Moreira (University of Porto, Protugal)
- Hidenosuke Nishio (University of Kyoto, Japan)
- Marion Oswald (Technische Universitaet Wien, Austria)
- Friedrich Otto (Universitaet Kassel, Germany) (co-chair)
- Beatrice Palano (University of Milano, Italy) (co-chair)
- Giovanni Pighizzini (University of Milano, Italy)
- Kai Salomaa (Queen's University, Canada)
- Bianca Truthe (Universitaet Magdeburg, Germany)