Detecting useless transitions in pushdown automata

Dick Grune, Wan Fokkink*, Evangelos Chatzikalymnios, Brinio Hond, Peter Rutgers

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review


Pushdown automata may contain transitions that are never used in any accepting run of the automaton. We present an algorithm for detecting such useless transitions. A finite automaton that captures the possible stack content during runs of the pushdown automaton, is first constructed in a forward procedure to determine which transitions are reachable, and then employed in a backward procedure to determine which of these transitions can lead to a final state. An implementation of the algorithm is shown to exhibit a favorable performance.

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications
Subtitle of host publication11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings
EditorsFrank Drewes, Carlos Martín-Vide, Bianca Truthe
Number of pages14
ISBN (Electronic)9783319537337
ISBN (Print)9783319537320
Publication statusPublished - 2017
Event11th International Conference on Language and Automata Theory and Applications, LATA 2017 - Umea, Sweden
Duration: 6 Mar 20179 Mar 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10168 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th International Conference on Language and Automata Theory and Applications, LATA 2017
City Umea


Dive into the research topics of 'Detecting useless transitions in pushdown automata'. Together they form a unique fingerprint.

Cite this