Publication Details
Syntactic Complexity of Scattered Context Grammars
syntactic complexity, scattered context grammars, number of nonterminals, recursively enumerable languages,operations
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 context grammars with four nonterminals.
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 context grammars with four nonterminals. Then, a new method of achieving the characterization of the family of recursively enumerable languages by scattered context grammars with only five nonterminals and a single erasing production. Finally, it is demonstrated that the number of nonterminals can be decreased by one in the present characterizations if scattered context grammars start their derivations from a word rather than a single symbol.
@ARTICLE{FITPUB6167,
author = "Alexander Meduna",
title = "Syntactic Complexity of Scattered Context Grammars",
pages = "285--298",
booktitle = "Acta Informatica",
journal = "Acta Informatica",
volume = 1995,
number = 32,
year = 1995,
location = "Berlin, DE",
publisher = "Springer Verlag",
ISSN = "0001-5903",
language = "english",
url = "https://www.fit.vut.cz/research/publication/6167"
}