6533b824fe1ef96bd1280cc6
RESEARCH PRODUCT
On a class of languages recognizable by probabilistic reversible decide-and-halt automata
Marats GolovkinsVasilijs KravcevsMaksim Kravtsevsubject
Discrete mathematicsClass (set theory)Quantum automataNested wordGeneral Computer ScienceProbabilistic logicAutomatonTheoretical Computer ScienceRegular languageDeterministic automatonProbabilistic automatonQuantum finite automataProbabilistic automataComputer Science::Formal Languages and Automata TheoryMathematicsComputer Science(all)description
AbstractWe analyze the properties of probabilistic reversible decide-and-halt automata (DH-PRA) and show that there is a strong relationship between DH-PRA and 1-way quantum automata. We show that a general class of regular languages is not recognizable by DH-PRA by proving that two “forbidden” constructions in minimal deterministic automata correspond to languages not recognizable by DH-PRA. The shown class is identical to a class known to be not recognizable by 1-way quantum automata. We also prove that the class of languages recognizable by DH-PRA is not closed under union and other non-trivial Boolean operations.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2009-05-01 | Theoretical Computer Science |