Publication Details

Syntactic Complexity of Context-Free Grammars over Word Monoids

MEDUNA Alexander. Syntactic Complexity of Context-Free Grammars over Word Monoids. Acta Informatica, vol. 1996, no. 33, pp. 457-462. ISSN 0001-5903.
Czech title
Syntaktická složitost bezkontextových gramatik nad monoidy se slovy
Type
journal article
Language
english
Authors
Meduna Alexander, Doc. RNDr., CSc. (DCSE FEECS BUT)
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, DE
BibTeX 
@ARTICLE{FITPUB6169,
   author = "Alexander Meduna",
   title = "Syntactic Complexity of Context-Free Grammars over Word Monoids",
   pages = "457--462",
   booktitle = "Acta Informatica",
   journal = "Acta Informatica",
   volume = 1996,
   number = 33,
   year = 1996,
   location = "Berlin, DE",
   publisher = "Springer Verlag",
   ISSN = "0001-5903",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/6169"
}
Back to top