Tinput-Driven Pushdown, Counter, and Stack Automata

• Autorzy: Kutrib M. , Malcher A. , Wendlandt M.

Identyfikatory

DOI

10.3233/FI-2017-1576

• Języki publikacji: EN

Abstrakty

EN

In input-driven automata the input alphabet is divided into distinct classes and different actions on the storage medium are solely governed by the input symbols. For example, in inputdriven pushdown automata (IDPDA) there are three distinct classes of input symbols determining the action of pushing, popping, or doing nothing on the pushdown store. Here, input-driven automata are extended in such a way that the input is preprocessed by a deterministic sequential transducer. IDPDAs extended in this way are called tinput-driven pushdown automata (TDPDA) and it turns out that TDPDAs are more powerful than IDPDAs but still not as powerful as real-time deterministic pushdown automata. Nevertheless, even this stronger model has still good closure and decidability properties. In detail, it is shown that TDPDAs are closed under the Boolean operations union, intersection, and complementation. Furthermore, decidability procedures for the inclusion problem as well as for the questions of whether a given automaton is a TDPDA or an IDPDA are developed. Additionally, representation theorems for the context-free languages using IDPDAs and TDPDAs are established. Two other classes investigated are on the one hand TDPDAs restricted to tinput-driven counter automata and on the other hand TDPDAs generalized to tinput-driven stack automata. In both cases, it is possible to preserve the good closure and decidability properties of TDPDAs, namely, the closure under the Boolean operations as well as the decidability of the inclusion problem.

Słowa kluczowe

EN

machine theory; boolean functions; decidability; equivalence; finite state machine

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 155, nr 1/2
• Strony: 59--88
• Opis fizyczny: Bibliogr. 28 poz., rys., tab.

Twórcy

autor

Kutrib M.

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

autor

Malcher A.

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

autor

Wendlandt M.

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

Bibliografia

• [1] von Braunmühl B, Verbeek R. Input-Driven Languages are Recognized in log n Space. In: Karpinski M, van Leeuwen J, editors. Topics in the Theory of Computation. vol. 102 of Mathematics Studies. Amsterdam: North-Holland; 1985. p. 1–19. URL https://doi.org/10.1016/S0304-0208(08)73072-X.
• [2] Mehlhorn K. Pebbling Moutain Ranges and its Application of DCFL-Recognition. In: de Bakker JW, van Leeuwen J, editors. International Colloquium on Automata, Languages and Programming (ICALP 1980). vol. 85 of LNCS. Springer; 1980. p. 422–435. doi:10.1007/3-540-10003-2.
• [3] Dymond PW. Input-Driven Languages are in log n Depth. Inform Process Lett. 1988;26(5):247–250. URL https://doi.org/10.1016/0020-0190(88)90148-2.
• [4] Alur R, Madhusudan P. Visibly pushdown languages. In: Babai L, editor. Symposium on Theory of Computing (STOC 2004). ACM; 2004. p. 202–211. doi: 10.1145/1007352.1007390.
• [5] Alur R, Madhusudan P. Adding nesting structure to words. J ACM. 2009;56(3)16:1–16:43. doi:10.1145/1516512.1516518.
• [6] Okhotin A, Salomaa K. Complexity of input-driven pushdown automata. SIGACT News. 2014;45(2):47–67. doi:10.1145/2636805.2636821.
• [7] Chervet P, Walukiewicz I. Minimizing Variants of Visibly Pushdown Automata. In: Kucera L, Kucera A, editors. Mathematical Foundations of Computer Science (MFCS 2007). vol. 4708 of LNCS. Springer; 2007. p. 135–146. ISBN:3-540-74455-X, 978-3-540-74455-9.
• [8] Crespi-Reghizzi S, Mandrioli D. Operator precedence and the visibly pushdown property. J Comput System Sci. 2012;78(6):1837–1867. doi:10.1016/j.jcss.2011.12.006.
• [9] La Torre S, Madhusudan P, Parlato G. A Robust Class of Context-Sensitive Languages. In: Logic in Computer Science (LICS 2007). IEEE Computer Society; 2007. p. 161–170. doi:10.1109/LICS.2007.9.
• [10] Madhusudan P, Parlato G. The tree width of auxiliary storage. In: Ball T, Sagiv M, editors. Principles of Programming Languages, (POPL 2011). ACM; 2011. p. 283–294. doi:10.1145/1925844.1926419.
• [11] Autebert JM, Berstel J, Boasson L. Context-free Languages and Pushdown Automata. In: Rozenberg G, Salomaa A, editors. Handbook of Formal Languages. vol. 1. Berlin: Springer; 1997. p. 111–174. ISBN:3-540-60420-0.
• [12] Bárány V, Löding C, Serre O. Regularity Problems for Visibly Pushdown Languages. In: Durand B, Thomas W, editors. Symposium on Theoretical Aspects of Computer Science (STACS 2006). vol. 3884 of LNCS. Springer; 2006. p. 420–431. ISBN:3-540-32301-5 978-3-540-32301-3. doi:10.1007/11672142_34.
• [13] Hahn M, Krebs A, Lange K, Ludwig M. Visibly Counter Languages and the Structure of NC1. In: Italiano GF, Pighizzini G, Sannella D, editors. Mathematical Foundations of Computer Science (MFCS 2015). vol. 9235 of LNCS. Springer; 2015. p. 384–394. doi:10.1007/978-3-662-48054-0_32.
• [14] Krebs A, Lange K, Ludwig M. Visibly Counter Languages and Constant Depth Circuits. In: Mayr EW, Ollinger N, editors. Symposium on Theoretical Aspects of Computer Science (STACS 2015). vol. 30 of LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik; 2015. p. 594–607. doi:10.4230/LIPIcs.STACS.2015.594.
• [15] Ginsburg S, Greibach SA, Harrison MA. Stack automata and compiling. J ACM. 1967;14:172–201.
• [16] Ginsburg S, Greibach SA, Harrison MA. One-Way Stack Automata. J ACM. 1967;14:389–418.
• [17] Bensch S, Holzer M, Kutrib M, Malcher A. Input-Driven Stack Automata. In: Baeten JCM, Ball T, de Boer FS, editors. Theoretical Computer Science (TCS 2012). vol. 7604 of LNCS. Springer; 2012. p. 28–42. doi:10.1007/978-3-642-33475-7_3.
• [18] Kutrib M, Malcher A, Mereghetti C, Palano B, Wendlandt M. Deterministic Input-Driven Queue Automata: Finite Turns, Decidability, and Closure Properties. Theoret Comput Sci. 2015;578(C):58–71. doi:10.1016/j.tcs.2015.01.012.
• [19] Caucal D. Synchronization of Pushdown Automata. In: Ibarra OH, Dang Z, editors. Developments in Language Theory (DLT 2006). vol. 4036 of LNCS. Springer; 2006. p. 120–132. doi:10.1007/11779148 12.
• [20] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation. Reading, Massachusetts: Addison-Wesley; 1979.
• [21] Hartmanis J, Hopcroft JE. What makes Some Language Theory Problems Undecidable. J Comput Syst Sci. 1970;4(4):368–376. URL https://doi.org/10.1016/S0022-0000(70)80018-6.
• [22] Schützenberger MP. Sur les relations rationelles. In: Braklage H, editor. Automata Theory and Formal Languages. vol. 33 of LNCS. Springer; 1975. p. 209–213. ISBN:3-540-07407-4.
• [23] Bordihn H, Holzer M, Kutrib M. Economy of Description for Basic Constructions on Rational Transductions. J Autom Lang Comb. 2004;9(2-3):175–188. URL http://dl.acm.org/citation.cfm?id=1103362.1103364.
• [24] Yu S. Regular Languages. In: Rozenberg G, Salomaa A, editors. Handbook of Formal Languages. vol. 1. Berlin: Springer; 1997. p. 41–110. doi:10.1007/978-3-642-59136-5_2.
• [25] Myhill J. Finite Automata and the Representation of Events. WADC; 1957. TR 57-624.
• [26] Okhotin A. Non-erasing Variants of the Chomsky-Schützenberger Theorem. In: Yen HC, Ibarra OH, editors. Developments in Language Theory (DLT 2012). vol. 7410 of LNCS. Springer; 2012. p. 121–129. doi:10.1007/978-3-642-31653-1_12.
• [27] Li M, Vitányi PMB. An Introduction to Kolmogorov Complexity and Its Applications. Springer; 1993. doi:10.1007/978-1-4757-3860-5.
• [28] Ogden WF. Intercalation Theorems for Stack Languages. In: Proceedings of the First Annual ACM Symposium on Theory of Computing (STOC 1969). New York: ACM Press; 1969. p. 31–42. doi:10.1145/800169.805419.