On Tree-Restricted Regular-Controlled Context-Free Grammars

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F17%3APU126454" target="_blank" >RIV/00216305:26230/17:PU126454 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

On Tree-Restricted Regular-Controlled Context-Free Grammars

Popis výsledku v původním jazyce

This paper gives simple tree-based conditions under which regular-controlled context-free grammars generate context-free languages of finite index, so they cannot even generate all context-free languages. It defines the notion of path-changing derivation step which corresponds to performing two consecutive rewritings of nonterminal symbols present in the different branches of the derivation tree. It proves that if there exists a certain constant that limits the number of path-changing deriva- tion steps, then, the regular-controlled grammar generates a context-free language of finite index. At the end, we generalize achieved result and provide some open problems for future study.

Název v anglickém jazyce

On Tree-Restricted Regular-Controlled Context-Free Grammars

Popis výsledku anglicky

This paper gives simple tree-based conditions under which regular-controlled context-free grammars generate context-free languages of finite index, so they cannot even generate all context-free languages. It defines the notion of path-changing derivation step which corresponds to performing two consecutive rewritings of nonterminal symbols present in the different branches of the derivation tree. It proves that if there exists a certain constant that limits the number of path-changing deriva- tion steps, then, the regular-controlled grammar generates a context-free language of finite index. At the end, we generalize achieved result and provide some open problems for future study.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

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)

Rok uplatnění

2017

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: Computer Systems Theory

ISSN

2379-9927

e-ISSN

—

Svazek periodika

2

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

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

Počet stran výsledku

17

Strana od-do

147-163

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85056990677