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

Czech title

Gramatiky s roztroušeným kontextem obsahující čtyři neterminály charakterizující třídu rekurzivně spočetných jazyků

Type

journal article

Language

English

Authors

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

Keywords

recursively enumerable languages, scattered context grammars, nonterminals

Abstract

The family of recursively enumerable languages is characterized by scattered context grammars with four 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"
}