CS 789 THEORY SEMINAR [home]

Speaker:  Rusins  Freivalds,     
Affiliation: University of Latvia, Computer Science
Date: Monday, January 21, 2002
Title: Quantum Finite Automata

Abstract: 

There are several definitions of Quantum Finite Automata (QFA). The "most standard" one was introduced by A.Kondacs and J.Watrous. The languages recognizable by QFA are regular but not all regular languages are recognizable by QFA. A.Ambainis and R.Freivalds proved in 1998 that there are languages recognizable by QFA, the size of which equals logarithm of the size needed by DFA recognizing the same language.  A.Nayak proved that for some other languages the size of DFA equals logarithm of the size needed by QFA recognizing the same language. Since then many results are proved in the University of Latvia describing the properties of regular languages causing advantages and disadvantages of the size of QFA.