Deciding DPDA Equivalence Is Primitive Recursive

Colin Stirling

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)978-3-540-45465-6
ISBN (Print)978-3-540-43864-9
Publication statusPublished - 2002

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Deciding DPDA Equivalence Is Primitive Recursive'. Together they form a unique fingerprint.

Cite this