Publication result detail

Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement

MASOPUST, T.; MEDUNA, A.

Original Title

Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement

English Title

Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement

Type

Paper in proceedings outside WoS and Scopus

Original Abstract

Recently, it has been shown that every recursively enumerable language can be generated by a scattered context grammar with no more than three nonterminals. However, in that construction, the maximal number of nonterminals simultaneously rewritten during a derivation step depends on many factors, such as the cardinality of the alphabet of the generated language and the structure of the generated language itself. This paper improves the result by showing that the maximal number of nonterminals rewritten during any derivation step can be limited by a small constant regardless of other factors.

English abstract

Recently, it has been shown that every recursively enumerable language can be generated by a scattered context grammar with no more than three nonterminals. However, in that construction, the maximal number of nonterminals simultaneously rewritten during a derivation step depends on many factors, such as the cardinality of the alphabet of the generated language and the structure of the generated language itself. This paper improves the result by showing that the maximal number of nonterminals rewritten during any derivation step can be limited by a small constant regardless of other factors.

Keywords

Scattered context grammars, descriptional complexity, generative power

Key words in English

Scattered context grammars, descriptional complexity, generative power

Authors

MASOPUST, T.; MEDUNA, A.

RIV year

2010

Released

06.07.2009

Publisher

Otto-von-Guericke-University of Magdeburg

Location

Magdeburg

ISBN

978-3-940961-31-0

Book

Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems

Pages from

235

Pages to

245

Pages count

11

URL

http://cgi.cse.unsw.edu.au/~rvg/eptcs/content.cgi?DCFS2009

BibTex

@inproceedings{BUT33782,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement",
  booktitle="Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems",
  year="2009",
  pages="235--245",
  publisher="Otto-von-Guericke-University of Magdeburg",
  address="Magdeburg",
  isbn="978-3-940961-31-0",
  url="http://cgi.cse.unsw.edu.au/~rvg/eptcs/content.cgi?DCFS2009"
}