Kapitola v knize

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
Jazyk publikace:angličtina
Název publikace:One-Sided Random Context Grammars: A Survey
Název (cs):Jednostranné gramatiky s nahodilým kontextem: Přehled
Strany:338-351
Kniha:Computing with New Resources
Místo vydání:Berlin, DE
Rok:2014
URL:https://www.scopus.com/record/display.uri?eid=2-s2.0-84916899681&origin=resultslist
ISBN:978-3-319-13349-2
DOI:10.1007/978-3-319-13350-8_25
Vydavatel:Springer Verlag
URL:http://www.springer.com/computer/theoretical+computer+science/book/978-3-319-13349-2 [HTML]
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
Anotace
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ů.
BibTeX:
@INBOOK{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=10515}
}

Vaše IPv4 adresa: 35.175.200.4
Přepnout na https