Result 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.

Type

journal article

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc.

Abstract

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

Keywords

descriptional complexity, cattered context grammars, recursively enumerable languages

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"
}

Projects

Optimally Integrated Models of Modern Information Technologies, GACR, Standardní projekty, GA201/04/0441, start: 2004-01-01, end: 2006-12-31, completed

Departments

Faculty of Information Technology (FIT)