Detecting useless transitions in pushdown automata

Dick Grune, Wan Fokkink*, Evangelos Chatzikalymnios, Brinio Hond, Peter Rutgers

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

21 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
Title of host publicationLanguage and Automata Theory and Applications
Subtitle of host publication11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings
EditorsFrank Drewes, Carlos Martín-Vide, Bianca Truthe
PublisherSpringer/Verlag
Pages421-434
Number of pages14
ISBN (Electronic)9783319537337
ISBN (Print)9783319537320
DOIs
Publication statusPublished - 2017
Event11th International Conference on Language and Automata Theory and Applications, LATA 2017 - Umea, Sweden
Duration: 6 Mar 20179 Mar 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10168 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Language and Automata Theory and Applications, LATA 2017
Country/TerritorySweden
City Umea
Period6/03/179/03/17

Fingerprint

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

Cite this