Context-free grammars with cancellation properties (Q1080662)

Let F(X) be the free group generated by a set X and \(X^*\) be the free monoid generated by X. If \(Q\subseteq X^*\times X^*\), then [Q] denotes the congruence of \(X^*\) generated by elements of Q and \(<Q>\) denotes the congruence of F(X) generated by the elements of Q. Given a grammar \(G=(X,V,P,S),\) the Hotz group of it is \(H(G)=F(X\cup V)/<P>\) and the Hotz monoid of it is \(M(G)=(X\cup V)^*/[P]\) [see \textit{G. Hotz}, Theor. Comput. Sci. 11, 107-116 (1980; Zbl 0447.68089); \textit{G. Hotz}, RAIRO Inf. Théor. 13, 337-345 (1979; Zbl 0428.68085); \textit{Ch. Frougny}, \textit{J. Sakarovitch} and \textit{E. Valkema}, Acta Inf. 18, 109- 115 (1982; Zbl 0495.68066)]. The paper continues the study of Hotz groups and monoids associated to context-free grammars. Results: one characterizes the syntactic monoid of the language \(L_ R\) of all words equal to the axiom in M(G), one defines two types of grammars (2-sided very-simple and bi-very-simple) which have cancellative Hotz monoids, one proves that the not-derivation- bounded bi-very-simple grammars generate generators of the faimly of context-free languages and so on.