Publication detail

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

MASOPUST, T.

Original Title

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

Type

conference paper

Language

English

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

Keywords

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

Authors

MASOPUST, T.

RIV year

2006

Released

27. 10. 2006

Publisher

Faculty of Information Technology BUT

Location

Mikulov

ISBN

80-214-3287-X

Book

Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)

Pages from

105

Pages to

112

Pages count

8

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