Reachability in graph transformation systems and slice languages

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F15%3A00454008" target="_blank" >RIV/67985840:_____/15:00454008 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-21145-9_8" target="_blank" >http://dx.doi.org/10.1007/978-3-319-21145-9_8</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-21145-9_8" target="_blank" >10.1007/978-3-319-21145-9_8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Reachability in graph transformation systems and slice languages

Popis výsledku v původním jazyce

In this work we show that the reachability problem for graph transformation systems is in the complexity class XP when parameterized with respect to the depth of derivations and the cutwidth of the source graph. More precisely, we show that for any set R of graph transformation rules, one can determine in time f(c,d)G H g(c,d) whether a graph G of cutwidth c can be transformed into a graph H in depth at most d by the application of graph transformation rules from R . In particular, our algorithm runs in polynomial time when c and d are constants. On the other hand, we show that the problem becomes NP-hard if we allow c=O(G) and d=5 . In the case in which all transformation rules are monotone we get an algorithm running in time f(c,d)⋅G O(c) ⋅H . To prove our main theorems we will establish an interesting connection between graph transformation systems and regular slice languages.

Název v anglickém jazyce

Reachability in graph transformation systems and slice languages

Popis výsledku anglicky

In this work we show that the reachability problem for graph transformation systems is in the complexity class XP when parameterized with respect to the depth of derivations and the cutwidth of the source graph. More precisely, we show that for any set R of graph transformation rules, one can determine in time f(c,d)G H g(c,d) whether a graph G of cutwidth c can be transformed into a graph H in depth at most d by the application of graph transformation rules from R . In particular, our algorithm runs in polynomial time when c and d are constants. On the other hand, we show that the problem becomes NP-hard if we allow c=O(G) and d=5 . In the case in which all transformation rules are monotone we get an algorithm running in time f(c,d)⋅G O(c) ⋅H . To prove our main theorems we will establish an interesting connection between graph transformation systems and regular slice languages.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

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 statě ve sborníku

Graph Transformation

ISBN

978-3-319-21144-2

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

17

Strana od-do

121-137

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

L'Aquila

Datum konání akce

21. 6. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000364104800008