Result Details

Four-Nonterminal Scattered Context Grammars Characterize the Family of Recursively Enumerable Languages

MEDUNA, A. Four-Nonterminal Scattered Context Grammars Characterize the Family of Recursively Enumerable Languages. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1997, vol. 1997, no. 63, p. 67-83. ISSN: 0020-7160.

Type

journal article

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc.

Abstract

The family of recursively enumerable languages is characterized by scattered context grammars with four nonterminals.

Keywords

recursively enumerable languages, scattered context grammars, nonterminals

Annotation

The family of recursively enumerable languages is characterized by scattered context grammars with four nonterminals. Moreover, this family is characterized by scattered context grammars with three nonterminals if these grammars start their derivations from a word rather than a symbol. Three open problem areas are suggested.

Published

1997

Pages

67–83

Journal

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, vol. 1997, no. 63, ISSN 0020-7160

Book

International Journal of Computer Mathematics

Publisher

unknown

Place

London

BibTeX

@article{BUT191803,
  author="Alexandr {Meduna}",
  title="Four-Nonterminal Scattered Context Grammars Characterize the Family of Recursively Enumerable Languages",
  journal="INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS",
  year="1997",
  volume="1997",
  number="63",
  pages="67--83",
  issn="0020-7160"
}

Departments

Faculty of Information Technology (FIT)