On a class of languages recognizable by probabilistic reversible decide-and-halt automata |
| |
Authors: | Marats Golovkins Maksim Kravtsev Vasilijs Kravcevs |
| |
Affiliation: | Institute of Mathematics and Computer Science, University of Latvia, Rai?a bulv. 29, Riga, Latvia |
| |
Abstract: | We 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. |
| |
Keywords: | Probabilistic automata Quantum automata |
本文献已被 ScienceDirect 等数据库收录! |