Publication Details

Context-Free and E0L Derivations over Free Groups

BIDLO Radek, BLATNÝ Petr and MEDUNA Alexander. Context-Free and E0L Derivations over Free Groups. Schedae Informaticae, vol. 2007, no. 16, pp. 14-24. ISSN 0860-0295.
Czech title
Bezkontextové a E0L derivace nad volnými grupami
Type
journal article
Language
english
Authors
Bidlo Radek, Ing. (DIFS FIT BUT)
Blatný Petr, Ing. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
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, PL
BibTeX 
@ARTICLE{FITPUB8271,
   author = "Radek Bidlo and Petr Blatn\'{y} and Alexander Meduna",
   title = "Context-Free and E0L Derivations over Free Groups",
   pages = "14--24",
   booktitle = "Schedae Informaticae",
   journal = "Schedae Informaticae",
   volume = 2007,
   number = 16,
   year = 2007,
   location = "Krakow, PL",
   ISSN = "0860-0295",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8271"
}
Back to top