A practical simulation result for two-way pushdown automata

Robert Glück

doi:10.1007/978-3-319-40946-7_10

A practical simulation result for two-way pushdown automata

Robert Glück

Department of Computer Science

2 Citations (Scopus)

Abstract

The simulation of two-way deterministic and nondeterministic pushdown automata is revisited. A uniform algorithm presented herein decides on a random-access machine in linear time resp. cubic time whether a given pushdown automaton accepts a word, while the actual run of the automaton may take exponential time. The algorithm is practical since it only explores reachable configurations, simulates a class of quasi-deterministic decision problems in linear time even if the pushdown automaton is nondeterministic, and iterates over a simple work list. This is an improvement over previous simulation algorithms.

Original language	English
Title of host publication	Implementation and Application of Automata : 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings
Editors	Yo-Sub Han, Kai Salomaa
Publisher	Springer
Publication date	2016
Pages	113-124
ISBN (Print)	978-3-319-40945-0
ISBN (Electronic)	978-3-319-40946-7
DOIs	https://doi.org/10.1007/978-3-319-40946-7_10
Publication status	Published - 2016
Event	21st International Conference on Implementation and Application of Automata - Seoul, Korea, Republic of Duration: 19 Jul 2016 → 22 Jul 2016 Conference number: 21

Conference

Conference	21st International Conference on Implementation and Application of Automata
Number	21
Country/Territory	Korea, Republic of
City	Seoul
Period	19/07/2016 → 22/07/2016

Series	Lecture Notes in Computer Science
Number	9705
ISSN	0302-9743

Access to Document

10.1007/978-3-319-40946-7_10

Cite this

A practical simulation result for two-way pushdown automata. / Glück, Robert.
Implementation and Application of Automata: 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings. ed. / Yo-Sub Han; Kai Salomaa. Springer, 2016. p. 113-124 (Lecture Notes in Computer Science; No. 9705).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Glück, R 2016, A practical simulation result for two-way pushdown automata. in Y-S Han & K Salomaa (eds), Implementation and Application of Automata: 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings. Springer, Lecture Notes in Computer Science, no. 9705, pp. 113-124, 21st International Conference on Implementation and Application of Automata, Seoul, Korea, Republic of, 19/07/2016. https://doi.org/10.1007/978-3-319-40946-7_10

@inproceedings{50dbacd8cb8342f998204b66252748b8,

title = "A practical simulation result for two-way pushdown automata",

abstract = "The simulation of two-way deterministic and nondeterministic pushdown automata is revisited. A uniform algorithm presented herein decides on a random-access machine in linear time resp. cubic time whether a given pushdown automaton accepts a word, while the actual run of the automaton may take exponential time. The algorithm is practical since it only explores reachable configurations, simulates a class of quasi-deterministic decision problems in linear time even if the pushdown automaton is nondeterministic, and iterates over a simple work list. This is an improvement over previous simulation algorithms.",

author = "Robert Gl{\"u}ck",

year = "2016",

doi = "10.1007/978-3-319-40946-7_10",

language = "English",

isbn = "978-3-319-40945-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "9705",

pages = "113--124",

editor = "Yo-Sub Han and Kai Salomaa",

booktitle = "Implementation and Application of Automata",

note = "21st International Conference on Implementation and Application of Automata ; Conference date: 19-07-2016 Through 22-07-2016",

}

TY - GEN

T1 - A practical simulation result for two-way pushdown automata

AU - Glück, Robert

N1 - Conference code: 21

PY - 2016

Y1 - 2016

N2 - The simulation of two-way deterministic and nondeterministic pushdown automata is revisited. A uniform algorithm presented herein decides on a random-access machine in linear time resp. cubic time whether a given pushdown automaton accepts a word, while the actual run of the automaton may take exponential time. The algorithm is practical since it only explores reachable configurations, simulates a class of quasi-deterministic decision problems in linear time even if the pushdown automaton is nondeterministic, and iterates over a simple work list. This is an improvement over previous simulation algorithms.

AB - The simulation of two-way deterministic and nondeterministic pushdown automata is revisited. A uniform algorithm presented herein decides on a random-access machine in linear time resp. cubic time whether a given pushdown automaton accepts a word, while the actual run of the automaton may take exponential time. The algorithm is practical since it only explores reachable configurations, simulates a class of quasi-deterministic decision problems in linear time even if the pushdown automaton is nondeterministic, and iterates over a simple work list. This is an improvement over previous simulation algorithms.

U2 - 10.1007/978-3-319-40946-7_10

DO - 10.1007/978-3-319-40946-7_10

M3 - Article in proceedings

SN - 978-3-319-40945-0

T3 - Lecture Notes in Computer Science

SP - 113

EP - 124

BT - Implementation and Application of Automata

A2 - Han, Yo-Sub

A2 - Salomaa, Kai

PB - Springer

T2 - 21st International Conference on Implementation and Application of Automata

Y2 - 19 July 2016 through 22 July 2016

ER -