Visibly Pushdown Automata and Transducers with Counters

• Autorzy: Ibarra O. H.

Identyfikatory

DOI

10.3233/FI-2016-1436

• Języki publikacji: EN

Abstrakty

EN

We generalize the models of visibly pushdown automata (VPDAs) and visibly pushdown transducers (VPDTs) by equipping them with reversal-bounded counters. We show that some of the results for VPDAs and VPDTs (e.g., closure under intersection and decidability of emptiness for VPDA languages) carry over to the generalized models, but other results (e.g., determinization and closure under complementation) do not carry over, in general. We define a model that combines the desirable features of a VPDA and reversal-bounded counters, called 2- phase VPCM, and show that the deterministic and nondeterministic versions are equivalent and that the family of languages they define is closed under Boolean operations and has decidable emptiness, infiniteness, disjointness, containment, and equivalence problems. We also investigate the finite-ambiguity and finite-valuedness problems concerning these devices.

Słowa kluczowe

EN

pushdown automaton; pushdown transducer; visibly pushdown automaton; visibly pushdown transducer; reversal-bounded counters; ambiguous; finite-valued; decidable; undecidable

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 148, nr 3/4
• Strony: 291--308
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Ibarra O. H.

• Department of Computer Science, University of California, Santa Barbara, CA 93106, USA

Bibliografia

• [1] Alur R, Madhusudan P. Visibly Pushdown Languages. In: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing. STOC ’04. New York, NY, USA: ACM; 2004. p. 202–211. Available from: http://doi.acm.org/10.1145/1007352.1007390. doi:10.1145/1007352.1007390.
• [2] Mehlhorn K. Pebbling Moutain Ranges and Its Application of DCFL-Recognition. In: Proceedings of the 7th Colloquium on Automata, Languages and Programming. London, UK, UK: Springer-Verlag; 1980. p.422–435. Available from: http://dl.acm.org/citation.cfm?id=646234.682537.
• [3] von Braunmühl B, Verbeek R. Input Driven Languages Are Recognized in Log N Space. In: Selected Papers of the International Conference on ”Foundations of Computation Theory” on Topics in the Theory of Computation. New York, NY, USA: Elsevier North-Holland, Inc.; 1985. p. 1–19. Available from: http://dl.acm.org/citation.cfm?id=4030.4031.
• [4] Rytter W. An Application of Mehlhorn’s Algorithm for Bracket Languages to Log(N) Space Recognition of Input-driven Languages. Inf Process Lett. 1986 Aug; 23(2):81–84. Available from: http://dx.doi.org/10.1016/0020-0190(86)90047-5. doi:10.1016/0020-0190(86)90047-5.
• [5] Okhotin A, Salomaa K. Complexity of Input-driven Pushdown Automata. SIGACT News. 2014 Jun; 45(2):47–67. Available from: http://doi.acm.org/10.1145/2636805.2636821. doi:10.1145/2636805.2636821.
• [6] Raskin JF, Servais F. Visibly Pushdown Transducers. In: ICALP (2); 2008. p. 386–397.
• [7] Filiot E, Raskin JF, Reynier PA, Servais F, Talbot JM. Properties of Visibly Pushdown Transducers. In: Hlinený P, Kucera A, editors. Mathematical Foundations of Computer Science (MFCS). vol. 6281 of Lecture Notes in Computer Science. Springer; 2010. p. 355–367.
• [8] Ibarra OH. Reversal-Bounded Multicounter Machines and Their Decision Problems. J ACM. 1978 Jan; 25(1):116–133. Available from: http://doi.acm.org/10.1145/322047.322058. doi:10.1145/322047.322058.
• [9] Minsky ML. Recursive Unsolvability of Post’s Problem of ”Tag” and other Topics in Theory of Turing Machines. Annals of Mathematics. 1961;74(2):437–455.
• [10] Chiniforooshan E, Daley M, Ibarra OH, Kari L, Seki S. One-reversal Counter Machines and Multihead Automata: Revisited. Theor Comput Sci. 2012 Oct;454:81–87. Available from: http://dx.doi.org/10.1016/j.tcs.2012.04.002. doi:10.1016/j.tcs.2012.04.002.
• [11] Ibarra OH, Yen HC. On the Containment and Equivalence Problems for Two-way Transducers. Theor Comput Sci. 2012;429:155–163. Available from: http://dblp.uni-trier.de/db/journals/tcs/tcs429.html#IbarraY12.
• [12] Hopcroft JE, Ullman JD. Introduction To Automata Theory, Languages, And Computation. 1st ed. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.; 1990.
• [13] Baker BS, Book RV. Reversal-bounded Multipushdown Machines. J Comput Syst Sci. 1974 Jun;8(3):315–332. Available from: http://dx.doi.org/10.1016/S0022-0000(74)80027-9. doi:10.1016/S0022-0000(74)80027-9.
• [14] Eremondi J, Ibarra OH, McQuillan I. Insertion Operations on Deterministic Reversal-Bounded Counter Machines. In: Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings; 2015. p. 200–211. Available from: http://dx.doi.org/10.1007/978-3-319-15579-1_15. doi:10.1007/978-3-319-15579-1_15.
• [15] Wich K. Exponential Ambiguity of Context-Free Grammars. In: Developments in Language Theory, Foundations, Applications, and Perspectives, Aachen, Germany, 6-9 July 1999; 1999. p. 125–138.
• [16] Ibarra OH. On the Ambiguity, Finite-Valuedness, and Lossiness Problems in Acceptors and Transducers. In: Implementation and Application of Automata - 19th International Conference, CIAA 2014, Giessen, Germany, July 30 - August 2, 2014. Proceedings; 2014. p. 211–225. Available from: http://dx.doi.org/10.1007/978-3-319-08846-4_16. doi:10.1007/978-3-319-08846-4_16.
• [17] Blattner M, Head T. The Decidability of Equivalence for Deterministic Finite Transducers. Journal of Computer and System Sciences. 1979;19(1):45–49. Available from: http://www.sciencedirect.com/science/article/pii/0022000079900126. doi:http://dx.doi.org/10.1016/0022-0000(79)90012-6.
• [18] Griffiths TV. The Unsolvability of the Equivalence Problem for Epsilon-Free Nondeterministic Generalized Machines. J ACM. 1968 Jul;15(3):409–413. Available from: http://doi.acm.org/10.1145/321466.321473. doi:10.1145/321466.321473.
• [19] Ibarra OH. The Unsolvability of the Equivalence Problem for Epsilon-Free NGSM’s with Unary Input (Output) Alphabet and Applications. SIAM J Comput. 1978;7(4):524–532. Available from: http://dx.doi.org/10.1137/0207042. doi:10.1137/0207042.
• [20] Gurari EM, Ibarra OH. A Note on Finite-Valued and Finitely Ambiguous Transducers. Theory of Computing Systems / Mathematical Systems Theory. 1983;16:61–66. doi:10.1007/BF01744569.
• [21] II KC, Karhumäki J. The Equivalence of Finite-Valued Transducers (On HDT0L Languages) is Decidable. Theor Comput Sci. 1986;47(3):71–84. Available from: http://dx.doi.org/10.1016/0304-3975(86)90134-9. doi:10.1016/0304-3975(86)90134-9.
• [22] Weber A. Decomposing Finite-Valued Transducers and Deciding Their Equivalence. SIAM J Comput. 1993;22(1):175–202. Available from: http://dblp.uni-trier.de/db/journals/siamcomp/siamcomp22.html#Weber93.
• [23] Hague M, Lin AW. Model Checking Recursive Programs with Numeric Data Types. In: Computer Aided Verification (CAV); 2011.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).