Publication Details

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

MEDUNA, A. Six-Nonterminal Multi-Sequential Grammars Characterize the Family of Recursively Enumerable Languages. International Journal of Computer Mathematics, 1997, vol. 1997, no. 65, p. 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 Alexandr, prof. RNDr., CSc. (DIFS)
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
Publisher
unknown
Place
London
BibTeX 
@article{BUT191801,
  author="Alexandr {Meduna}",
  title="Six-Nonterminal Multi-Sequential Grammars Characterize the Family of Recursively Enumerable Languages",
  journal="International Journal of Computer Mathematics",
  year="1997",
  volume="1997",
  number="65",
  pages="179--189",
  issn="0020-7160"
}
Back to top