A fast algorithm to decide on the equivalence of stateless DPDA

Didier Caucal

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1993)

  • Volume: 27, Issue: 1, page 23-48
  • ISSN: 0988-3754

How to cite

top

Caucal, Didier. "A fast algorithm to decide on the equivalence of stateless DPDA." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 27.1 (1993): 23-48. <http://eudml.org/doc/92436>.

@article{Caucal1993,
author = {Caucal, Didier},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {equivalence; stateless DPDA},
language = {eng},
number = {1},
pages = {23-48},
publisher = {EDP-Sciences},
title = {A fast algorithm to decide on the equivalence of stateless DPDA},
url = {http://eudml.org/doc/92436},
volume = {27},
year = {1993},
}

TY - JOUR
AU - Caucal, Didier
TI - A fast algorithm to decide on the equivalence of stateless DPDA
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1993
PB - EDP-Sciences
VL - 27
IS - 1
SP - 23
EP - 48
LA - eng
KW - equivalence; stateless DPDA
UR - http://eudml.org/doc/92436
ER -

References

top
  1. 1. D. CAUCAL, Décidabilité de l'égalité des langages algébriques infinitaires simples, L.N.CS., Vol. 210, 1986, pp. 37-48. Zbl0595.68072MR827723
  2. 2. D. CAUCAL, A Fast Algorithm to Decide on Simple Grammars Equivalence, L.N.C.S., Vol. 401 1989, pp. 66-85. Zbl0704.68072MR1048156
  3. 3. B. COURCELLE, An Axiomatic Approach to the KH Algorithms, Math. Systems Theory, Vol. 16, 1983, pp. 191-231. Zbl0581.68032MR702448
  4. 4. B. COURCELLE and J. VUILLEMIN, Completeness Result for the Equivalence of Recursive Schemes, J.C.S.S., Vol. 12, 1976, pp. 179-197. Zbl0342.68008MR411225
  5. 5. M. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, 1978. Zbl0411.68058MR526397
  6. 6. M. HARRISON, I. HAVEL and A. YEDUHAÏ, On Equivalence of Grammars Through Transformation Trees, T.C.S.,Vol. 9, 1979, pp. 191-231. Zbl0409.68041MR540555
  7. 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. 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. Zbl0358.68118MR461996
  9. 9. M. OYAMAGUCHI and N. HONDA, The Decidability of Equivalence for Deterministic Stateless Pushdown Automata, Information and Control, Vol. 38, 1978, pp. 367-376. Zbl0393.68078MR509559
  10. 10. E. TOMITA, An Extended Direct Branching Algorithm for Checking Equivalence of Deterministic Pushdown Automata, T.C.S., Vol. 32, 1984, pp. 87-120 Zbl0552.68065MR761163
  11. 11. L. VALIANT, The Equivalence Problem for Deterministic Finite-Turn Pushdown Automata, Information and Control, Vol. 25, 1974, pp. 123-153. Zbl0285.68025MR391591
  12. 12. L. VALIANT and M. PATERSON, Deterministic One-Counter Automata, J.C.S.S., Vol. 10, 1975, pp. 340-350. Zbl0307.68038MR379149

NotesEmbed ?

top

You must be logged in to post comments.