Skip to main navigation Skip to search Skip to main content

Detecting useless transitions in pushdown automata

  • Evangelos Chatzikalymnios
  • , Wan Fokkink*
  • , Dick Grune
  • , Brinio Hond
  • , Peter Rutgers
  • *Corresponding author for this work

Research output: Contribution to Journal › Article › Academic › peer-review

218 Downloads (Pure)

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.

Original languageEnglish
Article number104612
Pages (from-to)1-12
Number of pages12
JournalInformation and Computation
Volume279
Early online date7 Aug 2020
DOIs
Publication statusPublished - Aug 2021

Bibliographical note

Publisher Copyright:
© 2020 Elsevier Inc.

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

Funding

Javier Esparza proposed the alternative approach using pre⁎ and post⁎. Jörg Endrullis provided a useful suggestion for the efficient implementation of this alternative approach.

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

  1. SDG 7 - Affordable and Clean Energy
    SDG 7 Affordable and Clean Energy

Keywords

  • Finite automaton
  • Pushdown automaton
  • Useless transition

Fingerprint

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

Cite this