Detail publikace

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

MASOPUST Tomáš. 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: Fakulta informačních technologií VUT v Brně, 2006, s. 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
angličtina
Autoři
Masopust Tomáš, RNDr., Ph.D. (UIFS FIT VUT)
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)
Konference
2nd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science -- MEMICS'06, Mikulov, CZ
ISBN
80-214-3287-X
Vydavatel
Fakulta informačních technologií VUT v Brně
Místo
Mikulov, CZ
BibTeX 
@INPROCEEDINGS{FITPUB8194,
   author = "Tom\'{a}\v{s} Masopust",
   title = "An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions",
   pages = "105--112",
   booktitle = "Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)",
   year = 2006,
   location = "Mikulov, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "80-214-3287-X",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8194"
}
Nahoru