Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

One-Sided Random Context Grammars: A Survey

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F14%3APU111929" target="_blank" >RIV/00216305:26230/14:PU111929 - isvavai.cz</a>

  • Výsledek na webu

    <a href="https://www.scopus.com/record/display.uri?eid=2-s2.0-84916899681&origin=resultslist" target="_blank" >https://www.scopus.com/record/display.uri?eid=2-s2.0-84916899681&origin=resultslist</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1007/978-3-319-13350-8_25" target="_blank" >10.1007/978-3-319-13350-8_25</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    One-Sided Random Context Grammars: A Survey

  • Popis výsledku v původním jazyce

    Recall that the notion of a one-sided random context grammar is based upon a finite set of context-free rules, each of which may be extended by finitely many permitting and forbidding nonterminal symbols. The set of all these rules is divided into two sets - the set of left random context rules and the set of right random context rules. When applying a left random context rule, the grammar checks the existence and absence of its permitting and forbidding symbols, respectively, in the prefix to the left of the rewritten nonterminal. Analogically, when applying a right random context rule, it checks the existence and absence of its permitting and forbidding symbols, respectively, only in the suffix to the right of the rewritten nonterminal. This paper gives a survey of the established results concerning one-sided random context grammars. These results concern their generative power, normal forms, size reduction, and conceptual modifications, which represent both restricted and generalized versions of their standard concepts. Perhaps most importantly and surprisingly, the paper points out that propagating versions of one-sided random context grammars characterize the family of context-sensitive languages, and with erasing rules, they characterize the family of recursively enumerable languages; as a result, they are stronger than ordinary random context grammars. Many open problem areas are suggested.

  • Název v anglickém jazyce

    One-Sided Random Context Grammars: A Survey

  • Popis výsledku anglicky

    Recall that the notion of a one-sided random context grammar is based upon a finite set of context-free rules, each of which may be extended by finitely many permitting and forbidding nonterminal symbols. The set of all these rules is divided into two sets - the set of left random context rules and the set of right random context rules. When applying a left random context rule, the grammar checks the existence and absence of its permitting and forbidding symbols, respectively, in the prefix to the left of the rewritten nonterminal. Analogically, when applying a right random context rule, it checks the existence and absence of its permitting and forbidding symbols, respectively, only in the suffix to the right of the rewritten nonterminal. This paper gives a survey of the established results concerning one-sided random context grammars. These results concern their generative power, normal forms, size reduction, and conceptual modifications, which represent both restricted and generalized versions of their standard concepts. Perhaps most importantly and surprisingly, the paper points out that propagating versions of one-sided random context grammars characterize the family of context-sensitive languages, and with erasing rules, they characterize the family of recursively enumerable languages; as a result, they are stronger than ordinary random context grammars. Many open problem areas are suggested.

Klasifikace

  • Druh

    C - Kapitola v odborné knize

  • CEP obor

  • OECD FORD obor

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Návaznosti výsledku

  • Projekt

    Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

  • Návaznosti

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Ostatní

  • Rok uplatnění

    2014

  • Kód důvěrnosti údajů

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Údaje specifické pro druh výsledku

  • Název knihy nebo sborníku

    Computing with New Resources

  • ISBN

    978-3-319-13349-2

  • Počet stran výsledku

    14

  • Strana od-do

    338-351

  • Počet stran knihy

    473

  • Název nakladatele

    Springer Verlag

  • Místo vydání

    Berlin

  • Kód UT WoS kapitoly