Graph consistency as a graduated property. Consistency-sustaining and -improving graph transformations

DOI10.1007/978-3-030-51372-6_14MaRDI QIDQ5100736zbMATHOpenAlexFDO

Authors Jens Kosiol, Steffen Zschaler, Daniel Strüber, Gabriele Taentzer

Publication date 1 September 2022

Published in Graph Transformation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.04162

zbMATH Keywords

evolutionary searchgraph transformation systemsgraph consistencygraph repair

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Abstract: Where graphs are used for modelling and specifying systems, consistency is an important concern. To be a valid model of a system, the graph structure must satisfy a number of constraints. To date, consistency has primarily been viewed as a binary property: a graph either is or is not consistent with respect to a set of graph constraints. This has enabled the definition of notions such as constraint-preserving and constraint-guaranteeing graph transformations. Many practical applications - for example model repair or evolutionary search - implicitly assume a more graduated notion of consistency, but without an explicit formalisation only limited analysis of these applications is possible. In this paper, we introduce an explicit notion of consistency as a graduated property, depending on the number of constraint violations in a graph. We present two new characterisations of transformations (and transformation rules) enabling reasoning about the gradual introduction of consistency: while consistency-sustaining transformations do not decrease the consistency level, consistency-improving transformations strictly reduce the number of constraint violations. We show how these new definitions refine the existing concepts of constraint-preserving and constraint-guaranteeing transformations. To support a static analysis based on our characterisations, we present criteria for deciding which form of consistency ensuring transformations is induced by the application of a transformation rule. We illustrate our contributions in the context of an example from search-based model engineering.

Recommendations

• scientific article; zbMATH DE number 1231489
• A Logic of Graph Constraints
• Constructing constraint-preserving interaction schemes in adhesive categories
• Reasoning with graph constraints
• Preserving consistency in geometric modeling with graph transformations

Cites work

• scientific article; zbMATH DE number 7453090 (Why is no real title available?)
• scientific article; zbMATH DE number 7456054 (Why is no real title available?)
• Constructing constraint-preserving interaction schemes in adhesive categories
• Constructing optimized validity-preserving application conditions for graph transformation rules
• Correctness of high-level transformation systems relative to nested conditions
• Fundamentals of algebraic graph transformation
• Granularity of conflicts and dependencies in graph transformation systems: a two-dimensional approach
• Helper-objectives: Using multi-objective evolutionary algorithms for single-objective optimisation
• Processes, Terms and Cycles: Steps on the Road to Infinity
• \(k\)-inductive invariant checking for graph transformation systems

Cited in

(5)

• A Logic of Graph Constraints
• Finding the right way to Rome: effect-oriented graph transformation
• Schema compliant consistency management via triple graph grammars and integer linear programming
• scientific article; zbMATH DE number 7456048 (Why is no real title available?)
• Preserving consistency in geometric modeling with graph transformations

Describes a project that uses

Uses Software

• Henshin
• MDEOptimiser

This page was built for publication: Graph consistency as a graduated property. Consistency-sustaining and -improving graph transformations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5100736)