On the equality sets for homomorphisms on free monoids with two generators

K. Culik II; J. Karhumäki

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

  • Volume: 14, Issue: 4, page 349-369
  • ISSN: 0988-3754

How to cite

top

Culik II, K., and Karhumäki, J.. "On the equality sets for homomorphisms on free monoids with two generators." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 14.4 (1980): 349-369. <http://eudml.org/doc/92131>.

@article{CulikII1980,
author = {Culik II, K., Karhumäki, J.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {periodic homomorphisms on free monoids; equations in free monoids; Post's Correspondence Problem; equality set; periodicity forcing sets},
language = {eng},
number = {4},
pages = {349-369},
publisher = {EDP-Sciences},
title = {On the equality sets for homomorphisms on free monoids with two generators},
url = {http://eudml.org/doc/92131},
volume = {14},
year = {1980},
}

TY - JOUR
AU - Culik II, K.
AU - Karhumäki, J.
TI - On the equality sets for homomorphisms on free monoids with two generators
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1980
PB - EDP-Sciences
VL - 14
IS - 4
SP - 349
EP - 369
LA - eng
KW - periodic homomorphisms on free monoids; equations in free monoids; Post's Correspondence Problem; equality set; periodicity forcing sets
UR - http://eudml.org/doc/92131
ER -

References

top
  1. 1. K. CULIK II, A Purely Homomorphic Characterization of Recurively Enumerable Sets, J. Assoc. Comput. Mach., Vol. 26, 1979, pp. 345-350. Zbl0395.68076MR528036
  2. 2. K. CULIK II, On Homomorphic Characterization of Families of Languages. Proceedings of the Six Inter. Colloquium an Automata, Languages and Programrning, Graz, Austria, pp. 161-170, July 1979. Zbl0412.68064MR573239
  3. 3. K. CULIK II and I. FRIS, The Decidability of the Equivalence Problem for DOL Systems, Inf. and Control, Vol. 35, 1977, pp.20-39. Zbl0365.68074MR449030
  4. 4. K. CULIK II and A. SALOMAA, On the Decidability of Homomorphism Equivalence for Languages, J. Comp. System Sc., Vol. 17, 1978, pp.163-175. Zbl0389.68042MR514269
  5. 5. K. CULIK II and A. SALOMAA, Test Sets and Checking words for Homomorphism Equivalence, J. Comp. System Sc., Vol. 20, 1980, pp. 379-395. Zbl0451.68046MR584866
  6. 6. K. CULIK II and H. A. MAURER, On Simple Representations of Language Families, R.A.I.R.O., Informatique théorique/Theoretical Informatics, Vol. 13, No. 3, 1979, pp. 241-250. Zbl0432.68052MR554685
  7. 7. A. EHRENFEUCHT and G. ROZENBERG, Elementary Homomorphisms and a Solution to the DOL Sequence Equivalence Problem, Theoretical Computer Science, Vol. 7, 1978, pp. 169-183. Zbl0407.68085MR509015
  8. 8. J. ENGELFRIET and G. ROZENBERG, Equality Languages and Fixed Point Languages, Inf. and Control, Vol. 43, 1979, pp. 20-49. Zbl0422.68034MR549263
  9. 9. J. KARHUMAKI and I. SIMON, A Note on Elementary Homomorphisms and the Regularity of Equality Sets, Bulletin E.A.T.C.S., No, 9, October 1979, pp. 16-24, 
  10. 10. R. C. LYNDON and M. P. SCHUTZENBERGER, The Equation aM=bN cP in a Free Group, Michigan Math. J., Vol.9, 1962, pp. 289-298. Zbl0106.02204MR162838
  11. 11. G. S. MAKANIN, The Problem of Solvability of Equations in a Free Semigroup (in Russian), Matematiceskij Sbornik, Vol. 103, No. 145, 1977, pp. 148-236. Zbl0371.20047MR470107
  12. 12. A. SALOMAA, Equality Sets for Homomorphisms of Free Monoids, Acta Cybernetica, Vol. 4, 1978, pp.127-139. Zbl0407.68077MR521458
  13. 13. A. SALOMAA, DOL Equivalence: The Problem of Iterated Morphisms, Bulletin E.A.T.C.S., No. 4, January 1978, pp. 5-12 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.