| 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.
|
|---|