Detail publikace

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

MASOPUST, T.

Originální název

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

Typ

článek ve sborníku mimo WoS a Scopus

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

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

Autoři

MASOPUST, T.

Rok RIV

2006

Vydáno

27. 10. 2006

Nakladatel

Faculty of Information Technology BUT

Místo

Mikulov

ISBN

80-214-3287-X

Kniha

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

Strany od

105

Strany do

112

Strany počet

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