一句话：证明了实时交替、私有交替与量子交替自动机的空问题不可判定性及若干非正则识别能力。
本文研究实时交替自动机、私有交替有限自动机（PAFA）与量子交替自动机。首先证明一元字母表上交替单计数器自动机的空问题不可判定；随后给出 PAFA 的两个等价定义，并证明其空问题不可判定，且 PAFA 能识别某些一元非正则语言（包括一元平方语言），即使对某些带双向输入的经典计数器自动机也较困难。对于量子有限自动机（QFA），证明一般字母表上的 universal QFA 和一元字母表上具有两次交替的交替 QFA 的空问题不可判定，而一般字母表上非确定性 QFA 的空问题可判定。最后证明具有两次交替的交替 QFA 可识别一元平方语言。
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.
@article{paperbot762,
title = {Alternating, private alternating, and quantum alternating realtime automata},
author = {Gökalp Demirci and Mika Hirvensalo and Klaus Reinhardt and A. C. Cem Say and Abuzer Yakaryılmaz},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 3},
year = {2019},
doi = {10.23638/lmcs-15(3:22)2019}
}