Publication Details

An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions

MASOPUST, T. An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions. Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006). Mikulov: Faculty of Information Technology BUT, 2006. p. 105-112. ISBN: 80-214-3287-X.
Czech title
Vylepšení popisné složitosti gramatik regulovaných kontextovými podmínkami
Type
conference paper
Language
English
Authors
Masopust Tomáš, doc. RNDr., Ph.D. (CM-SFE)
Keywords

descriptional complexity, generalized forbidding grammar, simple semi-conditional grammar

Abstract

This paper improves some well-known results concerning thedescriptional complexity of grammars regulated by context conditions.Specifically, it proves that every recursively enumerable language isgenerated by a generalized forbidding grammar of degree two with nomore than eight conditional productions and ten nonterminals, or by asimple semi-conditional grammar of degree (2,1) with no more than nineconditional productions and ten nonterminals.

Published
2006
Pages
105–112
Proceedings
Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)
Conference
2nd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science -- MEMICS'06, Mikulov, CZ
ISBN
80-214-3287-X
Publisher
Faculty of Information Technology BUT
Place
Mikulov
BibTeX 
@inproceedings{BUT22301,
  author="Tomáš {Masopust}",
  title="An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions",
  booktitle="Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)",
  year="2006",
  pages="105--112",
  publisher="Faculty of Information Technology BUT",
  address="Mikulov",
  isbn="80-214-3287-X"
}
Back to top