Summary
The Hotz group H(G) and the Hotz monoid M(G) of an arbitrary grammar G=(V, X, P, S) are defined by H(G)=F(V∪X)/P and M(G) =(V∪X)*/P respectively. A language L⊂X* is called a language with Hotz isomorphism if there exists a grammar G with L=L(G) such that the natural homomorphism F(X)/L→H(G) is an isomorphism. The main result of this paper states that homomorphic images of sentential form languages are languages with Hotz isomorphism. This is a generalization of a result of Frougny, Sakarovitch, and Valkema on context-free languages.
Hotz groups are used to obtain lower bounds for the number of productions which are needed to generate a language. Further it is shown that there are languages with Hotz isomorphism without being a homomorphic image of a sentential form language, and there are context-sensitive languages without Hotz isomorphism. The theory of Hotz monoids is used to get some results on languages generated by grammars with a symmetric set of rules.
Similar content being viewed by others
References
Adjan, I.: Defining relations and algorithmic problems for groups and semi groups. Proc. Steklov Institute Math. 85 (1966) (Amer. Transl. (1967))
Baumslag, G.: Finitely presented metabelian groups. Lect. Notes Comput. Sci. 372, 65–75 (1974)
Berstel, J.: Congruences plus parfaites et languages alg��brique. Séminaire d'Information Théorique, Institut de Programmation, pp. 123–147 (1976–77)
Boasson, L.: Dérivations et reduction dans les grammaires algébriques. Proc. of the 7th ICALP. Lect. Notes Comput. Sci. 85, 109–118 (1980)
Clifford, A., Preston, G.: The algebraic theory of semi-groups. Am. Math. Soc. I (1961), II (1967)
Diekert, V.: On Hotz-groups and homomorphic images of sentential form languages. STACS 85. Lect. Notes Comput. Sci. 182, 87–97 (1985)
Frougny, C.: Grammaires algébriques et monoides simplifiables. RAIRO 18, 225–239 (1984)
Frougny, C., Sakarovitch, J., Valkema, E.: On the Hotz-group of a context-free grammar. Acta Inf. 18, 109–115 (1982)
Hotz, G.: Eine neue Invariante für kontext-freie Sprachen. Theor. Comput. Sci. 11, 107–116 (1980)
Hotz, G.: Verschränkte Homomorphismen formaler Sprachen. RAIRO 14, 193–208 (1980)
Huppert, B.: Endliche Gruppen I, Grundlehren der Mathematik 134. Berlin-Heidelberg-New York: Springer 1967
Jantzen, M.: Thue systems and the Church-Rosser property. MFCS Prag 1984. Lect. Notes Comput. Sci. 176, 80–95 (1984)
Jantzen, M., Kudlek, M.: Homomorphic images of sentential form languages defined by semi-Thue systems. Theor. Comput. Sci. 33, 13–43 (1984)
Serre, J.P.: Cohomologie galosienne. Lect. Notes Math. 5 (1965)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Diekert, V. Investigations on Hotz groups for arbitrary grammars. Acta Informatica 22, 679–698 (1986). https://doi.org/10.1007/BF00263651
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00263651