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
Language:English
ISSN:1432-0525
Physical Description:Online-Ressource
DOI:10.1007/BF01178263
Subjects:
QR Code: Show QR Code