Controlled Pure Grammar Systems

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F12%3APU101749" target="_blank" >RIV/00216305:26230/12:PU101749 - isvavai.cz</a>
Result on the web
<a href="http://www.jucs.org/jucs_18_14/controlled_pure_grammar_systems" target="_blank" >http://www.jucs.org/jucs_18_14/controlled_pure_grammar_systems</a>
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Controlled Pure Grammar Systems
Original language description
This paper discusses grammar systems that have only terminals, work in the leftmost way, and generate their languages under the regulation by control languages over rule labels. It establishes three results concerning their generative power. First, without any control languages, these systems are not even able to generate all context-free languages. Second, with regular control languages, these systems, having no more than two components, characterize the family of recursively enumerable languages. Finally, with control languages that are themselves generated by regular-controlled context-free grammars, these systems over unary alphabets generate nothing but regular languages. In its introductory section, the paper gives a motivation for introducing these systems, and in the concluding section, it formulates several open problems.
Czech name
—
Czech description
—

Project
<a href="/en/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: IT4Innovations Centre of Excellence</a>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP) Z - Vyzkumny zamer (s odkazem do CEZ) S - Specificky vyzkum na vysokych skolach

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)