Detail publikace

One-Sided Random Context Grammars: A Survey

MEDUNA, A.; ZEMEK, P. One-Sided Random Context Grammars: A Survey. In Computing with New Resources. Berlin: Springer Verlag, 2014. p. 338-351. ISBN: 978-3-319-13349-2.
Název česky
Jednostranné gramatiky s nahodilým kontextem: Přehled
Typ
kapitola v knize
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Zemek Petr, Ing., Ph.D.
URL
Klíčová slova

formal language theory, regulated rewriting, random context grammars, one-sided random context grammars, generative power, normal forms, reduction, leftmost derivations, generalized versions, survey

Abstrakt

Připomeňme, že pojem jednastránné gramatiky s nahodilým kontextem je založen na konečném počtu bezkontextových pravidel, která jsou doplněna konečným počtem povolujících a zakazujících neterminálních symbolů. Množina těchto pravidel je rozdělena na dvě - množinu zleva nahodilých pravidel a množinu zprava nahodilých pravidel. Když aplikujeme zleva nahodilé pravidlo, gramatika zkontroluje existenci povolujících a absenci zakazujících neterminálů v prefixu nalevo od přepisovaného neterminálu. Analogicky při aplikaci zprava nahodilého pravidla je kontrolována existence povolujících a absence zakazujících symbolů v sufixu napravo od přepisovaného neterminálu. Tato kapitola v knize dává přehled dosažených výsledků pro tyto jednostranné gramatiky s nahodilým kontextem. Tyto výsledky se týkají generativní síly, normálních forem, redukce velikosti a koncepčních modifikací, které jsou omezujícími či zobecňujícími verzemi těchto gramatik. Pravděpodobně nejzájímavější výsledek říká, že jednostranné gramatiky s nahodilým kontextem bez vymazávajících pravidel charakterizují třídu kontextových jazyků a s vymazávajícími pravidly charakterizují třídu rekurzivně spočetných jazyků, z čehož plyne, že jsou tyto gramatiky silnější než klasické gramatiky s nahodilým kontextem. Dále je navrženo studium řady otevřených problémů.

Rok
2014
Strany
338–351
Kniha
Computing with New Resources
ISBN
978-3-319-13349-2
Vydavatel
Springer Verlag
Místo
Berlin
DOI
10.1007/978-3-319-13350-8_25
EID Scopus
2-s2.0-84916899681
BibTeX 
@inbook{BUT111524,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="One-Sided Random Context Grammars: A Survey",
  booktitle="Computing with New Resources",
  year="2014",
  publisher="Springer Verlag",
  address="Berlin",
  pages="338--351",
  doi="10.1007/978-3-319-13350-8\{_}25",
  isbn="978-3-319-13349-2",
  url="https://www.scopus.com/record/display.uri?eid=2-s2.0-84916899681&origin=resultslist"
}
Nahoru