Deciding DPDA Equivalence Is Primitive Recursive

Colin Stirling

Research output: Chapter in Book/Report/Conference proceedingConference 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 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
Pages821-832
Number of pages12
ISBN (Electronic)978-3-540-45465-6
ISBN (Print)978-3-540-43864-9
DOIs
Publication statusPublished - 2002

Publication series

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

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

Cite this