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

Datalogisk Institut

2 Citationer (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.

Originalsprog	Engelsk
Titel	Implementation and Application of Automata : 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings
Redaktører	Yo-Sub Han, Kai Salomaa
Forlag	Springer
Publikationsdato	2016
Sider	113-124
ISBN (Trykt)	978-3-319-40945-0
ISBN (Elektronisk)	978-3-319-40946-7
DOI	https://doi.org/10.1007/978-3-319-40946-7_10
Status	Udgivet - 2016
Begivenhed	21st International Conference on Implementation and Application of Automata - Seoul, Sydkorea Varighed: 19 jul. 2016 → 22 jul. 2016 Konferencens nummer: 21

Konference

Konference	21st International Conference on Implementation and Application of Automata
Nummer	21
Land/Område	Sydkorea
By	Seoul
Periode	19/07/2016 → 22/07/2016

Navn	Lecture Notes in Computer Science
Nummer	9705
ISSN	0302-9743

Adgang til dokumentet

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

Citationsformater

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. red. / Yo-Sub Han; Kai Salomaa. Springer, 2016. s. 113-124 (Lecture Notes in Computer Science; Nr. 9705).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Glück, R 2016, A practical simulation result for two-way pushdown automata. i Y-S Han & K Salomaa (red), Implementation and Application of Automata: 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings. Springer, Lecture Notes in Computer Science, nr. 9705, s. 113-124, 21st International Conference on Implementation and Application of Automata, Seoul, Sydkorea, 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 -