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
—