Paper Info
Title
Alternating, private alternating, and quantum alternating realtime automata
Abstract
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.
Year
DOI
Venue
2019
10.23638/LMCS-15(3:22)2019
LOGICAL METHODS IN COMPUTER SCIENCE
Keywords
Field
DocType
alternation,private alternation,interactive proof systems,quantum computing,realtime computation,counter automata,emptiness problem,unary languages
Quantum finite automata,Quantum,Discrete mathematics,Combinatorics,Unary operation,Nondeterministic algorithm,Automaton,Decidability,Finite-state machine,Mathematics,Undecidable problem
Journal
Volume
Issue
ISSN
15
3
1860-5974
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
H. Gökalp Demirci183.31
Mika Hirvensalo216321.19
Klaus Reinhardt331.09
A. C. Cem Say419326.13
Abuzer Yakaryilmaz516825.31