Publication Details

On State Grammars

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

Czech title

Stavové gramatiky

Type

journal article

Language

English

Authors

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

Keywords

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

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.

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"
}