Publication Details

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

MEDUNA Alexander. Four-Nonterminal Scattered Context Grammars Characterize the Family of Recursively Enumerable Languages. International Journal of Computer Mathematics, vol. 1997, no. 63, pp. 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 Alexander, Doc. RNDr., CSc. (DCSE FEECS BUT)
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
Place
London, GB
BibTeX 
@ARTICLE{FITPUB6170,
   author = "Alexander Meduna",
   title = "Four-Nonterminal Scattered Context Grammars Characterize the Family of Recursively Enumerable Languages",
   pages = "67--83",
   booktitle = "International Journal of Computer Mathematics",
   journal = "International Journal of Computer Mathematics",
   volume = 1997,
   number = 63,
   year = 1997,
   location = "London, GB",
   ISSN = "0020-7160",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/6170"
}
Back to top