Nonterminal complexity of one-sided random context grammars

In the present paper, we study the nonterminal complexity of one-sided random context grammars. More specifically, we prove that every recursively enumerable language can be generated by a one-sided random context grammar with no more than ten nonterminals. An analogical result holds for thirteen no...

Full description

Bibliographic Details
Published in:Acta Informatica, Vol. 49, No. 2 (2012), p. 55-68
Main Author: Meduna, Alexander
Other Involved Persons: Zemek, Petr
Format: electronic Article
Language:English
ISSN:1432-0525
Physical Description:Online-Ressource
DOI:10.1007/s00236-012-0150-6
Subjects:
QR Code: Show QR Code