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