Publication Details

Context-Free and E0L Derivations over Free Groups

BIDLO, R.; BLATNÝ, P.; MEDUNA, A. Context-Free and E0L Derivations over Free Groups. Schedae Informaticae, 2007, vol. 2007, no. 16, p. 14-24. ISSN: 0860-0295.
Czech title
Bezkontextové a E0L derivace nad volnými grupami
Type
journal article
Language
English
Authors
Bidlo Radek, Ing., Ph.D.
Blatný Petr, Ing., Ph.D.
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Keywords

context-free grammars, E0L grammars, derivations, free groups

Abstract

In the context-free and E0L grammars discussed in this paper, the derivations are introduced over free groups rather than free monoids. It is proved that both grammars with derivations introduced in this way characterize the family of recursively enumerable languages in a very succinct way. Specifically, this characterization is based on the eight-nonterminal contextfree grammars and six-nonterminal E0L grammars over free groups.

Published
2007
Pages
14–24
Journal
Schedae Informaticae, vol. 2007, no. 16, ISSN 0860-0295
Book
Schedae Informaticae
Place
Krakow
BibTeX 
@article{BUT45190,
  author="Radek {Bidlo} and Petr {Blatný} and Alexandr {Meduna}",
  title="Context-Free and E0L Derivations over Free Groups",
  journal="Schedae Informaticae",
  year="2007",
  volume="2007",
  number="16",
  pages="14--24",
  issn="0860-0295"
}
Back to top