Decidability of DPDA equivalence

Authors
Stirling, C
Citation
C. Stirling, Decidability of DPDA equivalence, THEOR COMP, 255(1-2), 2001, pp. 1-31
Citations number
12
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
255
Issue
1-2
Year of publication
2001
Pages
1 - 31
Database
ISI
SICI code
0304-3975(20010328)255:1-2<1:DODE>2.0.ZU;2-6
Abstract
A proof of decidability of equivalence between deterministic pushdown autom ata is presented using a mixture of methods developed in concurrency and la nguage theory. The technique appeals to a tableau proof system for equivale nce of configurations of strict deterministic grammars. (C) 2001 Elsevier S cience B.V. All rights reserved.