Result Details

On State Grammars

HORVAT, G.; MEDUNA, A. On State Grammars. Acta Cybernetica, 1988, vol. 1988, no. 8, p. 237-245. ISSN: 0324-721X.

Type

journal article

Language

English

Authors

HORVAT, G.
Meduna Alexandr, prof. RNDr., CSc.

Abstract

In this paper we study some properties of state grammars. Among others, it is shown that for every recursively enumerable language there exists a state gammar with erasing rules that generates it.

Keywords

state grammars, recursively enumerable languages, gammars with erasing rules, descriptive complexity

Annotation

In this paper we study some properties of state grammars. Among others, it is shown that for every recursively enumerable language there exists a state gammar with erasing rules that generates it. Some problems concerning the descriptive complexity of state grammars are discussed.

Published

1988

Pages

237–245

Journal

Acta Cybernetica, vol. 1988, no. 8, ISSN 0324-721X

Book

Acta Cybernetika

Publisher

unknown

Place

Szeged

BibTeX

@article{BUT191817,
  author="HORVAT, G. and MEDUNA, A.",
  title="On State Grammars",
  journal="Acta Cybernetica",
  year="1988",
  volume="1988",
  number="8",
  pages="237--245",
  issn="0324-721X"
}

Departments

Faculty of Information Technology (FIT)