Publication Details

Syntactic Complexity of Scattered Context Grammars

MEDUNA Alexander. Syntactic Complexity of Scattered Context Grammars. Acta Informatica, vol. 1995, no. 32, pp. 285-298. ISSN 0001-5903.
Czech title
Sytaktická složitost gramatik s roztroušeným kontextem
Type
journal article
Language
english
Authors
Keywords

syntactic complexity, scattered context grammars, number of nonterminals, recursively enumerable languages,operations

Abstract

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.

Annotation

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.

Published
1995
Pages
285-298
Journal
Acta Informatica, vol. 1995, no. 32, ISSN 0001-5903
Book
Acta Informatica
Publisher
Springer Verlag
Place
Berlin, DE
BibTeX
@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"
}
Back to top