Publication Details

Descriptional Complexity of Multi-Continues Grammars

MEDUNA Alexander. Descriptional Complexity of Multi-Continues Grammars. Acta Cybernetica, vol. 1998, no. 13, pp. 375-384. ISSN 0324-721X.
Czech title
Popisná složitost multi-continuous gramatik
Type
journal article
Language
english
Authors
Meduna Alexander, Doc. RNDr., CSc. (DCSE FEECS BUT)
Keywords

multi-continuous grammars, descriptional complexity, recursively enumerable languages

Abstract

The present paper discusses multi-continuous grammars and their descriptional complexity with respect to the number of nonterminals.

Annotation

The present paper discusses multi-continuous grammars and their descriptional complexity with respect to the number of nonterminals. It proves that six-nonterminal multi-continuous grammars characterize the family of recursively enumerable languages. In addition, this paper formulates an open problem area closely related to this characterization.

Published
1998
Pages
375-384
Journal
Acta Cybernetica, vol. 1998, no. 13, ISSN 0324-721X
Book
Acta Cybernetica
Place
Szeged, HU
BibTeX 
@ARTICLE{FITPUB6176,
   author = "Alexander Meduna",
   title = "Descriptional Complexity of Multi-Continues Grammars",
   pages = "375--384",
   booktitle = "Acta Cybernetica",
   journal = "Acta Cybernetica",
   volume = 1998,
   number = 13,
   year = 1998,
   location = "Szeged, HU",
   ISSN = "0324-721X",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/6176"
}
Back to top