Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{799991,
author = {Masopust, Tomáš},
address = {Mikulov},
booktitle = {Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)},
keywords = {descriptional complexity; generalized forbidding grammar; simple semi-conditional grammar},
location = {Mikulov},
isbn = {80-214-3287-X},
pages = {105-112},
publisher = {FIT VUT Brno},
title = {An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions},
year = {2006}
}
TY - JOUR
ID - 799991
AU - Masopust, Tomáš
PY - 2006
TI - An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions
PB - FIT VUT Brno
CY - Mikulov
SN - 802143287X
KW - descriptional complexity
KW - generalized forbidding grammar
KW - simple semi-conditional grammar
N2 - This paper improves some well-known results concerning the descriptional complexity of grammars regulated by context conditions. Specifically, it proves that every recursively enumerable language is generated by a generalized forbidding grammar of degree two with no more than eight conditional productions and ten nonterminals, or by a simple semi-conditional grammar of degree (2,1) with no more than nine conditional productions and ten nonterminals.
ER -
MASOPUST, Tomáš. An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions. In \textit{Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)}. Mikulov: FIT VUT Brno, 2006, s.~105-112. ISBN~80-214-3287-X.
|
