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. In 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 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.

Published
2006
Pages
105–112
Proceedings
Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)
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