Activation diagrams as a tool for generating consistency-preserving graph transformation rules: the case of product-line configuration with Acapulco


Graph transformations that change a graph while preserving consistency wrt a given set of constraints are an important type of transformation in many areas. For example, in search-based optimisation over graphs, aiming to find graph structures (e.g., models) that are optimal wrt some given objective functions, we need to be able to make changes to a graph without introducing violations of consistency constraints so that we can ensure to only generate feasible solutions. However, writing graph-transformation rules that ensure consistency-preservation while still allowing change to the graph is difficult: A change to the graph may introduce a constraint violation and, therefore, the rule must include components that repair any such new violations. Any such repair has the potential to introduce new constraint violations itself and, therefore, the number of potential repair paths to follow can quickly explode exponentially in size.
In this talk, I present work addressing these challenges in the context of optimal product-line configuration. We introduce a new data structure – feature-activation diagrams – to capture the dependencies between changes and use this to efficiently derive consistency-preserving graph transformation rules encoded as variability-based rules. The rules we generate allow us to solve existing benchmarks for product-line configuration more efficiently than the state of the art and find more optimal configurations.

Friday, December 16, 2022 15:00 Europe/Paris
GReTA seminar
Zoom registration: click here! Please consider joining the meeting already within the 15min prior to the start of the seminar to ensure your setup is functioning properly. You may connect with either the Zoom web or Zoom desktop clients.

Please note that the meeting will be recorded and live-streamed to YouTube:

Steffen Zschaler
Steffen Zschaler
Reader in Computer Science

Steffen Zschaler is a Reader in Software Engineering and Deputy Head of Department (Education) at the Department of Informatics at King’s College London, and a Visiting Scientist at the Francis Crick Institute. He is a member of the Software Systems (SSY) group. He also directs MDENet: the expert network for model-driven engineering. His research focuses on model-driven engineering, in particular on formal foundations for modularity of models and (executable) domain-specific modelling languages, using graph-transformations to enable evolutionary search over models to solve multi-objective model optimisation problems, and on applications of model-driven engineering, including in non-technical domains.