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., 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