Undecidability of the emptiness problem for context-free picture languages

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00312203" target="_blank" >RIV/68407700:21230/17:00312203 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Undecidability of the emptiness problem for context-free picture languages

Popis výsledku v původním jazyce

A two-dimensional Kolam grammar as defined by Siromoney et al. in 1972 and independently by Matz in 1997 and Schlesinger in 1989 allows context-free productions of the form A->a, A->BC, A->B/C, and S->λ which concatenate sub-pictures produced by B and C horizontally respectively vertically if their height respectively width fits. We demonstrate that this grammar is quite powerful by proving undecidability of the emptiness problem. We further analyze consequences of this finding and give additional characteristics related to size of generated pictures.

Název v anglickém jazyce

Undecidability of the emptiness problem for context-free picture languages

Popis výsledku anglicky

A two-dimensional Kolam grammar as defined by Siromoney et al. in 1972 and independently by Matz in 1997 and Schlesinger in 1989 allows context-free productions of the form A->a, A->BC, A->B/C, and S->λ which concatenate sub-pictures produced by B and C horizontally respectively vertically if their height respectively width fits. We demonstrate that this grammar is quite powerful by proving undecidability of the emptiness problem. We further analyze consequences of this finding and give additional characteristics related to size of generated pictures.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA15-04960S" target="_blank" >GA15-04960S: SeLeCt - struktury, učení a kognice</a><br>

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

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

1879-2294

Svazek periodika

679

Číslo periodika v rámci svazku

May

Stát vydavatele periodika

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

Počet stran výsledku

8

Strana od-do

118-125

Kód UT WoS článku

000403125700010

EID výsledku v databázi Scopus

2-s2.0-84962429335