zbMATH — the first resource for mathematics

Complexity classes of g-systems are AFL. (English) Zbl 0639.68064
Summary: The notion of a generative system (g-system) was introduced in the author’s article [(*) Lect. Notes Comput. Sci. 118, 473-482 (1981; Zbl 0491.68076)] in an attempt to facilitate a unified approach to various types of rewriting systems studied in the literature. The complexity of language descriptions by sequential and parallel grammars was studied there. An important question arising in the complexity theory is the study of complexity classes. In the present paper we shall consider the complexity classes of g-systems. We shall show that each complexity class for the measure STATE (the number of states of the a-transducer of the g- system in normal form) is an abstract family of languages.
The paper consists of two sections. The first section briefly reviews the main notions studied. The results are presented in the second section. The reader is referred to (*) for further background and motivation concerning g-systems.

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity