Controlled Pure Grammar Systems

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

Controlled Pure Grammar Systems

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Controlled Pure Grammar Systems

Popis výsledku anglicky

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.

Druh

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

CEP obor

IN - Informatika

OECD FORD obor

—

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

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

Journal of Universal Computer Science

ISSN

0948-6968

e-ISSN

—

Svazek periodika

18

Číslo periodika v rámci svazku

14

Stát vydavatele periodika

AT - Rakouská republika

Počet stran výsledku

17

Strana od-do

2024-2040

Kód UT WoS článku

000310430600007

EID výsledku v databázi Scopus

—