Detail publikace

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. In 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.
Název česky
Vylepšení popisné složitosti gramatik regulovaných kontextovými podmínkami
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
Klíčová slova

popisná složitost, zobecněná zakazující gramatika, prostá polopodmínková gramatika

Abstrakt

V článeku jsou vylepšeny dva výsledky týkající se popisné složitosti gramatik regulovaných kontextovými podmínkami. Konkrétněji, je ukázáno, že každý rekurzívně spočetný jazyk je generován zobecněnou zakazující gramatikou stupně dva s nejvýše osmi podmínkovými pravidly a deseti neterminály, nebo prostou polopodmínkovou gramatikou stupně (2,1) s nejvýše devíti podmínkovými pravidly a deseti neterminály.

Rok
2006
Strany
105–112
Sborník
Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)
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"
}
Nahoru