BACK to VOLUME 30 NO.2

Kybernetika 30(2):177-186, 1994.

Syntactic Complexity of Regulated Rewriting

Alexander Meduna, Cynthia J. Crooks and Milan Šárek


Abstract:

The syntactic complexity of regulated grammars with respect to the number of nonterminals is investigated. Several characterizations of the family of recursively enumerable languages are established; most importantly, it is proved that this family is defined by programmed grammars with only seven nonterminals.


Keywords:


AMS:


download full-text.pdf
download abstract.pdf

BIB TeX

@article{kyb:1994:2:177-186,

author = {Meduna, Alexander and Crooks, Cynthia J. and \v{S}\'{a}rek, Milan},

title = {Syntactic Complexity of Regulated Rewriting},

journal = {Kybernetika},

volume = {30},

year = {1994},

number = {2},

pages = {177-186}

publisher = {{\'U}TIA, AV {\v C}R, Prague },

}


BACK to VOLUME 30 NO.2