Self-Verifying Pushdown and Queue Automata

• Autorzy: Fernau Henning , Kutrib Martin , Wendlandt Matthias

Identyfikatory

DOI

10.3233/FI-2021-2032

• Języki publikacji: EN

Abstrakty

EN

We study the computational and descriptional complexity of self-verifying pushdown automata (SVPDA) and self-verifying realtime queue automata (SVRQA). A self-verifying automaton is a nondeterministic device whose nondeterminism is symmetric in the following sense. Each computation path can give one of the answers yes, no, or do not know. For every input word, at least one computation path must give either the answer yes or no, and the answers given must not be contradictory. We show that SVPDA and SVRQA are automata characterizations of so-called complementation kernels, that is, context-free or realtime nondeterministic queue automaton languages whose complement is also context free or accepted by a realtime nondeterministic queue automaton. So, the families of languages accepted by SVPDA and SVRQA are strictly between the families of deterministic and nondeterministic languages. Closure properties and various decidability problems are considered. For example, it is shown that it is not semidecidable whether a given SVPDA or SVRQA can be made self-verifying. Moreover, we study descriptional complexity aspects of these machines. It turns out that the size trade-offs between nondeterministic and self-verifying as well as between self-verifying and deterministic automata are non-recursive. That is, one can choose an arbitrarily large recursive function f, but the gain in economy of description eventually exceeds f when changing from the former system to the latter.

Słowa kluczowe

EN

recursive functions; computational complexity; robots

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 180, nr 1-2
• Strony: 1--28
• Opis fizyczny: Bibliogr. 26 poz., tab.

Twórcy

autor

Fernau Henning

• Fachbereich 4 – Abteilung Informatikwissenschaften, CIRT, Universität Trier, 54296 Trier, Germany

autor

Kutrib Martin

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

autor

Wendlandt Matthias

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

Bibliografia

• [1] Fischer PC, Kintala CMR. Real-Time Computations with Restricted Nondeterminism. Math. Systems Theory, 1979. 12:219-231. doi:10.1007/BF01776575.
• [2] Kintala CMR. Computations with a Restricted Number of Nondeterministic Steps. Ph.D. thesis, Pennsylvania State University, 1977.
• [3] Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S. Parameterized Algorithms. Springer, 2015. ISBN:978-3-319-21274-6, 978-3-319-35702-7.
• [4] Downey RG, Fellows MR. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. ISBN:978-1-4471-5559-1.
• [5] Duris P, Hromkovic J, Rolim JDP, Schnitger G. Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations. In: Reischuk R, Morvan M (eds.), Theoretical Aspects of Computer Science (STACS 1997), volume 1200 of LNCS. Springer, 1997 pp. 117-128. doi:10.1007/BFb0023453.
• [6] Hromkovic J, Schnitger G. On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata. Inform. Comput., 2001. 169:284-296. doi:10.1006/inco.2001.3040.
• [7] Hromkovic J, Schnitger G. Nondeterministic Communication with a Limited Number of Advice Bits. SIAM J. Comput., 2003. 33:43-68. doi:10.1137/S0097539702414622.
• [8] Jirásková G, Pighizzini G. Optimal simulation of self-verifying automata by deterministic automata. Inform. Comput., 2011. 209:528-535. doi:10.1016/j.ic.2010.11.017.
• [9] Ilie L, Păun G, Rozenberg G, Salomaa A. On Strongly Context-Free Languages. Discrete Appl. Math., 2000. 103:158-165. doi:10.1016/S0166-218X(99)00239-5.
• [10] Kutrib M, Malcher A, Wendlandt M. Queue Automata: Foundations and Developments. In: Adamatzky A (ed.), Reversibility and Universality, volume 30 of Emergence, Complexity and Computation, pp. 385-431. Springer, 2018. doi:10.1007/978-3-319-73216-9_19.
• [11] Cherubini A, Citrini C, Crespi-Reghizzi S, Mandrioli D. QRT FIFO Automata, Breadth-First Grammars and Their Relations. Theoret. Comput. Sci., 1991. 85:171-203.
• [12] Sudborough IH. One-Way Multihead Writing Finite Automata. Inform. Control, 1976. 30:1-20. doi:10.1016/S0019-9958(76)90426-5.
• [13] Sudborough IH. Computation by multihead writing finite automata. Ph.D. thesis, Pennsylvania State University, 1971.
• [14] Holzer M, Kutrib M. Descriptional Complexity - An Introductory Survey. In: Martín-Vide C (ed.), Scientific Applications of Language Methods, pp. 1-58. Imperial College Press, 2010. doi:10.1142/9781848165458_0001.
• [15] Hartmanis J. On Gödel speed-up and succinctness of language representations. Theoret. Comput. Sci., 1983. 26:335-342.
• [16] Hartmanis J. Context-free languages and Turing machine computations. Proc. Symposia in Applied Mathematics, 1967. 19:42-51. doi:10.2307/2272443.
• [17] Herzog C. Pushdown automata with bounded nondeterminism and bounded ambiguity. Theoret. Comput. Sci., 1997. 181:141-157. doi:10.1016/S0304-3975(96)00267-8.
• [18] Herzog C. Die Rolle des Nichtdeterminismus in kontextfreien Sprachen. Doctoral dissertation, Universität Frankfurt, 1999. (in German).
• [19] Holzer M, Kutrib M. One-Time Nondeterministic Computations. In: Pighizzini G, Câmpeanu C (eds.), Descriptional Complexity of Formal Systems (DCFS 2017), volume 10316 of LNCS. Springer, 2017 pp. 177-188. doi:10.1007/978-3-319-60252-3_14.
• [20] Harrison MA. Introduction to Formal Language Theory. Addison-Wesley, Reading, 1978.
• [21] Sénizergues G. L(A) = L(B)? Decidability Results from Complete Formal Systems. Theoret. Comput. Sci., 2001. 251:1-166. doi:10.1016/S0304-3975(00)00285-1.
• [22] Stearns RE. A regularity test for pushdown machines. Inform. Control, 1967. 11:323-340. doi:10.1016/S0019-9958(67)90591-8.
• [23] Rogers H. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967. doi:10.2307/2271523.
• [24] Salomaa A. Formal Languages. Academic Press, New York, 1973. doi:10.2307/2271881.
• [25] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Massachusetts, 1979. ISBN-13: 978-0201029888, 10:020102988X.
• [26] Schneider C. Deterministisch kontextfreie Sprachen und ihre Reversionen. Master’s thesis, Institut für Informatik, Universität Giessen, 2007. (in German).

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).