×

Investigations on Hotz groups for arbitrary grammars. (English) Zbl 0612.68067

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\cup X)/P\) and \(M(G)=(V\cup X)^*/P\) respectively. A language \(L\subset 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\(\to H(G)\) is an isomorphism. The main result 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.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adjan, I.: Defining relations and algorithmic problems for groups and semi groups. Proc. Steklov Institute Math. 85 (1966) (Amer. Transl. (1967))
[2] Baumslag, G.: Finitely presented metabelian groups. Lect. Notes Comput. Sci. 372, 65-75 (1974) · Zbl 0304.20015
[3] Berstel, J.: Congruences plus parfaites et languages alg?brique. S?minaire d’Information Th?orique, Institut de Programmation, pp. 123-147 (1976-77)
[4] Boasson, L.: D?rivations et reduction dans les grammaires alg?briques. Proc. of the 7th ICALP. Lect. Notes Comput. Sci. 85, 109-118 (1980)
[5] Clifford, A., Preston, G.: The algebraic theory of semi-groups. Am. Math. Soc. I (1961), II (1967) · Zbl 0111.03403
[6] Diekert, V.: On Hotz-groups and homomorphic images of sentential form languages. STACS 85. Lect. Notes Comput. Sci. 182, 87-97 (1985) · Zbl 0578.68055 · doi:10.1007/BFb0023998
[7] Frougny, C.: Grammaires alg?briques et monoides simplifiables. RAIRO 18, 225-239 (1984) · Zbl 0545.68071
[8] Frougny, C., Sakarovitch, J., Valkema, E.: On the Hotz-group of a context-free grammar. Acta Inf. 18, 109-115 (1982) · Zbl 0495.68066 · doi:10.1007/BF00625283
[9] Hotz, G.: Eine neue Invariante f?r kontext-freie Sprachen. Theor. Comput. Sci. 11, 107-116 (1980) · Zbl 0447.68089 · doi:10.1016/0304-3975(80)90040-7
[10] Hotz, G.: Verschr?nkte Homomorphismen formaler Sprachen. RAIRO 14, 193-208 (1980) · Zbl 0442.68080
[11] Huppert, B.: Endliche Gruppen I, Grundlehren der Mathematik 134. Berlin-Heidelberg-New York: Springer 1967 · Zbl 0217.07201
[12] Jantzen, M.: Thue systems and the Church-Rosser property. MFCS Prag 1984. Lect. Notes Comput. Sci. 176, 80-95 (1984) · Zbl 0553.03025 · doi:10.1007/BFb0030291
[13] Jantzen, M., Kudlek, M.: Homomorphic images of sentential form languages defined by semi-Thue systems. Theor. Comput. Sci. 33, 13-43 (1984) · Zbl 0542.68059 · doi:10.1016/0304-3975(84)90101-4
[14] Serre, J.P.: Cohomologie galosienne. Lect. Notes Math. 5 (1965)
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.