A New Algorithm for the Determinisation of Visibly Pushdown Automata

• Autorzy: Radomír Polách , Jan Trávnícek , Jan Janoušek , Borivoj Melichar
• Języki publikacji: EN

Abstrakty

EN

Visibly pushdown automata are pushdown automata whose pushdown operations are determined by the input symbol, where the input alphabet is partitioned into three parts for push, pop and local pushdown operations. It is well known that nondeterministic visibly pushdown automata can be determinised. In this paper a new algorithm for the determinisation of nondeterministic visibly pushdown automata is presented. The algorithm improves the existing methods and can result in significantly smaller deterministic pushdown automata. This is achieved in a way that only necessary and accessible states and pushdown symbols are computed and constructed during the determinisation.(original abstract)

Słowa kluczowe

EN

Algorithms; Cybernetics

PL

Algorytmy; Cybernetyka

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 5
• Strony: 915--922

Twórcy

autor

Radomír Polách

• Czech Technical University in Prague

autor

Jan Trávnícek

• Czech Technical University in Prague

autor

Jan Janoušek

• Czech Technical University in Prague

autor

Borivoj Melichar

• Czech Technical University in Prague

Bibliografia

• R. Alur. Marrying words and trees. In J. Meseguer and G. Rosu, editors, Algebraic Methodology and Software Technology, 12th International Conference, AMAST 2008, Urbana, IL, USA, July 28-31, 2008, Proceedings, volume 5140 of Lecture Notes in Computer Science, page 1. Springer, 2008.
• R. Alur, V. Kumar, P. Madhusudan, and M. Viswanathan. Congruences for visibly pushdown languages. In L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, and M. Yung, editors, Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 of Lecture Notes in Computer Science, pages 1102-1114. Springer, 2005.
• R. Alur and P. Madhusudan. Visibly pushdown languages. In L. Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 202-211. ACM, 2004.
• Arbology www pages. Available on: http://arbology.fit.cvut.cz/, 2015. May 2015.
• V. Bárány, C. Löding, and O. Serre. Regularity problems for visibly pushdown languages. In B. Durand and W. Thomas, editors, STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, volume 3884 of Lecture Notes in Computer Science, pages 420-431. Springer, 2006.
• D. Debarbieux, O. Gauwin, J. Niehren, T. Sebastian, and M. Zergaoui. Early nested word automata for xpath query answering on XML streams. Theor. Comput. Sci., 578:100-125, 2015.
• E. Filiot, J. Raskin, P. Reynier, F. Servais, and J. Talbot. Properties of visibly pushdown transducers. In P. Hlinený and A. Kucera, editors, Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings, volume 6281 of Lecture Notes in Computer Science, pages 355-367. Springer, 2010.
• J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to automata theory, languages and computation. Addison-Wesley, second edition, 2001.
• H. Nguyen. Visibly pushdown automata library. Available on: http: //www.emn.fr/z-info/hnguyen/vpa/, 2015. May 2015.
• D. Nowotka and J. Srba. Height-deterministic pushdown automata. In L. Kucera and A. Kucera, editors, Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings, volume 4708 of Lecture Notes in Computer Science, pages 125-134. Springer, 2007.
• J. Srba. Visibly pushdown automata: From language equivalence to simulation and bisimulation. In Z. Ésik, editor, Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006, Proceedings, volume 4207 of Lecture Notes in Computer Science, pages 89-103. Springer, 2006.
• N. V. Tang. A tighter bound for the determinization of visibly pushdown automata. In A. Legay, editor, Proceedings International Workshop on Verification of Infinite-State Systems, INFINITY 2009, Bologna, Italy, 31th August 2009., volume 10 of EPTCS, pages 62-76, 2009.
• J. Trávnícek. ALT: Automata (Algorithms) Library Toolkit, 2015.

Identyfikatory

DOI

10.15439/2015F325