On the equivalence of compositions of morphisms and inverse morphisms on regular languages
Karhumäki, J. ; Kleijn, H. C. M.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 19 (1985), p. 203-211 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1985-01-01
@article{ITA_1985__19_3_203_0,
     author = {Karhum\"aki, J. and Kleijn, H. C. M.},
     title = {On the equivalence of compositions of morphisms and inverse morphisms on regular languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {19},
     year = {1985},
     pages = {203-211},
     mrnumber = {809756},
     zbl = {0601.68049},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1985__19_3_203_0}
}

Karhumäki, J.; Kleijn, H. C. M. On the equivalence of compositions of morphisms and inverse morphisms on regular languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 19 (1985) pp. 203-211. http://gdmltest.u-ga.fr/item/ITA_1985__19_3_203_0/

1. J. Berstel, Transductions and Context-Free Languages (B. G. Teubner, Stuttgard, 1979). | MR 549481 | Zbl 0424.68040

2. M. Blattner and T. Head, Single-valued a-transducers, J. Comput. System Sci. 15 (1977) 310-327. | MR 462810 | Zbl 0367.94071

3. K. Culik Ii, F. E. Fich and A. Salomaa, A homomorphic characterization of regular languages, Discrete Appl. Math. 4 (1982) 149-152. | MR 677880 | Zbl 0481.68069

4. K. Culik Ii and A. Salomaa, On the decidability of homomorphism equivalence for languages, J. Comput. System Sci. 17 (1978) 163-175. | MR 514269 | Zbl 0389.68042

5. S. Eilenberg, Automata, Languages, and Machines, Vol. A (Academic Press, New York, 1974). | MR 530382 | Zbl 0317.94045

6. T. V. Griffiths, The unsolvability of the equivalence problem for λ-free nondeterministic generalized machines, J. Assoc. Comput. Mach. 15 (1968) 409-413. | MR 235925 | Zbl 0162.02302

7. J. Karhumäki and Y. Maon, A simple undecidable problem : Existential agreement of inverse of two morphisms on a regular language, submitted for publication. | Zbl 0615.68051

8. J. Karhumäki and M. Linna, A note on morphic characterization of languages, Discrete Appl. Math. 5 (1983) 243-246. | MR 683516 | Zbl 0499.68031

9. J. Karhumäki and D. Wood, Inverse morphic equivalence on languages, manuscript (1983). | MR 777801

10. M. Latteux and J. Leguy, On the composition of morphisms and inverse morphisms, Lecture Notes in Computer Science 154 (1983) 420-432. | MR 727673 | Zbl 0523.68067

11. P. Turakainen, On homomorphic characterization of principal semi AFL's without using intersection with regular sets, Inform. Sci. 27 (1982) 141-149. | MR 678037 | Zbl 0506.68063

12. P. Turakainen, A machine-oriented approach to compositions of morphisms and inverse morphisms, EATCS Bull. 20 (1983) 162-166.