Formal models: regulation and reduction

self-regulating automata, descriptional complexity, conditional grammars, scattered context grammars, multisequential grammars, multicontinuous grammars

The subject of this monograph is divided into two parts-regulated and reduced formal models. The first part introduces and studies self-regulating finite and pushdown automata. In essence, these automata regulate the use of their rules by a sequence of rules applied during the previous moves. A special attention is paid to turns defined as moves during which a self-regulating automaton starts a new self-regulating sequence of moves. Based on the number of turns, two infinite hierarchies of language families resulting from two variants of these automata are established (see Sections 4.1.1 and 4.1.2). Section 4.1.1 demonstrates that in case of self-regulating finite automata these hierarchies coincide with the hierarchies resulting from parallel right linear and right linear simple matrix grammars, so the self-regulating finite automata can be viewed as the automaton counterparts to these grammars. Finally, both infinite hierarchies are compared. In addition, Section 4.1.2 discusses some results and open problems concerning self-regulating pushdown automata. The second part studies descriptional complexity of partially parallel grammars (Section 5.1) and grammars regulated by context conditions (Section 5.2) with respect to the number of nonterminals and a special type of productions. Specifically, Chapter 5 proves that every recursively enumerable language is gen erated (i) by a scattered context grammar with no more than four non-context-free productions and four nonterminals, (ii) by a multisequential grammar with no more than two selectors and two nonterminals, (iii) by a multicontinuous grammar with no more than two selectors and three nonterminals, (iv) by a context-conditional grammar of degree (2, 1) with no more than six conditional productions and seven nonterminals, (v) by a simple context-conditional grammar of degree (2, 1) with no more than seven conditional productions and eight nonterminals, (vi) by a generalized forbidding grammar of degree two and index six with no more than ten conditional productions and nine nonterminals, (vii) by a generalized forbidding grammar of degree two and index four with no more than eleven conditional productions and ten nonterminals, (viii) by a generalized forbidding grammar of degree two and index nine with no more than eight conditional productions and ten nonterminals, (ix) by a generalized forbidding grammar of degree two and unlimited index with no more than nine conditional productions and eight nonterminals, (x) by a semi-conditional grammar of degree (2, 1) with no more than seven conditional productions and eight nonterminals, and (xi) by a simple semi-conditional grammar of degree (2, 1) with no more than nine conditional productions and ten nonterminals. Chapter 2 contains basic definitions and the notation used during this monograph. Chapter 3 then summarizes the previous known results related to the studied formal models; regulated automata and descriptional complexity of partially parallel grammars and grammars regulated by context conditions. Chapter 4 studies self-regulating automata, and Chapter 5 presents the new results concerning descriptional complexity of partially parallel grammars and grammars regulated by context conditions.