Meno:  Martin


Priezvisko:  Macko


Názov:  On Closure Properties of Quantum Finite Automata


Vedúci:  prof. Dr. Jozef Gruska, DrSc.


Rok:  2006


Blok:  MMI


Kµúčové slová:  Quantum computation, Quantum finite automata, 1.5QFA, 2QFA, 2QCFA.


Abstrakt:  We prove several new closure properties of the classes of languages recognized
by 1.5way and 2way quantum finite state automata (1.5QFA and 2QFA) and 2way
finite automata with quantum and classical states (2QCFA). We show that none
of these classes of languages is closed under homomorphism, the classes of
languages recognized by 1.5QFA and by simple 2QFA are closed under inverse
nonerasing homomorphism and the class of languages recognized by simple
1.5QFA is closed under general inverse homomorphism. We also show that the
homomorphic closures of the classes of languages recognized by 1.5QFA, 2QFA
and 2QCFA are equal to the class of recursively enumerable languages and the
homomorphic closure of the class of languages recognized by 1way quantum
finite state automata (1QFA) is equal to the class of regular languages.

