Detail publikačního výsledku

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

MASOPUST, T.; MEDUNA, A.

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

Druh

Stať ve sborníku mimo WoS a Scopus

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.

Klíčová slova

Scattered context grammars, descriptional complexity, generative power

Klíčová slova v angličtině

Scattered context grammars, descriptional complexity, generative power

Autoři

MASOPUST, T.; MEDUNA, A.

Rok RIV

2010

Vydáno

06.07.2009

Nakladatel

Otto-von-Guericke-University of Magdeburg

Místo

Magdeburg

ISBN

978-3-940961-31-0

Kniha

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

Strany od

235

Strany do

245

Strany počet

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"
}