On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>ost</sub> - Miscellaneous article in a specialist periodical
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
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
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
1879-2294
Volume of the periodical
477
Issue of the periodical within the volume
1
Country of publishing house
FR - FRANCE
Number of pages
9
Pages from-to
67-75
UT code for WoS article
—
EID of the result in the Scopus database
—