Syntactic complexity of scattered context grammars

The syntactic complexity of scattered context grammars with respect to the number of nonterminals is investigated. First, the family of the recursively enumerable languages is characterized by some basic operations, such as quotient and coding, over the languages generated by propagating scattered c...

Full description

Bibliographic Details
Published in:Acta Informatica, Vol. 32, No. 3 (1995), p. 285-298
Main Author: Meduna, Alexander
Format: electronic Article
Physical Description:Online-Ressource
QR Code: Show QR Code