Detail publikačního výsledku

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

Anglický název

Context-Free and E0L Derivations over Free Groups

Druh

Článek recenzovaný mimo WoS a Scopus

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.

Anglický 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

Klíčová slova v angličtině

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

Autoři

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

Rok RIV

2010

Vydáno

28.02.2007

Místo

Krakow

Kniha

Schedae Informaticae

ISSN

0860-0295

Periodikum

Schedae Informaticae

Svazek

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