Publication detail

Context-Free and E0L Derivations over Free Groups

BIDLO, R. BLATNÝ, P. MEDUNA, A.

Original Title

Context-Free and E0L Derivations over Free Groups

Type

journal article - other

Language

English

Original 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

Authors

BIDLO, R.; BLATNÝ, P.; MEDUNA, A.

RIV year

2007

Released

28. 2. 2007

Location

Krakow

ISBN

0860-0295

Periodical

Schedae Informaticae

Year of study

2007

Number

16

State

Republic of Poland

Pages from

14

Pages to

24

Pages count

11

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"
}