Publication Details

Generative Power of Three-Nonterminal Scattered Context Grammars

MEDUNA, A. Generative Power of Three-Nonterminal Scattered Context Grammars. Theoretical Computer Science, 2000, vol. 2000, no. 246, p. 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 Alexandr, prof. RNDr., CSc. (DIFS)

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

unknown

Place

Amsterdam

BibTeX

@article{BUT191792,
  author="Alexandr {Meduna}",
  title="Generative Power of Three-Nonterminal Scattered Context Grammars",
  journal="Theoretical Computer Science",
  year="2000",
  volume="2000",
  number="246",
  pages="279--284",
  issn="0304-3975"
}