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)