TY - GEN
T1 - Detecting useless transitions in pushdown automata
AU - Grune, Dick
AU - Fokkink, Wan
AU - Chatzikalymnios, Evangelos
AU - Hond, Brinio
AU - Rutgers, Peter
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85013441213&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85013441213&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-53733-7_31
DO - 10.1007/978-3-319-53733-7_31
M3 - Conference contribution
AN - SCOPUS:85013441213
SN - 9783319537320
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 421
EP - 434
BT - Language and Automata Theory and Applications
A2 - Drewes, Frank
A2 - Martín-Vide, Carlos
A2 - Truthe, Bianca
PB - Springer/Verlag
T2 - 11th International Conference on Language and Automata Theory and Applications, LATA 2017
Y2 - 6 March 2017 through 9 March 2017
ER -