Publication Details

On State Grammars

HORVAT George and MEDUNA Alexander. On State Grammars. Acta Cybernetica, vol. 1988, no. 8, pp. 237-245. ISSN 0324-721X.

Czech title

Stavové gramatiky

Type

journal article

Language

english

Authors

Horvat George ( unknown)
Meduna Alexander, Doc. RNDr., CSc. (DCSE FEECS BUT)

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

Place

Szeged, HU

BibTeX

@ARTICLE{FITPUB6156,
   author = "George Horvat and Alexander Meduna",
   title = "On State Grammars",
   pages = "237--245",
   booktitle = "Acta Cybernetika",
   journal = "Acta Cybernetica",
   volume = 1988,
   number = 8,
   year = 1988,
   location = "Szeged, HU",
   ISSN = "0324-721X",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/6156"
}