Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{835059,
author = {Masopust, Tomáš and Meduna, Alexander},
address = {Magdeburg},
booktitle = {Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems},
keywords = {Scattered context grammars, descriptional complexity, generative power},
language = {eng},
location = {Magdeburg},
isbn = {978-3-940961-31-0},
pages = {235-245},
publisher = {Otto-von-Guericke-Universität Magdeburg, Germany},
title = {Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement},
year = {2009}
}
TY - JOUR
ID - 835059
AU - Masopust, Tomáš - Meduna, Alexander
PY - 2009
TI - Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
PB - Otto-von-Guericke-Universität Magdeburg, Germany
CY - Magdeburg
SN - 9783940961310
KW - Scattered context grammars, descriptional complexity, generative power
N2 - 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.
ER -
MASOPUST, Tomáš a Alexander MEDUNA. Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement. In \textit{Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems}. Magdeburg: Otto-von-Guericke-Universität Magdeburg, Germany, 2009, s.~235-245. ISBN~978-3-940961-31-0.
|
