On some variants of the Ehrenfeucht conjecture. (English) Zbl 0617.68067

We will show that some variants of the Ehrenfeucht Conjecture give us algebraic properties which separate the Chomsky classes 1, 2, and 3.


68Q45 Formal languages and automata
Full Text: DOI


[1] Albert, M. H.; Lawrence, J., A proof of Ehrenfeucht’s Conjecture, Theoret. Comput. Sci., 41, 1, 121-123 (1985) · Zbl 0602.68066
[2] Cliffort, A.; Preston, G., (The Algebraic Theory of Semigroups, Vol. II (1967), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 0178.01203
[3] Diekert, V., Investigations on Hotz groups for arbitrary grammars, Acta Inform., 22, 679-698 (1986) · Zbl 0612.68067
[4] Frougny, C.; Sakarovitch, J.; Valkema, E., On the Hotz group of a context-free grammar, Acta Inform., 18, 109-115 (1982) · Zbl 0495.68066
[5] A. Möbus, On languages with Hotz isomorphism, Preprint.; A. Möbus, On languages with Hotz isomorphism, Preprint.
[6] Muller, D. E.; Schupp, P. E., Groups, the theory of ends and context-free languages, J. Comput. System Sci., 26, 295-310 (1983) · Zbl 0537.20011
[7] Lyndon, R. E.; Schupp, P. E., Combinatorial Group Theory (1977), Springer: Springer Berlin · Zbl 0368.20023
[8] Restivo, A.; Reutenauer, C., On cancellation properties of languages which are supports of rational power series, J. Comput. System Sci., 29, 153-159 (1984) · Zbl 0578.68061
[9] Perrin, D., On the solution of Ehrenfeucht’s Conjecture, EATCS-Bull., 27, 68-69 (1985)
[10] Serre, J. P., Trees (1980), Springer: Springer Berlin · Zbl 0548.20018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.