BookMASOPUST Tomáš. Formal models: regulation and reduction. Brno: Faculty of Information Technology BUT, 2007. ISBN 9788021435506.  Publication language:  english 

Original title:  Formal Models: Regulation and Reduction 

Title (cs):  Formální modely: řízení a redukce 

Pages:  103 

Place:  Brno, CZ 

Year:  2007 

ISBN:  9788021435506 

Publisher:  Faculty of Information Technology BUT 

Files:  

 Keywords 

selfregulating automata, descriptional complexity, conditional
grammars, scattered context grammars, multisequential grammars,
multicontinuous grammars 
Annotation 

The subject of this monograph is divided into two partsregulated and reduced formal models.
The first part introduces and studies selfregulating 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 selfregulating automaton starts a new selfregulating 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 selfregulating finite automata these hierarchies coincide with the hierarchies resulting from parallel right linear and right linear simple matrix grammars, so the selfregulating 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 selfregulating 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 noncontextfree 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 contextconditional grammar of degree (2, 1) with no more than six conditional productions and seven nonterminals, (v) by a simple contextconditional 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 semiconditional grammar of degree (2, 1) with no more than seven conditional productions and eight nonterminals, and (xi) by a simple semiconditional 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 selfregulating automata, and Chapter 5 presents the new results concerning descriptional complexity of partially parallel grammars and grammars regulated by context conditions.

BibTeX: 

@BOOK{
author = {Tom{\'{a}}{\v{s}} Masopust},
title = {Formal Models: Regulation and Reduction},
pages = {103},
year = {2007},
location = {Brno, CZ},
publisher = {Faculty of Information Technology BUT},
ISBN = {9788021435506},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8553}
} 
