Name
Abstract | ||
|---|---|---|
We present some new results on realtime classical and quantum alternating models. Firstly, we show that the emptiness problem for alternating one-counter automata on unary alphabets is undecidable. Then, we define realtime private alternating finite automata (PAFAs) and show that they can recognize some non-regular unary languages, and the emptiness problem is undecidable for them. Moreover, PAFAs augmented with a counter can recognize the unary squares language, which seems to be difficult even for some classical counter automata with two-way input. For quantum finite automata (QFAs), we show that the emptiness problem for universal QFAs on general alphabets and alternating QFAs with two alternations on unary alphabets are undecidable. 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 | Venue | DocType |
|---|---|---|
2014 | NCMA | Journal |
Volume | Citations | PageRank |
abs/1407.0334 | 3 | 0.42 |
References | Authors | |
7 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| H. Gökalp Demirci | 1 | 8 | 3.31 |
| Mika Hirvensalo | 2 | 163 | 21.19 |
| Klaus Reinhardt | 3 | 3 | 1.09 |
| A. C. Cem Say | 4 | 193 | 26.13 |
| Abuzer Yakaryilmaz | 5 | 168 | 25.31 |