Syntactic complexity of context-free grammars over word monoids

The syntactic complexity of context-free grammars defined over word monoids is investigated. It is demonstrated that every recursively enumerable language can be defined by a ten-nonterminal context-free grammar over a word monoid generated by an alphabet and six words of length two. Open problems a...

Full description

Bibliographic Details
Published in:Acta Informatica, Vol. 33, No. 5 (1996), p. 457-462
Main Author: Meduna, Alexander
Format: electronic Article
Language:English
ISSN:1432-0525
Physical Description:Online-Ressource
DOI:10.1007/s002360050052
Subjects:
QR Code: Show QR Code