Publication Details

Generative Power of Three-Nonterminal Scattered Context Grammars

MEDUNA Alexander. Generative Power of Three-Nonterminal Scattered Context Grammars. Theoretical Computer Science, vol. 2000, no. 246, pp. 279-284. ISSN 0304-3975.

Czech title

Generativní síla tříneterminálních gramatik s rozptýleným kontextem

Type

journal article

Language

english

Authors

Meduna Alexander, Doc. RNDr., CSc. (DCSE FEECS BUT)

Keywords

descriptional complexity, cattered context grammars, recursively enumerable languages

Abstract

Generative power of three-nonterminal scattered context grammars is discussed.

Annotation

This paper discusses the descriptional complexity of scattered context grammars with respect to the number of nonterminals. It proves that the three-nonterminal scattered context grammars characterize the family of recursively enumerable languages.

Published

2000

Pages

279-284

Journal

Theoretical Computer Science, vol. 2000, no. 246, ISSN 0304-3975

Book

Theoretical Computer Science

Publisher

Elsevier Science

Place

Amsterdam, NL

BibTeX

@ARTICLE{FITPUB6182,
   author = "Alexander Meduna",
   title = "Generative Power of Three-Nonterminal Scattered Context Grammars",
   pages = "279--284",
   booktitle = "Theoretical Computer Science",
   journal = "Theoretical Computer Science",
   volume = 2000,
   number = 246,
   year = 2000,
   location = "Amsterdam, NL",
   ISSN = "0304-3975",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/6182"
}