Publication Details

Syntactic Complexity of Regulated Rewriting

CROOKS Cynthia, MEDUNA Alexander and ŠÁREK Milan. Syntactic Complexity of Regulated Rewriting. Kybernetika, vol. 1993, no. 30, pp. 177-186. ISSN 0023-5954.
Czech title
Syntaktická složitost regulovaného přepisování
Type
journal article
Language
english
Authors
Crooks Cynthia ( unknown)
Meduna Alexander, Doc. RNDr., CSc. (DCSE FEECS BUT)
Šárek Milan, Ing. (CVIS BUT)
Keywords

syntactic complexity, regulated grammars, number of nonterminals, recursive enumerable languages, programmed grammars

Abstract

The syntactic complexity of regulated grammars with respect to the number of nonterminals is investigated.

Annotation

The syntactic complexity of regulated grammars with respect to the number of nonterminals is investigated. Several characterizations of the family of recursive enumerable languages are established; most importantly, it is proved that this family is defined by programmed grammars with only seven nonterminals.

Published
1993
Pages
177-186
Journal
Kybernetika, vol. 1993, no. 30, ISSN 0023-5954
Book
Kybernetika
Place
Prague, CZ
BibTeX 
@ARTICLE{FITPUB6163,
   author = "Cynthia Crooks and Alexander Meduna and Milan \v{S}\'{a}rek",
   title = "Syntactic Complexity of Regulated Rewriting",
   pages = "177--186",
   booktitle = "Kybernetika",
   journal = "Kybernetika",
   volume = 1993,
   number = 30,
   year = 1993,
   location = "Prague, CZ",
   ISSN = "0023-5954",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/6163"
}
Back to top