Publication Details

Descriptional Complexity of Multi-Continues Grammars

MEDUNA, A. Descriptional Complexity of Multi-Continues Grammars. Acta Cybernetica, 1998, vol. 1998, no. 13, p. 375-384. ISSN: 0324-721X.

Czech title

Popisná složitost multi-continuous gramatik

Type

journal article

Language

English

Authors

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

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

Publisher

unknown

Place

Szeged

BibTeX

@article{BUT191797,
  author="Alexandr {Meduna}",
  title="Descriptional Complexity of Multi-Continues Grammars",
  journal="Acta Cybernetica",
  year="1998",
  volume="1998",
  number="13",
  pages="375--384",
  issn="0324-721X"
}