A Short Decidability Proof for DPDA Language Equivalence via First-Order Grammars

Details A Short Decidability Proof for DPDA Language Equivalence via First-Order Grammars A Short Decidability Proof for DPDA Language Equivalence via First-Order Grammars

2010-10-22

arxiv.org/abs/1010.4760v4

Computer Science

Formal Languages and Automata Theory

28 pages, version 4 reworks the main proof and omits the nondeterministic case where a problem was found by G. Senizergues

Scientific paper

The main aim of the paper is to give a short self-contained proof of the decidability of language equivalence for deterministic pushdown automata, which is the famous problem solved by G. Senizergues, for which C. Stirling has derived a primitive recursive complexity upper bound. The proof here is given in the framework of first-order grammars, which seems to be particularly apt for the aim. An appendix presents a modification of Stirling's approach, yielding a complexity bound of the form tetr(2,g(n)) where tetr is the (nonelementary) operator of iterated exponentiation (tetration) and g is an elementary function of the input size.

Affiliated with

Also associated with

No associations

Rating

A Short Decidability Proof for DPDA Language Equivalence via First-Order Grammars does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Short Decidability Proof for DPDA Language Equivalence via First-Order Grammars, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Short Decidability Proof for DPDA Language Equivalence via First-Order Grammars will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-660901