Investigations on Hotz groups for arbitrary grammars
type: Item
instance of: scholarly article
title: Investigations on Hotz groups for arbitrary grammars
zbMATH Open document ID: 0612.68067
DOI: 10.1007/BF00263651
author: Volker Diekert
published in: Acta Informatica
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3990894
zbMATH Keywords: Hotz group
zbMATH Keywords: Hotz monoid
zbMATH Keywords: language with Hotz isomorphism
zbMATH Keywords: homomorphic images of sentential form languages
zbMATH Keywords: context-sensitive languages
zbMATH Keywords: grammars with a symmetric set of rules
MaRDI profile type: Publication
cites work: Q4059649
cites work: Q3848243
cites work: Q3700852
cites work: Q3335013
cites work: On the Hotz group of a context-free grammar
cites work: Eine neue Invariante für kontextfreie Sprachen
cites work: Q3885224
cites work: Endliche Gruppen I
cites work: Q3346296
cites work: Homomorphic images of sentential form languages defined by semi-Thue systems
description: scientific article; zbMATH DE number 3990894