Detecting useless transitions in pushdown automata
2017
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.
Keywords:
- Two-way deterministic finite automaton
- Nested word
- Discrete mathematics
- Pushdown automaton
- Timed automaton
- Nested stack automaton
- Mathematics
- Deterministic context-free language
- Embedded pushdown automaton
- Algorithm
- Deterministic pushdown automaton
- Büchi automaton
- Theoretical computer science
- Computer science
- Deterministic automaton
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
1
Citations
NaN
KQI