Detail výsledku

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.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Bidlo Radek, Ing., Ph.D., UIFS (FIT)
Blatný Petr, Ing., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
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

Rok
2007
Strany
14–24
Časopis
Schedae Informaticae, roč. 2007, č. 16, ISSN 0860-0295
Kniha
Schedae Informaticae
Místo
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"
}
Projekty
Multiinformační technologie, GAČR, Standardní projekty, GA201/07/0005, zahájení: 2007-01-01, ukončení: 2009-12-31, ukončen
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru