Detail výsledku

One-Sided Random Context Grammars with Leftmost Derivations

MEDUNA, A.; ZEMEK, P. One-Sided Random Context Grammars with Leftmost Derivations. In LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday. Berlin-Heidelberg: Springer Verlag, 2012. p. 160-173. ISBN: 978-3-642-31643-2.
Typ
kapitola, resp. kapitoly v odborné knize
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Zemek Petr, Ing., Ph.D., FIT (FIT), UIFS (FIT)
Abstrakt

In this paper, we study the generative power of one-sided random context grammars working in a leftmost way. More specifically, by analogy with the three well-known types of leftmost derivations in regulated grammars, we introduce three types of leftmost derivations to one-sided random context grammars and prove the following three results. (I) One-sided random context grammars with type-1 leftmost derivations characterize the family of context-free languages. (II) One-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of recursively enumerable languages. (III) Propagating one-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of context-sensitive languages. In the conclusion, the generative power of random context grammars and one-sided random context grammars with leftmost derivations is compared.

Klíčová slova

formal languages, regulated rewriting, one-sided random context grammars, leftmost derivations, generative power

URL
Rok
2012
Strany
160–173
Kniha
LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday
ISBN
978-3-642-31643-2
Vydavatel
Springer Verlag
Místo
Berlin-Heidelberg
DOI
10.1007/978-3-642-31644-9_11
EID Scopus
2-s2.0-84867018824
BibTeX 
@inbook{BUT96922,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="One-Sided Random Context Grammars with Leftmost Derivations",
  booktitle="LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday",
  year="2012",
  publisher="Springer Verlag",
  address="Berlin-Heidelberg",
  pages="160--173",
  doi="10.1007/978-3-642-31644-9\{_}11",
  isbn="978-3-642-31643-2",
  url="https://www.scopus.com/record/display.uri?eid=2-s2.0-84867018824&origin=resultslist"
}
Projekty
Centrum excelence IT4Innovations, MŠMT, Operační program Výzkum a vývoj pro inovace, ED1.1.00/02.0070, zahájení: 2011-01-01, ukončení: 2015-12-31, ukončen
Pokročilé rozpoznávání a prezentace multimediálních dat, VUT, Vnitřní projekty VUT, FIT-S-11-2, zahájení: 2011-01-01, ukončení: 2013-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru