Publication Details

Syntactic Complexity of Context-Free Grammars over Word Monoids

MEDUNA, A. Syntactic Complexity of Context-Free Grammars over Word Monoids. Acta Informatica, 1996, vol. 1996, no. 33, p. 457-462. ISSN: 0001-5903.

Czech title

Syntaktická složitost bezkontextových gramatik nad monoidy se slovy

Type

journal article

Language

English

Authors

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

Keywords

syntactic complexity, context-free grammars, word monoids, recursively enumerable languages

Abstract

The syntactic complexity of context-free grammars defined over word monoids is investigated.

Annotation

The syntactic complexity of context-free grammars defined over word monoids is investigated. It is demonstrated that every recursively enumerable language can be defined by a ten-nonterminal context-free grammar over a word monoid generated by an alphabet and six words of length two. Open problems are formulated.

Published

1996

Pages

457–462

Journal

Acta Informatica, vol. 1996, no. 33, ISSN 0001-5903

Book

Acta Informatica

Publisher

Springer Verlag

Place

Berlin

BibTeX

@article{BUT191804,
  author="Alexandr {Meduna}",
  title="Syntactic Complexity of Context-Free Grammars over Word Monoids",
  journal="Acta Informatica",
  year="1996",
  volume="1996",
  number="33",
  pages="457--462",
  issn="0001-5903"
}