6533b862fe1ef96bd12c6efe
RESEARCH PRODUCT
Multi-letter reversible and quantum finite automata
Juris SmotrovsAleksandrs BelovsAnsis Rosmanissubject
AlgebraDiscrete mathematicsDeterministic finite automatonRegular languageDeterministic automatonProbabilistic automatonContext-free languageComputer Science::Programming LanguagesQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryMathematicsdescription
The regular language (a+b)*a (the words in alphabet {a, b} having a as the last letter) is at the moment a classical example of a language not recognizable by a one-way quantum finite automaton (QFA). Up to now, there have been introduced many different models of QFAs, with increasing capabilities, but none of them can cope with this language. We introduce a new, quite simple modification of the QFA model (actually even a deterministic reversible FA model) which is able to recognize this language. We also completely characterise the set of languages recognizable by the new model FAs, by finding a "forbidden construction" whose presence or absence in the minimal deterministic (not necessarily reversible) finite automaton of the language decides the recognizability. Thus, the new model still cannot recognize the whole set of regular languages, however it enhances the understanding of what can be done in a finite-state real-time quantum process.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2007-09-12 |