Top

Published in:

2018 | OriginalPaper | Chapter

Graph Repair by Graph Programs

Authors : Annegret Habel, Christian Sandmann

Published in: Software Technologies: Applications and Foundations

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Model repair is an essential topic in model-driven engineering. We consider the problem of graph repair: Given a graph constraint, we try to construct a graph program, such that the application to any graph yields a graph satisfying the graph constraint. We show the existence of terminating repair programs for a number of satisfiable constraints.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Short-Cut Rules

next chapter Double-Pushout Rewriting in Context

Without loss of generality, we may assume that the conditions are proper, i.e., for all inclusion morphisms

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-04771-9_31/477029_1_En_31_IEq33_HTML.gif

in the condition, P is a proper subgraph of C.

For definition & existence of pushouts in the category of graphs see e.g. [EEPT06].

\(\bar{c}\) stands for the empty rule with the application condition c. \(\rightarrow ^+\)denotes the transitive closure of \(\rightarrow \).

A configuration \(\gamma \) is terminal if there is no configuration \(\delta \) such that \(\gamma \rightarrow \delta \).

A pair \((a',b')\) is jointly surjective if for each \(x\in R'\) there is a preimage \(y\in R\) with \(a'(y)=x\) or \(z\in C\) with \(b'(z)=x\).

For a rule

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-04771-9_31/477029_1_En_31_IEq155_HTML.gif

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-04771-9_31/477029_1_En_31_IEq156_HTML.gif

denotes the inverse rule. For

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-04771-9_31/477029_1_En_31_IEq157_HTML.gif

with intermediate graph \(K'\),

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-04771-9_31/477029_1_En_31_IEq159_HTML.gif

is the derived rule.

A morphism

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-04771-9_31/477029_1_En_31_IEq239_HTML.gif

is edge-increasing, if \(|E_C|>|E_A|\).

The requirement \(A\not =\emptyset \) in Theorem 2 cannot be deleted: for the unsatisfiable constraint \(\mathrm {\not \exists \,}C\wedge \mathrm {\exists \,}C\), there is no repair program.

For a rule

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-04771-9_31/477029_1_En_31_IEq492_HTML.gif

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-04771-9_31/477029_1_En_31_IEq493_HTML.gif

denotes the rule

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-04771-9_31/477029_1_En_31_IEq494_HTML.gif

[BET12]

Biermann, E., Ermel, C., Taentzer, G.: Formal foundation of consistent EMF model transformations by algebraic graph transformation. Softw. Syst. Model. 11(2), 227–250 (2012)CrossRef

[EEGH15]

Ehrig, H., Ermel, C., Golas, U., Hermann, F.: Graph and Model Transformation - General Framework and Applications. Monographs in Theoretical Computer Science. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47980-3CrossRefMATH

[EEPT06]

Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamentals of Algebraic Graph Transformation. EATCS Monographs of Theoretical Computer Science. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-31188-2CrossRefMATH

[HP09]

Habel, A., Pennemann, K.-H.: Correctness of high-level transformation systems relative to nested conditions. Math. Struct. Comput. Sci. 19, 245–296 (2009)MathSciNetCrossRef

[HS18]

Habel, A., Sandmann, C.: Graph repair by graph programs. In: Graph Computation Models (GCM 2018), Electronic Pre-Proceedings (2018). https://www.gcm2018.uni-bremen.de/assets/gcm_2018_paper_5.pdf

[Löw93]

Löwe, M.: Algebraic approach to single-pushout graph transformation. Theor. Comput. Sci. 109, 181–224 (1993)MathSciNetCrossRef

[MGC13]

Macedo, N., Guimarães, T., Cunha, A.: Model repair and transformation with echo. In: Automated Software Engineering (ASE 2013), pp. 694–697. IEEE (2013)

[NEF03]

Nentwich, C., Emmerich, W., Finkelstein, A.: Consistency management with repair actions. In: Software Engineering, pp. 455–464. IEEE Computer Society (2003)

[NKR17]

Nassar, N., Kosiol, J., Radke, H.: Rule-based repair of EMF models: formalization and correctness proof. In: Graph Computation Models (GCM 2017) (2017). https://www.uni-marburg.de/fb12/arbeitsgruppen/swt/forschung/publikationen/2017/NKR17.pdf

[Pen09]

Pennemann, K.-H.: Development of correct graph transformation systems. Ph.D. thesis, Universität Oldenburg (2009)

[PP12]

Poskitt, C.M., Plump, D.: Hoare-style verification of graph programs. Fundamenta Informaticae 118(1–2), 135–175 (2012)MathSciNetMATH

[PP13]

Poskitt, C.M., Plump, D.: Verifying total correctness of graph programs. Electron. Commun. EASST 61 (2013)

[PSM15]

Puissant, J.P., Van Der Straeten, R., Mens, T.: Resolving model inconsistencies using automated regression planning. Softw. Syst. Model. 14(1), 461–481 (2015)CrossRef

[SLO18]

Schneider, S., Lambers, L., Orejas, F.: Automated reasoning for attributed graph properties. Int. J. Softw. Tools Technol. Transf. 20, 705–737 (2018)CrossRef

Title: Graph Repair by Graph Programs
Authors: Annegret Habel
Christian Sandmann
Publisher: Springer International Publishing
Book: Software Technologies: Applications and Foundations
Print ISBN: 978-3-030-04770-2

Electronic ISBN: 978-3-030-04771-9

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-04771-9_31

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner