Detail výsledku

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.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D., FIT (FIT), UIFS (FIT)
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

Rok
2006
Strany
105–112
Sborník
Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)
Konference
2nd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science -- MEMICS'06
ISBN
80-214-3287-X
Vydavatel
Faculty of Information Technology BUT
Místo
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"
}
Projekty
Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů, GAČR, Doktorské granty, GD102/05/H050, zahájení: 2005-01-01, ukončení: 2008-12-31, ukončen
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru