Detail publikace

Formal models: regulation and reduction

Originální název

Formal models: regulation and reduction

Anglický název

Formal models: regulation and reduction

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

BibTex


@book{BUT61770,
  author="Tomáš {Masopust}",
  title="Formal models: regulation and reduction",
  annote="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.",
  address="Faculty of Information Technology BUT",
  chapter="61770",
  howpublished="print",
  institution="Faculty of Information Technology BUT",
  year="2007",
  month="november",
  pages="0--0",
  publisher="Faculty of Information Technology BUT",
  type="book"
}