One-Sided Forbidding Grammars and Selective Substitution Grammars

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F12%3APU98154" target="_blank" >RIV/00216305:26230/12:PU98154 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

One-Sided Forbidding Grammars and Selective Substitution Grammars

Popis výsledku v původním jazyce

In one-sided forbidding grammars, the set of rules is divided into the set of left forbidding rules and the set of right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding symbols is absent to the left of the rewritten symbol in the current sentential form while a right forbidding rule is applied analogically except that this absence is verified to the right. Apart from this, they work like ordinary forbidding grammars. As its main result, the present paper proves that one-sided forbidding grammars are equivalent to selective substitution grammars. This equivalence is established in terms of grammars with and without erasing rules. Furthermore, the paper proves that one-sided forbidding grammars in which the set of left forbidding rules coincides with the set of right forbidding rules characterize the family of context-free languages. In the conclusion, the significance of the achieved results is discussed.

Název v anglickém jazyce

One-Sided Forbidding Grammars and Selective Substitution Grammars

Popis výsledku anglicky

In one-sided forbidding grammars, the set of rules is divided into the set of left forbidding rules and the set of right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding symbols is absent to the left of the rewritten symbol in the current sentential form while a right forbidding rule is applied analogically except that this absence is verified to the right. Apart from this, they work like ordinary forbidding grammars. As its main result, the present paper proves that one-sided forbidding grammars are equivalent to selective substitution grammars. This equivalence is established in terms of grammars with and without erasing rules. Furthermore, the paper proves that one-sided forbidding grammars in which the set of left forbidding rules coincides with the set of right forbidding rules characterize the family of context-free languages. In the conclusion, the significance of the achieved results is discussed.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

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>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2012

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ů

Název periodika

International Journal of Computer Mathematics

ISSN

0020-7160

e-ISSN

—

Svazek periodika

89

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

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

Počet stran výsledku

11

Strana od-do

586-596

Kód UT WoS článku

000300852300001

EID výsledku v databázi Scopus

—