Publication Details

Six-Nonterminal Multi-Sequential Grammars Characterize the Family of Recursively Enumerable Languages

MEDUNA Alexander. Six-Nonterminal Multi-Sequential Grammars Characterize the Family of Recursively Enumerable Languages. International Journal of Computer Mathematics, vol. 1997, no. 65, pp. 179-189. ISSN 0020-7160.
Czech title
Multisekvenční gramatiky se šesti neterminály charekterizují třídu rekurzivně vyčíslitelných jazyků
Type
journal article
Language
english
Authors
Meduna Alexander, Doc. RNDr., CSc. (DCSE FEECS BUT)
Keywords

descriptional complexity, multi-sequential grammars, recursively enumerable languages, nonterminals

Abstract

The present paper investigates the descriptional complexity of multi-sequential grammars with respect to the number of nonterminals.

Annotation

The present paper investigates the descriptional complexity of multi-sequential grammars with respect to the number of nonterminals. This investigation demonstrates that the family of recursively enumerable languages is characterized by six-nonterminal multi-sequential grammars.

Published
1997
Pages
179-189
Journal
International Journal of Computer Mathematics, vol. 1997, no. 65, ISSN 0020-7160
Book
International Journal of Computer Mathematics
Place
London, GB
BibTeX 
@ARTICLE{FITPUB6172,
   author = "Alexander Meduna",
   title = "Six-Nonterminal Multi-Sequential Grammars Characterize the Family of Recursively Enumerable Languages",
   pages = "179--189",
   booktitle = "International Journal of Computer Mathematics",
   journal = "International Journal of Computer Mathematics",
   volume = 1997,
   number = 65,
   year = 1997,
   location = "London, GB",
   ISSN = "0020-7160",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/6172"
}
Back to top