Fakulta informačních technologií VUT v Brně

Detail publikace

One-Sided Random Context Grammars: A Survey

MEDUNA Alexander a ZEMEK Petr. One-Sided Random Context Grammars: A Survey. Computing with New Resources. Berlin: Springer Verlag, 2014, s. 338-351. ISBN 978-3-319-13349-2. Dostupné z: https://www.scopus.com/record/display.uri?eid=2-s2.0-84916899681&origin=resultslist
Název česky
Jednostranné gramatiky s nahodilým kontextem: Přehled
Typ
kapitola v knize
Jazyk
angličtina
Autoři
URL
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, DE
DOI
BibTeX
@INBOOK{FITPUB10515,
   author = "Alexander Meduna and Petr Zemek",
   title = "One-Sided Random Context Grammars: A Survey",
   pages = "338--351",
   booktitle = "Computing with New Resources",
   year = 2014,
   location = "Berlin, DE",
   publisher = "Springer Verlag",
   ISBN = "978-3-319-13349-2",
   doi = "10.1007/978-3-319-13350-8\_25",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10515"
}
Nahoru