Rooted Graph Programs
Detlef Plump, Christopher Bak
2024White Rose Research Online (University of Leeds, The University of Sheffield, University of York)21 citationsDOIOpen Access PDF
Abstract
We present an approach for programming with graph transformation rules in which programs can be as efficient as programs in imperative languages. The basic idea is to equip rules and host graphs with distinguished nodes, so-called roots, and to match roots in rules with roots in host graphs. This enables graph transformation rules to be matched in constant time, provided that host graphs have a bounded node degree (which in practice is often the case). Hence, for example, programs with a linear bound on the number of rule applications run in truly linear time. We demonstrate the feasibility of this approach with a case study in graph colouring.
Topics & Concepts
Computer scienceGraphGraph rewritingBounded functionTheoretical computer scienceHost (biology)Node (physics)MathematicsEcologyEngineeringMathematical analysisBiologyStructural engineeringModel-Driven Software Engineering TechniquesFormal Methods in VerificationSoftware Testing and Debugging Techniques