Gökalp Demirci ; Mika Hirvensalo ; Klaus Reinhardt ; A. C. Cem Say ; Abuzer Yakaryılmaz - Alternating, private alternating, and quantum alternating realtime automata

lmcs:4664 - Logical Methods in Computer Science, August 28, 2019, Volume 15, Issue 3 - https://doi.org/10.23638/LMCS-15(3:22)2019
Alternating, private alternating, and quantum alternating realtime automataArticle

Authors: Gökalp Demirci ; Mika Hirvensalo ; Klaus Reinhardt ; A. C. Cem Say ORCID; Abuzer Yakaryılmaz

    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.


    Volume: Volume 15, Issue 3
    Published on: August 28, 2019
    Accepted on: June 4, 2019
    Submitted on: July 4, 2018
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,Quantum Physics

    Consultation statistics

    This page has been seen 1049 times.
    This article's PDF has been downloaded 319 times.