Publication Details

Syntactic Complexity of Regulated Rewriting

CROOKS, C.; MEDUNA, A.; ŠÁREK, M. Syntactic Complexity of Regulated Rewriting. Kybernetika, 1993, vol. 1993, no. 30, p. 177-186. ISSN: 0023-5954.

Czech title

Syntaktická složitost regulovaného přepisování

Type

journal article

Language

English

Authors

CROOKS, C.
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Šárek Milan

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

Publisher

unknown

Place

Prague

BibTeX

@article{BUT191810,
  author="CROOKS, C. and MEDUNA, A. and ŠÁREK, M.",
  title="Syntactic Complexity of Regulated Rewriting",
  journal="Kybernetika",
  year="1993",
  volume="1993",
  number="30",
  pages="177--186",
  issn="0023-5954"
}