Detail publikace

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

Originální název

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

Anglický název

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

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

BibTex


@inproceedings{BUT33782,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement",
  annote="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.",
  address="Otto-von-Guericke-University of Magdeburg",
  booktitle="Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems",
  chapter="33782",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Otto-von-Guericke-University of Magdeburg",
  year="2009",
  month="july",
  pages="235--245",
  publisher="Otto-von-Guericke-University of Magdeburg",
  type="conference paper"
}