Syntactic Complexity of Scattered Context Grammars

Czech title

Sytaktická složitost gramatik s roztroušeným kontextem

Type

journal article

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)

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

BibTeX

@article{BUT191806,
  author="Alexandr {Meduna}",
  title="Syntactic Complexity of Scattered Context Grammars",
  journal="Acta Informatica",
  year="1995",
  volume="1995",
  number="32",
  pages="285--298",
  issn="0001-5903"
}