Detecting useless transitions in pushdown automata

Authors :: Evangelos Chatzikalymnios
Wan Fokkink
Dick Grune
Brinio Hond
Peter Rutgers
Theoretical Computer Science
Network Institute
Source :: Chatzikalymnios, E, Fokkink, W, Grune, D, Hond, B & Rutgers, P 2021, ' Detecting useless transitions in pushdown automata ', Information and Computation, vol. 279, 104612, pp. 1-12 . https://doi.org/10.1016/j.ic.2020.104612, Information and Computation, 279:104612, 1-12. Elsevier Inc.
Publication Year :: 2021
Abstract: 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.

Subjects :: TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Computational Theory and Mathematics
Finite automaton
SDG 7 - Affordable and Clean Energy
Nonlinear Sciences::Cellular Automata and Lattice Gases
Pushdown automaton
Useless transition
Computer Science::Formal Languages and Automata Theory
Computer Science Applications
Information Systems
Theoretical Computer Science

Language :: English
ISSN :: 08905401
Database :: OpenAIRE
Journal :: Chatzikalymnios, E, Fokkink, W, Grune, D, Hond, B & Rutgers, P 2021, ' Detecting useless transitions in pushdown automata ', Information and Computation, vol. 279, 104612, pp. 1-12 . https://doi.org/10.1016/j.ic.2020.104612, Information and Computation, 279:104612, 1-12. Elsevier Inc.
Accession number :: edsair.doi.dedup.....9945ed2e0cf7be2ec7a8fa8d3c2ac365
Full Text :: https://doi.org/10.1016/j.ic.2020.104612