On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S0304397513000066" target="_blank" >http://www.sciencedirect.com/science/article/pii/S0304397513000066</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2012.12.040" target="_blank" >10.1016/j.tcs.2012.12.040</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars

Popis výsledku v původním jazyce

The present paper explains how to transform any regular-controlled (context-free) grammar with appearance checking G to a propagating regular-controlled (context-free) grammar with appearance checking G' whose language L(G') has sentences of the form wz, where w is in L(G) and z is a parse of w in G'. Consequently, for every recursively enumerable language K, there exists a propagating regular-controlled grammar with appearance checking G' with L(G') of the above form so that K results from L(G') by erasing all rules in L(G'). In addition, analogical results are established (a) in terms of these grammars without appearance checking and (b) in terms of these grammars that make only leftmost derivations. In the conclusion, we point out some consequences implied by the results achieved in this paper.

Název v anglickém jazyce

On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars

Popis výsledku anglicky

The present paper explains how to transform any regular-controlled (context-free) grammar with appearance checking G to a propagating regular-controlled (context-free) grammar with appearance checking G' whose language L(G') has sentences of the form wz, where w is in L(G) and z is a parse of w in G'. Consequently, for every recursively enumerable language K, there exists a propagating regular-controlled grammar with appearance checking G' with L(G') of the above form so that K results from L(G') by erasing all rules in L(G'). In addition, analogical results are established (a) in terms of these grammars without appearance checking and (b) in terms of these grammars that make only leftmost derivations. In the conclusion, we point out some consequences implied by the results achieved in this paper.

Druh

J_ost - 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)

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í

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ů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

1879-2294

Svazek periodika

477

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

9

Strana od-do

67-75

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—