Alternating, private alternating, and quantum alternating realtime automata
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 alternati...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2019-08-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/4664/pdf |
| _version_ | 1797268555642699776 |
|---|---|
| author | Gökalp Demirci Mika Hirvensalo Klaus Reinhardt A. C. Cem Say Abuzer Yakaryılmaz |
| author_facet | Gökalp Demirci Mika Hirvensalo Klaus Reinhardt A. C. Cem Say Abuzer Yakaryılmaz |
| author_sort | Gökalp Demirci |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:34:21Z |
| format | Article |
| id | doaj.art-4b597330cf854fc4b935070b3d33658f |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:34:21Z |
| publishDate | 2019-08-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-4b597330cf854fc4b935070b3d33658f2024-03-08T10:28:03ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742019-08-01Volume 15, Issue 310.23638/LMCS-15(3:22)20194664Alternating, private alternating, and quantum alternating realtime automataGökalp DemirciMika HirvensaloKlaus ReinhardtA. C. Cem SayAbuzer YakaryılmazWe 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.https://lmcs.episciences.org/4664/pdfcomputer science - formal languages and automata theorycomputer science - computational complexitycomputer science - logic in computer sciencequantum physics |
| spellingShingle | Gökalp Demirci Mika Hirvensalo Klaus Reinhardt A. C. Cem Say Abuzer Yakaryılmaz Alternating, private alternating, and quantum alternating realtime automata Logical Methods in Computer Science computer science - formal languages and automata theory computer science - computational complexity computer science - logic in computer science quantum physics |
| title | Alternating, private alternating, and quantum alternating realtime automata |
| title_full | Alternating, private alternating, and quantum alternating realtime automata |
| title_fullStr | Alternating, private alternating, and quantum alternating realtime automata |
| title_full_unstemmed | Alternating, private alternating, and quantum alternating realtime automata |
| title_short | Alternating, private alternating, and quantum alternating realtime automata |
| title_sort | alternating private alternating and quantum alternating realtime automata |
| topic | computer science - formal languages and automata theory computer science - computational complexity computer science - logic in computer science quantum physics |
| url | https://lmcs.episciences.org/4664/pdf |
| work_keys_str_mv | AT gokalpdemirci alternatingprivatealternatingandquantumalternatingrealtimeautomata AT mikahirvensalo alternatingprivatealternatingandquantumalternatingrealtimeautomata AT klausreinhardt alternatingprivatealternatingandquantumalternatingrealtimeautomata AT accemsay alternatingprivatealternatingandquantumalternatingrealtimeautomata AT abuzeryakaryılmaz alternatingprivatealternatingandquantumalternatingrealtimeautomata |