Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages

Autor:	Maksim Kravtsev, Vasilijs Kravcevs, Marats Golovkins
Rok vydání:	2011
Předmět:	Discrete mathematics Nested word Idempotence Quantum finite automata Automata theory Computer Science::Computational Complexity Algebraic number ω-automaton Characterization (mathematics) Computer Science::Formal Languages and Automata Theory Mathematics Automaton
Zdroj:	Mathematical Foundations of Computer Science 2011 ISBN: 9783642229923 MFCS
DOI:	10.1007/978-3-642-22993-0_33
Popis:	We study the recognition of R-trivial idempotent (R1) languages by various models of "decide-and-halt" quantum finite automata (QFA) and probabilistic reversible automata (DH-PRA). We introduce bistochastic QFA (MM-BQFA), a model which generalizes both Nayak's enhanced QFA and DH-PRA. We apply tools from algebraic automata theory and systems of linear inequalities to give a complete characterization of R1 languages recognized by all these models. We also find that "forbidden constructions" known so far do not include all of the languages that cannot be recognized by measure-many QFA.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::8d964c903fcdbbebcc12a45eb766f6bd https://doi.org/10.1007/978-3-642-22993-0_33 Zobrazit plný text záznamu