A New Algorithm for the Determinisation of Visibly Pushdown Automata

Radomír Polách, Jan Travniček, Jan Janoušek, Bořivoj Melichar

DOI: http://dx.doi.org/10.15439/2015F325

Citation: Proceedings of the 2015 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 5, pages 915–922 (2015)

Full text

Abstract. 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 are computed and constructed during the determinisation.