Result Details

Context-Free Derivations on Word Monoids

MEDUNA, A. Context-Free Derivations on Word Monoids. ACTA INFORMATICA, 1990, vol. 1990, no. 27, p. 781-786. ISSN: 0001-5903.

Type

journal article

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc.

Abstract

It shown that using generators of the length at most two, context sensitive and recursively enumerable languages can be characterized in a natural manner.

Keywords

word monoids, finite languages, context-free grammars, context sensitive languages, recursively enumerable languages

Annotation

The notion of a (direct) derivation is introduced on word monoids generated by finite languages over total vocabularies of context-free grammars. It shown that using generators of the length at most two, context sensitive and recursively enumerable languages can be characterized in a natural manner.

Published

1990

Pages

781–786

Journal

ACTA INFORMATICA, vol. 1990, no. 27, ISSN 0001-5903

Book

Acta Informatica

Publisher

Springer Verlag

Place

Heidelberg

BibTeX

@article{BUT191816,
  author="Alexandr {Meduna}",
  title="Context-Free Derivations on Word Monoids",
  journal="ACTA INFORMATICA",
  year="1990",
  volume="1990",
  number="27",
  pages="781--786",
  issn="0001-5903"
}

Departments

Faculty of Information Technology (FIT)