Descriptional complexity of semi-conditional grammars
From International Center for Computational Logic
Descriptional complexity of semi-conditional grammars
Tomáš MasopustTomáš Masopust, Alexander MedunaAlexander Meduna
Tomáš Masopust, Alexander Meduna
Descriptional complexity of semi-conditional grammars
Information Processing Letters, 104(1):29-31, 2007
Descriptional complexity of semi-conditional grammars
Information Processing Letters, 104(1):29-31, 2007
- KurzfassungAbstract
The descriptional complexity of semi-conditional grammars is studied. It is proved that every recursively enumerable language is generated by a semi-conditional grammar of degree (2,1) with no more than seven conditional productions and eight nonterminals. - Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems
@article{MM2007,
author = {Tom{\'{a}}{\v{s}} Masopust and Alexander Meduna},
title = {Descriptional complexity of semi-conditional grammars},
journal = {Information Processing Letters},
volume = {104},
number = {1},
year = {2007},
pages = {29-31},
doi = {10.1016/j.ipl.2007.05.002}
}