Publication Details

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

MASOPUST, T.; MEDUNA, A. Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement. Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems. Magdeburg: Otto-von-Guericke-University of Magdeburg, 2009. p. 235-245. ISBN: 978-3-940961-31-0.
Czech title
Popicná složitost gramatik s rozptýleným kontextem se třemi neterminály: vylepšení
Type
conference paper
Language
English
Authors
Masopust Tomáš, doc. RNDr., Ph.D. (CM-SFE)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
URL
Keywords

Scattered context grammars, descriptional complexity, generative power

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.

Published
2009
Pages
235–245
Proceedings
Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems
ISBN
978-3-940961-31-0
Publisher
Otto-von-Guericke-University of Magdeburg
Place
Magdeburg
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"
}
Back to top