A fast algorithm to decide on the equivalence of stateless DPDA
Caucal, Didier
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993), p. 23-48 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1993-01-01
@article{ITA_1993__27_1_23_0,
     author = {Caucal, Didier},
     title = {A fast algorithm to decide on the equivalence of stateless DPDA},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {27},
     year = {1993},
     pages = {23-48},
     mrnumber = {1213419},
     zbl = {0778.68051},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1993__27_1_23_0}
}

Caucal, Didier. A fast algorithm to decide on the equivalence of stateless DPDA. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) pp. 23-48. http://gdmltest.u-ga.fr/item/ITA_1993__27_1_23_0/

1. D. Caucal, Décidabilité de l'égalité des langages algébriques infinitaires simples, L.N.CS., Vol. 210, 1986, pp. 37-48. | MR 827723 | Zbl 0595.68072

2. D. Caucal, A Fast Algorithm to Decide on Simple Grammars Equivalence, L.N.C.S., Vol. 401 1989, pp. 66-85. | MR 1048156 | Zbl 0704.68072

3. B. Courcelle, An Axiomatic Approach to the KH Algorithms, Math. Systems Theory, Vol. 16, 1983, pp. 191-231. | MR 702448 | Zbl 0581.68032

4. B. Courcelle and J. Vuillemin, Completeness Result for the Equivalence of Recursive Schemes, J.C.S.S., Vol. 12, 1976, pp. 179-197. | MR 411225 | Zbl 0342.68008

5. M. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978. | MR 526397 | Zbl 0411.68058

6. M. Harrison, I. Havel and A. Yeduhaï, On Equivalence of Grammars Through Transformation Trees, T.C.S.,Vol. 9, 1979, pp. 191-231. | MR 540555 | Zbl 0409.68041

7. A. Korenjak and J. Hopcroft, Simple Deterministic Languages, Seventh annual I.E.E.E. switching and automata theory conference, 1966, pp. 36-46

8. T. Olshansky and A. Pnueli, A Direct Algorithm for Checking Equivalence of LL(k) Grammars, T.C.S., Vol. 4, 1977, pp. 321-349. | MR 461996 | Zbl 0358.68118

9. M. Oyamaguchi and N. Honda, The Decidability of Equivalence for Deterministic Stateless Pushdown Automata, Information and Control, Vol. 38, 1978, pp. 367-376. | MR 509559 | Zbl 0393.68078

10. E. Tomita, An Extended Direct Branching Algorithm for Checking Equivalence of Deterministic Pushdown Automata, T.C.S., Vol. 32, 1984, pp. 87-120 | MR 761163 | Zbl 0552.68065

11. L. Valiant, The Equivalence Problem for Deterministic Finite-Turn Pushdown Automata, Information and Control, Vol. 25, 1974, pp. 123-153. | MR 391591 | Zbl 0285.68025

12. L. Valiant and M. Paterson, Deterministic One-Counter Automata, J.C.S.S., Vol. 10, 1975, pp. 340-350. | MR 379149 | Zbl 0307.68038