A New Algorithm for the Determinisation of Visibly Pushdown Automata
Radomír Polách, Jan Trávníček, Jan Janoušek, Bořivoj Melichar · Annals of Computer Science and Information Systems · 2015
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.