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.5-way and 2-way quantum finite state automata (1.5QFA and 2QFA) and 2-way 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 non-erasing 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 1-way quantum finite state automata (1QFA) is equal to the class of regular languages.

Súbory diplomovej práce:

diplo.pdf