Detail publikačního výsledku

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

Anglický název

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

Druh

Stať ve sborníku mimo WoS a Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

MASOPUST, T.

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