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
Physical Description:Online-Ressource
QR Code: Show QR Code