Learning Minimal and Maximal Rules from Observations of Graph Transformations

Abstract: Graph transformations have been used to model services and systems where rules describe pre and post conditions of operations changing a complex state. However, despite their intuitive nature, creating such models is a time-consuming and error-prone process. In this paper we investigate the possibility of extracting rules from observations of transformations, i.e., pairs of input and output graphs re-sulting from successful transformations and individual input graphs were they have failed. From such positive and negative examples, minimal rules are extracted, to be extended by context that is present in all positive examples and missing in at least one negative example. The result is are a maximal and a required rule, jointly with the minimal rule defining the range of possible rules that could have created the ob-served transformations. We report on an implementation of the approach, evaluate its accuracy, scalability and limitations, and discuss applications to reverse engi-neering visual constructs from observations of object states of components under test