The decidability of the equivalence problem for polynomially bounded DOL sequences
Karhumäki, Juhani
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977), p. 17-28 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1977-01-01
@article{ITA_1977__11_1_17_0,
     author = {Karhum\"aki, Juhani},
     title = {The decidability of the equivalence problem for polynomially bounded DOL sequences},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {11},
     year = {1977},
     pages = {17-28},
     mrnumber = {464724},
     zbl = {0359.68086},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1977__11_1_17_0}
}

Karhumäki, Juhani. The decidability of the equivalence problem for polynomially bounded DOL sequences. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977) pp. 17-28. http://gdmltest.u-ga.fr/item/ITA_1977__11_1_17_0/

1. K. Culik , II, On the Decidability of the Sequence Equivalence Problem for DOL-Systems, Manuscript, 1975. | MR 495228

2. A. Ehrenfeucht and G. Rozenberg, DOL-Systems with Rank, Lecture Notes in Computer Science, Springer, Vol. 15, 1974, pp. 136-141. | MR 428816 | Zbl 0293.68063

3. S. Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York, 1966. | MR 211815 | Zbl 0184.28401

4. G. Herman and G. Rozenberg, Developmental Systems and Languages, North-Holland, Amsterdam, 1975. | MR 495247 | Zbl 0306.68045

5. K. P. Lee and G. Rozenberg, The Length Sets of DOL Languages Are Uniformely Bounded, Information Processing Letters, Vol. 2, 1974, pp. 185-188. | MR 431803 | Zbl 0282.68037

6. M. Nielsen, On the Decidability of Some Equivalence Problems For DOL-Systems, Information and Control, Vol. 25, 1974, pp. 166-193. | MR 345455 | Zbl 0284.68065

7. Problem book. Unusual Automata Theory, January 1972, Dept. of Computer Science, Univ. of Aarhus, Tech. Report DAIMI PB-15, 1973, pp. 14-26.

8. G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems, in J. T. Tou (éd.), Advances in Information Systems Science, Plenum Press, New York, Vol. 6, 1976, pp. 161-206. | MR 471464 | Zbl 0365.68072

9. L. G. Valiant, The Equivalence Problem for DOL Systems and its Decidability for Binary Alphabets, Manuscript, 1975.