Result 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.
Type
journal article
Language
English
Authors
Bidlo Radek, Ing., Ph.D., FIT (FIT), DIFS (FIT)
Blatný Petr, Ing., Ph.D., FIT (FIT), DIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Blatný Petr, Ing., Ph.D., FIT (FIT), DIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
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.
Keywords
context-free grammars, E0L grammars, derivations, 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"
}
Projects
Multi-Information Technologies, GACR, Standardní projekty, GA201/07/0005, start: 2007-01-01, end: 2009-12-31, completed
Departments