Informace o publikaci
An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions
| Název česky | Vylepšení popisné složitosti gramatik regulovaných kontextovými podmínkami |
|---|---|
| Autoři | |
| Rok publikování | 2006 |
| Druh | Článek ve sborníku |
| Konference | Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Klíčová slova | descriptional complexity; generalized forbidding grammar; simple semi-conditional grammar |
| Popis | 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. |