##### Document Text Contents

Page 1

Francesco Parisi-Presicce

Bernhard Westfechtel (Eds.)

123

LN

CS

9

15

1

8th International Conference, ICGT 2015

Held as Part of STAF 2015

L'Aquila, Italy, July 21–23, 2015, Proceedings

Graph

Transformation

Page 2

Lecture Notes in Computer Science 9151

Commenced Publication in 1973

Founding and Former Series Editors:

Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board

David Hutchison

Lancaster University, Lancaster, UK

Takeo Kanade

Carnegie Mellon University, Pittsburgh, PA, USA

Josef Kittler

University of Surrey, Guildford, UK

Jon M. Kleinberg

Cornell University, Ithaca, NY, USA

Friedemann Mattern

ETH Zurich, Zürich, Switzerland

John C. Mitchell

Stanford University, Stanford, CA, USA

Moni Naor

Weizmann Institute of Science, Rehovot, Israel

C. Pandu Rangan

Indian Institute of Technology, Madras, India

Bernhard Steffen

TU Dortmund University, Dortmund, Germany

Demetri Terzopoulos

University of California, Los Angeles, CA, USA

Doug Tygar

University of California, Berkeley, CA, USA

Gerhard Weikum

Max Planck Institute for Informatics, Saarbrücken, Germany

Page 146

134 M. de Oliveira Oliveira

the application of one layer of transformation rules if and only if there exists

unit decompositions U1 ∈ L(A(R, ξ1, ..., ξc)) and U2 ∈ Δ(inv(U,αun)) such

that α(U1 ⊗ U2) is a unit decomposition of H.

The proof of Lemma 9, which is lengthy and technically involved, will be

available in the full version of this paper. Recall that if A is a slice automaton,

then N (A) denotes the slice automaton whose graph language consists of all

possible graphs that can be obtained from graphs in LG(A) by the application

of one layer of transformation rules (See Theorem 6). As a corollary of Lemma 9

we have that the slice automaton N (A) can be defined from A by the application

of a constant number of elementary slice language operations.

Corollary 10. Let R be a set of graph transformation rules, αun be the uncol-

oring projection defined in the beginning of this section, and α be the projection

of Lemma 9. Let N (A) be the slice automaton defined in Theorem 6. Then

N (A) = A ∪ α[A(R, ξ1, ...ξc) ⊗ Δ(inv(A,αun))] ∩ A(Σ(c · ‖R‖, Γ1, Γ2)).

Finally, by combining Corollary 10 with Lemma 5 we have that the automaton

N (A) can be constructed in time 2O(c·‖R‖ log ‖R‖) · |A|. This proves Theorem 6.

��

6 Proofs of Our Main Results

We start by proving Proposition 1 which says that it is NP-complete to determine

whether a given graph G of unbounded cutwidth can be transformed into a given

graph H in depth d = 5.

Proof of Proposition 1. We show that the problem of determining whether a

graph H can be derived from a graph G in depth d = 5 is NP-complete. The

proof is by reduction from the Hamiltonian path problem. It is well known that

determining whether a graph G has a Hamiltonian path is NP-complete even if

G has maximum degree 3. On the other hand, by Vising’s theorem, the edges of

any graph of degree 3 can be colored with 4 colors in such a way that no two

adjacent edges have the same color. Now let G have n vertices, and let H be the

graph consisting of a line with n vertices. Then we have that G has a Hamiltonian

path if and only if H is a subgraph of G. Our transformation system consists of

8 transformation rules r1, ..., r4 and r′1, ..., r

′

4. For each i ∈ {1, ..., 4}, ri takes an

edge e and colors it with the color i. In the opposite direction, each r′i takes an

edge e of color i, and deletes it, leaving only its endpoints in the graph. Then

the process of testing whether G has a Hamiltonian path can be determined in

the following way. Assume G has a Hamiltonian path p = v1v2...vn. First, we

color into a single transformation step all edges of G not belonging to p in such a

way that no two adjacent edges have the same color. Subsequently we apply four

parallel transformation steps. At step i, we erase all edges colored with i. Since

no two edges with the same color are adjacent, such operation is well defined.

At the end of this process, only the edges of the Hamiltonian path p remain in

Page 147

Reachability in Graph Transformation Systems and Slice Languages 135

the graph. Therefore, since H is isomorphic to p we have that H can be derived

from G in 5 parallel steps. ��

Before proceeding with the proofs of Theorems 2 and 3, we state a theorem

which says that for any connected graph H of cutwidth at most c, one can con-

struct in time 2O(c log c) · |H|O(c) a normalized saturated slice automaton A(H, c)

generating precisely the unit decompositions of H of width at most c.

Theorem 11. Let H be a connected (Γ1, Γ2)-labeled digraph of cutwidth at

most c. One can construct in time 2O(c log c) · |H|O(c) a normalized saturated

slice automaton A(H, c) over the slice alphabet Σ(c, Γ1, Γ2) such that

L(A(H, c)) = {U ∈ L(Σ(c, Γ1, Γ2)) |

◦

U= H}.

Note that the graph language of A(H, c) has a unique graph, which is H itself.

In other words, LG(A(H, c)) = {H}. The importance of Theorem 11 for our

framework stems from the fact that that it allows us to verify in polynomial time

whether a graph H belongs to the graph language of an arbitrary normalized

slice automaton A. We observe that if A is not saturated, then some graphs in

the graph language LG(A) may correspond to few unit decompositions in the

slice language L(A). In this way to verify whether a graph H belongs to LG(A)

we have test for each unit decomposition U of H whether U ∈ L(A). If this

test is positive for one unit decomposition, then H is in the graph language

represented by A. However, enumerating all unit decompositions of a graph H

may take exponential time. Theorem 11 allows us to circumvent this problem.

Since A(H, c) is saturated, we have that H ∈ LG(A) if and only if the slice

language generated by A ∩ A(H, c) is non-empty. This non-emptiness test can

be performed in time |A| · |A(H, c)| = |A| · HO(c).

Proof of Theorem 2. Let G be a (Γ1, Γ2)-labeled graph of cutwidth at most

c. Using the results in [20] one can find, in time 2O(c) · |G|, an ordering ω =

(v1, v2, ..., vn) of the vertex of V such that maxi |E({v1, ..., vi}, {vi+1, ..., vn})| ≤

c. Now we can construct in time linear in |G| a unit decomposition U = S1S2...Sn

of G over the alphabet Σ(c, Γ1, Γ2) by letting vi be the center vertex of Si.

Now let A(U) be the slice automaton over Σ(c, Γ1, Γ2) which accepts a

unique unit decomposition, which is U itself. Then we have that |A| = O(|G|),

L(A(U)) = {U} and LG(A) = {G}. By Corollary 7 we can construct in time

2O(c·‖R‖

d·log |R|) · |G| a slice automaton A(R, G, d) = N d(A) over the slice alpha-

bet Σ(c · ‖R‖d, Γ1, Γ2) whose graph language LG(A(R, G, d)) consists precisely

of the set of graphs that can be obtained from LG(A) by the application of one

layer of transformation rules.

Now let H be a another (Γ1, Γ2)-labeled graph, and let c′ = c · ‖R‖d If the

cutwidth of H is greater than c′, then H cannot be reached from G in depth

at most d, and thus in this case our algorithm returns No. On the other hand,

if the cut-width of H is at most c′, then by Theorem 11, one can construct

in time 2O(c

′ log c′) · |H|O(c′) a saturated slice automaton A(H, c′) over the slice

alphabet Σ(c′, Γ1, Γ1) such that the graph language LG(A(H, c)) = {H}. There-

fore, since A(H, c) is saturated, we have that H belongs to the graph language

Page 291

282 M. Búr et al.

6 Conclusion and Future Work

In this paper, we described a novel feature of the EMF-IncQuery framework,

the support of local search-based pattern matching in addition to the previously

available incremental evaluation. By reusing the existing pattern language and

query development environment, it is possible to select the most appropriate

strategy without modifications to already developed patterns. Furthermore, we

presented a prototype graphical debugger that helps understanding complex

patterns by visualizing the execution of the search process. Both contributions

are included in the EMF-IncQuery project.

In the future, we plan to improve the local search support by providing a

model-sensitive planner for local search [5], that is expected to enhance the per-

formance. Another promising idea is the support of hybrid pattern matching [11]:

by mixing incrementally evaluated and local search-based pattern matching, it

is possible to fine-tune the performance characteristics (memory footprint or

execution time), extending the range of problems that can be addressed.

References

1. Ujhelyi, Z., Szõke, G., Ákos Horvth, Csiszár, N.I., Vidács, L., Varró, D., Ferenc,

R.: Performance comparison of query-based techniques for anti-pattern detection.

Information and Software Technology (0) (2015) - Accepted

2. Ujhelyi, Z., Bergmann, G., Hegeds, Á., Horváth, Á., Izsó, B., Ráth, I., Szatmári, Z.,

Varró, D.: EMF-Incquery: an integrated development environment for live model

queries. Sci. Comput. Program. 98(1), 80–99 (2015)

3. Nickel, U., Niere, J., Zündorf, A.: Tool demonstration: The FUJABA environ-

ment. In: Proceedings of the 22nd International Conference on Software Engineer-

ing (ICSE 2000), pp. 742–745. ACM Press, Limerick, Ireland (2000)

4. Geiß, R., Batz, G.V., Grund, D., Hack, S., Szalkowski, A.: GrGen: a fast spo-

based graph rewriting tool. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro,

L., Rozenberg, G. (eds.) ICGT 2006. LNCS, vol. 4178, pp. 383–397. Springer,

Heidelberg (2006)

5. Varró, G., Deckwerth, F., Wieber, M., Schürr, A.: An algorithm for generating

model-sensitive search plans for emf models. In: Hu, Z., de Lara, J. (eds.) ICMT

2012. LNCS, vol. 7307, pp. 224–239. Springer, Heidelberg (2012)

6. Oracle: Enterprise Manager (2015). http://www.oracle.com/technetwork/oem/

enterprise-manager/overview/index.html

7. Seifert, M., Katscher, S.: Debugging triple graph grammar-based model transfor-

mations. In: Fujaba Days, pp. 19–25 (2008)

8. Horn, T.: Model querying with funnyQT. In: Duddy, K., Kappel, G. (eds.) ICMB

2013. LNCS, vol. 7909, pp. 56–57. Springer, Heidelberg (2013)

9. Eclipse OCL Project: MDT-OCL website (2015). https://projects.eclipse.org/

projects/modeling.mdt.ocl

10. IBM Software: InfoSphere Data Architect (2015). http://www-01.ibm.com/soft

ware/data/optim/data-architect/

11. Horváth, Á., Bergmann, G., Ráth, I., Varró, D.: Experimental assessment of com-

bining pattern matching strategies with VIATRA2. Int. J. Softw. Tools Technol.

Transfer 12(3–4), 211–230 (2010)

Page 292

Author Index

Anjorin, Anthony 87, 257

Arendt, Thorsten 155

Becker, Jan Steffen 155

Bruggink, H.J. Sander 52

Búr, Márton 275

Corradini, Andrea 35

de Oliveira Oliveira, Mateus 121

Diemert, Simon 205

Drewes, Frank 19

Duval, Dominique 35

Dyck, Johannes 237

Echahed, Rachid 35

Giese, Holger 237

Golas, Ulrike 69

Habel, Annegret 155

Heckel, Reiko 171

Hoffmann, Berthold 19

Horn, Tassilo 189

Horváth, Ákos 275

Kissinger, Aleks 138

Kleijn, Jetty 221

König, Barbara 52

Kwantes, Pieter M. 221

Leblebici, Erhan 87, 257

Löwe, Michael 3

Machado, Rodrigo 171

Minas, Mark 19

Nolte, Dennis 52

Padberg, Julia 104

Price, Morgan 205

Prost, Frederic 35

Radke, Hendrik 155

Rensink, Arend 221

Ribeiro, Leila 35, 171

Schürr, Andy 87, 257

Stückrath, Jan 266

Taentzer, Gabriele 69, 87, 155

Ujhelyi, Zoltán 275

Van Gorp, Pieter 221

Varró, Dániel 275

Weber, Jens H. 205

Zamdzhiev, Vladimir 138

Zantema, Hans 52

Francesco Parisi-Presicce

Bernhard Westfechtel (Eds.)

123

LN

CS

9

15

1

8th International Conference, ICGT 2015

Held as Part of STAF 2015

L'Aquila, Italy, July 21–23, 2015, Proceedings

Graph

Transformation

Page 2

Lecture Notes in Computer Science 9151

Commenced Publication in 1973

Founding and Former Series Editors:

Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board

David Hutchison

Lancaster University, Lancaster, UK

Takeo Kanade

Carnegie Mellon University, Pittsburgh, PA, USA

Josef Kittler

University of Surrey, Guildford, UK

Jon M. Kleinberg

Cornell University, Ithaca, NY, USA

Friedemann Mattern

ETH Zurich, Zürich, Switzerland

John C. Mitchell

Stanford University, Stanford, CA, USA

Moni Naor

Weizmann Institute of Science, Rehovot, Israel

C. Pandu Rangan

Indian Institute of Technology, Madras, India

Bernhard Steffen

TU Dortmund University, Dortmund, Germany

Demetri Terzopoulos

University of California, Los Angeles, CA, USA

Doug Tygar

University of California, Berkeley, CA, USA

Gerhard Weikum

Max Planck Institute for Informatics, Saarbrücken, Germany

Page 146

134 M. de Oliveira Oliveira

the application of one layer of transformation rules if and only if there exists

unit decompositions U1 ∈ L(A(R, ξ1, ..., ξc)) and U2 ∈ Δ(inv(U,αun)) such

that α(U1 ⊗ U2) is a unit decomposition of H.

The proof of Lemma 9, which is lengthy and technically involved, will be

available in the full version of this paper. Recall that if A is a slice automaton,

then N (A) denotes the slice automaton whose graph language consists of all

possible graphs that can be obtained from graphs in LG(A) by the application

of one layer of transformation rules (See Theorem 6). As a corollary of Lemma 9

we have that the slice automaton N (A) can be defined from A by the application

of a constant number of elementary slice language operations.

Corollary 10. Let R be a set of graph transformation rules, αun be the uncol-

oring projection defined in the beginning of this section, and α be the projection

of Lemma 9. Let N (A) be the slice automaton defined in Theorem 6. Then

N (A) = A ∪ α[A(R, ξ1, ...ξc) ⊗ Δ(inv(A,αun))] ∩ A(Σ(c · ‖R‖, Γ1, Γ2)).

Finally, by combining Corollary 10 with Lemma 5 we have that the automaton

N (A) can be constructed in time 2O(c·‖R‖ log ‖R‖) · |A|. This proves Theorem 6.

��

6 Proofs of Our Main Results

We start by proving Proposition 1 which says that it is NP-complete to determine

whether a given graph G of unbounded cutwidth can be transformed into a given

graph H in depth d = 5.

Proof of Proposition 1. We show that the problem of determining whether a

graph H can be derived from a graph G in depth d = 5 is NP-complete. The

proof is by reduction from the Hamiltonian path problem. It is well known that

determining whether a graph G has a Hamiltonian path is NP-complete even if

G has maximum degree 3. On the other hand, by Vising’s theorem, the edges of

any graph of degree 3 can be colored with 4 colors in such a way that no two

adjacent edges have the same color. Now let G have n vertices, and let H be the

graph consisting of a line with n vertices. Then we have that G has a Hamiltonian

path if and only if H is a subgraph of G. Our transformation system consists of

8 transformation rules r1, ..., r4 and r′1, ..., r

′

4. For each i ∈ {1, ..., 4}, ri takes an

edge e and colors it with the color i. In the opposite direction, each r′i takes an

edge e of color i, and deletes it, leaving only its endpoints in the graph. Then

the process of testing whether G has a Hamiltonian path can be determined in

the following way. Assume G has a Hamiltonian path p = v1v2...vn. First, we

color into a single transformation step all edges of G not belonging to p in such a

way that no two adjacent edges have the same color. Subsequently we apply four

parallel transformation steps. At step i, we erase all edges colored with i. Since

no two edges with the same color are adjacent, such operation is well defined.

At the end of this process, only the edges of the Hamiltonian path p remain in

Page 147

Reachability in Graph Transformation Systems and Slice Languages 135

the graph. Therefore, since H is isomorphic to p we have that H can be derived

from G in 5 parallel steps. ��

Before proceeding with the proofs of Theorems 2 and 3, we state a theorem

which says that for any connected graph H of cutwidth at most c, one can con-

struct in time 2O(c log c) · |H|O(c) a normalized saturated slice automaton A(H, c)

generating precisely the unit decompositions of H of width at most c.

Theorem 11. Let H be a connected (Γ1, Γ2)-labeled digraph of cutwidth at

most c. One can construct in time 2O(c log c) · |H|O(c) a normalized saturated

slice automaton A(H, c) over the slice alphabet Σ(c, Γ1, Γ2) such that

L(A(H, c)) = {U ∈ L(Σ(c, Γ1, Γ2)) |

◦

U= H}.

Note that the graph language of A(H, c) has a unique graph, which is H itself.

In other words, LG(A(H, c)) = {H}. The importance of Theorem 11 for our

framework stems from the fact that that it allows us to verify in polynomial time

whether a graph H belongs to the graph language of an arbitrary normalized

slice automaton A. We observe that if A is not saturated, then some graphs in

the graph language LG(A) may correspond to few unit decompositions in the

slice language L(A). In this way to verify whether a graph H belongs to LG(A)

we have test for each unit decomposition U of H whether U ∈ L(A). If this

test is positive for one unit decomposition, then H is in the graph language

represented by A. However, enumerating all unit decompositions of a graph H

may take exponential time. Theorem 11 allows us to circumvent this problem.

Since A(H, c) is saturated, we have that H ∈ LG(A) if and only if the slice

language generated by A ∩ A(H, c) is non-empty. This non-emptiness test can

be performed in time |A| · |A(H, c)| = |A| · HO(c).

Proof of Theorem 2. Let G be a (Γ1, Γ2)-labeled graph of cutwidth at most

c. Using the results in [20] one can find, in time 2O(c) · |G|, an ordering ω =

(v1, v2, ..., vn) of the vertex of V such that maxi |E({v1, ..., vi}, {vi+1, ..., vn})| ≤

c. Now we can construct in time linear in |G| a unit decomposition U = S1S2...Sn

of G over the alphabet Σ(c, Γ1, Γ2) by letting vi be the center vertex of Si.

Now let A(U) be the slice automaton over Σ(c, Γ1, Γ2) which accepts a

unique unit decomposition, which is U itself. Then we have that |A| = O(|G|),

L(A(U)) = {U} and LG(A) = {G}. By Corollary 7 we can construct in time

2O(c·‖R‖

d·log |R|) · |G| a slice automaton A(R, G, d) = N d(A) over the slice alpha-

bet Σ(c · ‖R‖d, Γ1, Γ2) whose graph language LG(A(R, G, d)) consists precisely

of the set of graphs that can be obtained from LG(A) by the application of one

layer of transformation rules.

Now let H be a another (Γ1, Γ2)-labeled graph, and let c′ = c · ‖R‖d If the

cutwidth of H is greater than c′, then H cannot be reached from G in depth

at most d, and thus in this case our algorithm returns No. On the other hand,

if the cut-width of H is at most c′, then by Theorem 11, one can construct

in time 2O(c

′ log c′) · |H|O(c′) a saturated slice automaton A(H, c′) over the slice

alphabet Σ(c′, Γ1, Γ1) such that the graph language LG(A(H, c)) = {H}. There-

fore, since A(H, c) is saturated, we have that H belongs to the graph language

Page 291

282 M. Búr et al.

6 Conclusion and Future Work

In this paper, we described a novel feature of the EMF-IncQuery framework,

the support of local search-based pattern matching in addition to the previously

available incremental evaluation. By reusing the existing pattern language and

query development environment, it is possible to select the most appropriate

strategy without modifications to already developed patterns. Furthermore, we

presented a prototype graphical debugger that helps understanding complex

patterns by visualizing the execution of the search process. Both contributions

are included in the EMF-IncQuery project.

In the future, we plan to improve the local search support by providing a

model-sensitive planner for local search [5], that is expected to enhance the per-

formance. Another promising idea is the support of hybrid pattern matching [11]:

by mixing incrementally evaluated and local search-based pattern matching, it

is possible to fine-tune the performance characteristics (memory footprint or

execution time), extending the range of problems that can be addressed.

References

1. Ujhelyi, Z., Szõke, G., Ákos Horvth, Csiszár, N.I., Vidács, L., Varró, D., Ferenc,

R.: Performance comparison of query-based techniques for anti-pattern detection.

Information and Software Technology (0) (2015) - Accepted

2. Ujhelyi, Z., Bergmann, G., Hegeds, Á., Horváth, Á., Izsó, B., Ráth, I., Szatmári, Z.,

Varró, D.: EMF-Incquery: an integrated development environment for live model

queries. Sci. Comput. Program. 98(1), 80–99 (2015)

3. Nickel, U., Niere, J., Zündorf, A.: Tool demonstration: The FUJABA environ-

ment. In: Proceedings of the 22nd International Conference on Software Engineer-

ing (ICSE 2000), pp. 742–745. ACM Press, Limerick, Ireland (2000)

4. Geiß, R., Batz, G.V., Grund, D., Hack, S., Szalkowski, A.: GrGen: a fast spo-

based graph rewriting tool. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro,

L., Rozenberg, G. (eds.) ICGT 2006. LNCS, vol. 4178, pp. 383–397. Springer,

Heidelberg (2006)

5. Varró, G., Deckwerth, F., Wieber, M., Schürr, A.: An algorithm for generating

model-sensitive search plans for emf models. In: Hu, Z., de Lara, J. (eds.) ICMT

2012. LNCS, vol. 7307, pp. 224–239. Springer, Heidelberg (2012)

6. Oracle: Enterprise Manager (2015). http://www.oracle.com/technetwork/oem/

enterprise-manager/overview/index.html

7. Seifert, M., Katscher, S.: Debugging triple graph grammar-based model transfor-

mations. In: Fujaba Days, pp. 19–25 (2008)

8. Horn, T.: Model querying with funnyQT. In: Duddy, K., Kappel, G. (eds.) ICMB

2013. LNCS, vol. 7909, pp. 56–57. Springer, Heidelberg (2013)

9. Eclipse OCL Project: MDT-OCL website (2015). https://projects.eclipse.org/

projects/modeling.mdt.ocl

10. IBM Software: InfoSphere Data Architect (2015). http://www-01.ibm.com/soft

ware/data/optim/data-architect/

11. Horváth, Á., Bergmann, G., Ráth, I., Varró, D.: Experimental assessment of com-

bining pattern matching strategies with VIATRA2. Int. J. Softw. Tools Technol.

Transfer 12(3–4), 211–230 (2010)

Page 292

Author Index

Anjorin, Anthony 87, 257

Arendt, Thorsten 155

Becker, Jan Steffen 155

Bruggink, H.J. Sander 52

Búr, Márton 275

Corradini, Andrea 35

de Oliveira Oliveira, Mateus 121

Diemert, Simon 205

Drewes, Frank 19

Duval, Dominique 35

Dyck, Johannes 237

Echahed, Rachid 35

Giese, Holger 237

Golas, Ulrike 69

Habel, Annegret 155

Heckel, Reiko 171

Hoffmann, Berthold 19

Horn, Tassilo 189

Horváth, Ákos 275

Kissinger, Aleks 138

Kleijn, Jetty 221

König, Barbara 52

Kwantes, Pieter M. 221

Leblebici, Erhan 87, 257

Löwe, Michael 3

Machado, Rodrigo 171

Minas, Mark 19

Nolte, Dennis 52

Padberg, Julia 104

Price, Morgan 205

Prost, Frederic 35

Radke, Hendrik 155

Rensink, Arend 221

Ribeiro, Leila 35, 171

Schürr, Andy 87, 257

Stückrath, Jan 266

Taentzer, Gabriele 69, 87, 155

Ujhelyi, Zoltán 275

Van Gorp, Pieter 221

Varró, Dániel 275

Weber, Jens H. 205

Zamdzhiev, Vladimir 138

Zantema, Hans 52