A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Alternating, private alternating, and quantum alternating realtime automata




TekijätDemirci G, Hirvensalo M, Reinhardt K, Say ACC, Yakaryilmaz A

KustantajaLOGICAL METHODS COMPUTER SCIENCE E V

Julkaisuvuosi2019

JournalLogical Methods in Computer Science

Tietokannassa oleva lehden nimiLOGICAL METHODS IN COMPUTER SCIENCE

Lehden akronyymiLOG METH COMPUT SCI

Artikkelin numero22

Vuosikerta15

Numero3

Sivujen määrä21

ISSN1860-5974

eISSN1860-5974

DOIhttps://doi.org/10.23638/LMCS-15(3:22)2019

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/42728622


Tiivistelmä
We present new results on realtime alternating, private alternating, and quantum alternating automaton models. Firstly, we show that the emptiness problem for alternating one-counter automata on unary alphabets is undecidable. Then, we present two equivalent definitions of realtime private alternating finite automata (PAFAs). We show that the emptiness problem is undecidable for PAFAs. Furthermore, PAFAs can recognize some nonregular unary languages, including the unary squares language, which seems to be difficult even for some classical counter automata with two-way input. Regarding quantum finite automata (QFAs), we show that the emptiness problem is undecidable both for universal QFAs on general alphabets, and for alternating QFAs with two alternations on unary alphabets. On the other hand, the same problem is decidable for nondeterministic QFAs on general alphabets. We also show that the unary squares language is recognized by alternating QFAs with two alternations.

Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 22:44