Detail publikace

Context-Free and E0L Derivations over Free Groups

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

Originální název

Context-Free and E0L Derivations over Free Groups

Typ

článek v časopise - ostatní, Jost

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

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

Autoři

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

Rok RIV

2007

Vydáno

28. 2. 2007

Místo

Krakow

ISSN

0860-0295

Periodikum

Schedae Informaticae

Ročník

2007

Číslo

16

Stát

Polská republika

Strany od

14

Strany do

24

Strany počet

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