×

zbMATH — the first resource for mathematics

Matrix grammars. (Gramatici matriciale). (Romanian. English summary) Zbl 0618.68059
Bucureşti: Editura Ştiinţifică şi Enciclopedică. 261 p.; Lei 12.50 (1981).
In the present book, a very important and mathematically interesting topic in formal language theory is presented, namely, the matrix restriction in the derivation of Chomsky grammars. This restriction considerably increases the generative capacity of context-free grammars. Thus the matrix grammars are used in many applications of formal language theory when noncontext-free languages occur and the use of context- sensitive grammars can be avoided.
The book consists of two parts. Part one is a monograph devoted to the mathematical theoretic study of matrix grammars and languages. Almost all the known results in this area are presented together with many open problems and conjectures of interest.
The second part presents some applications which involve noncontext-free languages and naturally request the use of matrix grammars of various types.
Many results are original and some of them were published elsewhere. The large bibliography presented at the end of the book includes referenced papers but also many unreferenced articles about other types of grammars with restrictions in derivation.

MSC:
68Q45 Formal languages and automata
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science