Complexity classes of g-systems are AFL. (English) Zbl 0639.68064

Rovan, Branislav

Acta Math. Univ. Comenianae 48-49, 283-297 (1986).

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.

MSC:

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

Keywords:

generative system; complexity classes of g-systems; abstract family of languages