Talk "Unfolding conditional and attributed graph grammars - Towards efficient solutions to combinatorial graph computation problems"

by Reiko Heckel

Sun, 07 April 2019 at 11:00 am in Prague, Czech Republic

Joint work with: Andrea Corradini, Maryam Ghaffari Saadat, Fernando Orejas

Abstract: In a graph computation problem, for a given attributed input graph, any output graph produced by a non-deterministic graph transformation represents a solution subject to constraints and optimisation. Non-deterministic graph computations require search and backtracking. Due to infinite or large data types, attributes increase the degree of non-determinism dramatically, making a search-based approach impractical. We propose to use unfolding of graph grammars to address graph computation problems efficiently and systematically. An unfolding gives a compact representations of the derivation tree of a graph grammar, capturing the dependencies and conflicts between rule occurrences rather than explicit states and derivations. We extend the notion of unfolding to lazy symbolic attributed graph transformations, where attribute checks and computations are represented by symbolic constraints for delayed evaluation. We provide a mechanism to designing correct algorithms that first compute the unfolding of the underlying un-attributed grammar, then aggregate the constraints to use external tools, such as linear and finite domain constraint solvers, to implement attribute computations and optimisation problems. We illustrate the approach using a simple network optimisation problem, choosing the best topology and bandwidth allocation to serve the needs of all clients and balance server utilisation.