Detecting useless transitions in pushdown automata

Evangelos Chatzikalymnios; Wan Fokkink; Dick Grune; Brinio Hond; Peter Rutgers

doi:10.1016/j.ic.2020.104612

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

173 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 language	English
Article number	104612
Pages (from-to)	1-12
Number of pages	12
Journal	Information and Computation
Volume	279
Early online date	7 Aug 2020
DOIs	https://doi.org/10.1016/j.ic.2020.104612
Publication status	Published - 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.

Keywords

Finite automaton
Pushdown automaton
Useless transition

UN SDGs

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

Access to Document

10.1016/j.ic.2020.104612

Detecting useless transitions in pushdown automataFinal published version, 387 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

@article{fddb6125f76e4e7b93131cc7e3441a92,

title = "Detecting useless transitions in pushdown automata",

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.",

keywords = "Finite automaton, Pushdown automaton, Useless transition",

author = "Evangelos Chatzikalymnios and Wan Fokkink and Dick Grune and Brinio Hond and Peter Rutgers",

year = "2021",

month = aug,

doi = "10.1016/j.ic.2020.104612",

language = "English",

volume = "279",

pages = "1--12",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Detecting useless transitions in pushdown automata

AU - Chatzikalymnios, Evangelos

AU - Fokkink, Wan

AU - Grune, Dick

AU - Hond, Brinio

AU - Rutgers, Peter

PY - 2021/8

Y1 - 2021/8

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.

KW - Finite automaton

KW - Pushdown automaton

KW - Useless transition

UR - https://www.scopus.com/pages/publications/85089138903

UR - https://www.scopus.com/inward/citedby.url?scp=85089138903&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2020.104612

DO - 10.1016/j.ic.2020.104612

M3 - Article

AN - SCOPUS:85089138903

SN - 0890-5401

VL - 279

SP - 1

EP - 12

JO - Information and Computation

JF - Information and Computation

M1 - 104612

ER -

Detecting useless transitions in pushdown automata

Abstract

Bibliographical note

Funding

Keywords

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this