Deciding DPDA Equivalence Is Primitive Recursive

Colin Stirling

doi:10.1007/3-540-45465-9_70

Deciding DPDA Equivalence Is Primitive Recursive

Colin Stirling

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Recently Sénizergues showed decidability of the equivalence problem for deterministic pushown automata. The proof of decidability is two semi-decision procedures that do not give a complexity upper bound for the problem. Here we show that there is a simpler deterministic decision procedure that has a primitive recursive upper bound.

Original language	English
Title of host publication	Automata, Languages and Programming
Subtitle of host publication	29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings
Publisher	Springer Berlin Heidelberg
Pages	821-832
Number of pages	12
ISBN (Electronic)	978-3-540-45465-6
ISBN (Print)	978-3-540-43864-9
DOIs	https://doi.org/10.1007/3-540-45465-9_70
Publication status	Published - 2002

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	2380
ISSN (Print)	0302-9743

Access to Document

10.1007/3-540-45465-9_70

http://link.springer.com/chapter/10.1007%2F3-540-45465-9_70

Cite this

@inproceedings{a193e324e71648c2a5a53810d2a377c5,

title = "Deciding DPDA Equivalence Is Primitive Recursive",

abstract = "Recently S{\'e}nizergues showed decidability of the equivalence problem for deterministic pushown automata. The proof of decidability is two semi-decision procedures that do not give a complexity upper bound for the problem. Here we show that there is a simpler deterministic decision procedure that has a primitive recursive upper bound.",

author = "Colin Stirling",

year = "2002",

doi = "10.1007/3-540-45465-9_70",

language = "English",

isbn = "978-3-540-43864-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "821--832",

booktitle = "Automata, Languages and Programming",

}

Deciding DPDA Equivalence Is Primitive Recursive. / Stirling, Colin.

Automata, Languages and Programming: 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings. Springer Berlin Heidelberg, 2002. p. 821-832 (Lecture Notes in Computer Science; Vol. 2380).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Deciding DPDA Equivalence Is Primitive Recursive

AU - Stirling, Colin

PY - 2002

Y1 - 2002

N2 - Recently Sénizergues showed decidability of the equivalence problem for deterministic pushown automata. The proof of decidability is two semi-decision procedures that do not give a complexity upper bound for the problem. Here we show that there is a simpler deterministic decision procedure that has a primitive recursive upper bound.

AB - Recently Sénizergues showed decidability of the equivalence problem for deterministic pushown automata. The proof of decidability is two semi-decision procedures that do not give a complexity upper bound for the problem. Here we show that there is a simpler deterministic decision procedure that has a primitive recursive upper bound.

U2 - 10.1007/3-540-45465-9_70

DO - 10.1007/3-540-45465-9_70

M3 - Conference contribution

SN - 978-3-540-43864-9

T3 - Lecture Notes in Computer Science

SP - 821

EP - 832

BT - Automata, Languages and Programming

PB - Springer Berlin Heidelberg

ER -

Deciding DPDA Equivalence Is Primitive Recursive

Abstract

Publication series

Access to Document

Fingerprint

Cite this