Towards Guided Trajectory Exploration of Graph Transformation Systems

Abstract

Graph transformation systems (GTS) are often used for modeling the behavior of complex systems. A common GTS analysis scenario is the exploration of its state space from an initial state to a state adhering to given goals through a proper trajectory. Guided trajectory exploration uses information from some more abstract analysis of the system as hints to reduce the traversed state space. These hints are used to order possible further transitions from a given state (selection) and detect violations early (cut-off), thus pruning unpromising trajectories from the state space. In the current paper, we define cut-off and selection criteria for guiding the trajectory exploration, and use Petri Net analysis results and the dependency relations between rules as hints in our criteria calculation algorithm. The criteria definitions include navigation along dependency relations, various types of ordering for selection and quantifiers for cut-off criteria. Our approach is exemplified on a cloud infrastructure configuration problem.