Regulated Formal Models and Their Reduction

Regulated Formal Models and Their Reduction

Dissertation

This thesis is divided into two parts. The first part introduces and studies self-regulating 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 selfregulating 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. It 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, as an open problem area, it suggests the discussion of self-regulating pushdown automata.

The second part studies the descriptional complexity of partially parallel grammars and grammars regulated by context conditions with respect to the number of nonterminals and a special type of productions. Specifically, it proves that every recursively enumerable language is generated (1) by a scattered context grammar with no more than four non-context-free productions and four nonterminals, (2) by a multisequential grammar with no more than two selectors and two nonterminals, (3) by a multicontinuous grammar with no more than two selectors and three nonterminals, (4) by a context-conditional grammar of degree (2,1) with no more than six conditional productions and seven nonterminals, (5) by a simple context-conditional grammar of degree (2,1) with no more than seven conditional productions and eight nonterminals, (6) by a generalized forbidding grammar of degree two and index six with no more than ten conditional productions and nine nonterminals, (7) by a generalized forbidding grammar of degree two and index four with no more than eleven conditional productions and ten nonterminals, (8) by a generalized forbidding grammar of degree two and index nine with no more than eight conditional productions and ten nonterminals, (9) by a generalized forbidding grammar of degree two and unlimited index with no more than nine conditional productions and eight nonterminals, (10) by a semi-conditional grammar of degree (2,1) with no more than seven conditional productions and eight nonterminals, and (11) by a simple semi-conditional grammar of degree (2,1) with no more than nine conditional productions and ten nonterminals.

This thesis is divided into two parts. The first part introduces and studies self-regulating 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 selfregulating 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. It 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, as an open problem area, it suggests the discussion of self-regulating pushdown automata.

The second part studies the descriptional complexity of partially parallel grammars and grammars regulated by context conditions with respect to the number of nonterminals and a special type of productions. Specifically, it proves that every recursively enumerable language is generated (1) by a scattered context grammar with no more than four non-context-free productions and four nonterminals, (2) by a multisequential grammar with no more than two selectors and two nonterminals, (3) by a multicontinuous grammar with no more than two selectors and three nonterminals, (4) by a context-conditional grammar of degree (2,1) with no more than six conditional productions and seven nonterminals, (5) by a simple context-conditional grammar of degree (2,1) with no more than seven conditional productions and eight nonterminals, (6) by a generalized forbidding grammar of degree two and index six with no more than ten conditional productions and nine nonterminals, (7) by a generalized forbidding grammar of degree two and index four with no more than eleven conditional productions and ten nonterminals, (8) by a generalized forbidding grammar of degree two and index nine with no more than eight conditional productions and ten nonterminals, (9) by a generalized forbidding grammar of degree two and unlimited index with no more than nine conditional productions and eight nonterminals, (10) by a semi-conditional grammar of degree (2,1) with no more than seven conditional productions and eight nonterminals, and (11) by a simple semi-conditional grammar of degree (2,1) with no more than nine conditional productions and ten nonterminals.

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

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

MASOPUST, T.

04.10.2007

Brno

71

https://www.fit.vut.cz/research/publication/8488/

Řízené formální modely a jejich redukce