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”

Generalized One-Sided Forbidding Grammars

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F13%3APU106273" target="_blank" >RIV/00216305:26230/13:PU106273 - isvavai.cz</a>

  • Výsledek na webu

    <a href="http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.723703" target="_blank" >http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.723703</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1080/00207160.2012.723703" target="_blank" >10.1080/00207160.2012.723703</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    Generalized One-Sided Forbidding Grammars

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

    In generalized one-sided forbidding grammars (GOFGs), each context-free rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary context-free rules without any forbidding strings characterize the family of context-free languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of context-free languages.

  • Název v anglickém jazyce

    Generalized One-Sided Forbidding Grammars

  • Popis výsledku anglicky

    In generalized one-sided forbidding grammars (GOFGs), each context-free rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary context-free rules without any forbidding strings characterize the family of context-free languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of context-free languages.

Klasifikace

  • Druh

    J<sub>ost</sub> - Ostatní články v recenzovaných periodicích

  • 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

    <a href="/cs/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: Centrum excelence IT4Innovations</a><br>

  • Návaznosti

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

Ostatní

  • Rok uplatnění

    2013

  • 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 periodika

    International Journal of Computer Mathematics

  • ISSN

    0020-7160

  • e-ISSN

    1029-0265

  • Svazek periodika

    90

  • Číslo periodika v rámci svazku

    2

  • Stát vydavatele periodika

    GB - Spojené království Velké Británie a Severního Irska

  • Počet stran výsledku

    11

  • Strana od-do

    172-182

  • Kód UT WoS článku

  • EID výsledku v databázi Scopus