2017/05/10 by Hannah Arndt, Arndt, Hannah, Christina Jansen +5
Computer Science · #FOS: Computer and information sciences #Graph Theory and Algorithms #Model-Driven Software Engineering Techniques #Programming Languages (cs.PL) #Software Engineering Research
paper · pdf · doi:10.48550/arxiv.1705.03754
openalex publication_date 2017/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We develop a shape analysis for reasoning about relational properties of data structures. Both the concrete and the abstract domain are represented by hypergraphs. The analysis is parameterized by user-supplied indexed graph grammars to guide concretization and abstraction. This novel extension of context-free graph grammars is powerful enough to model complex data structures such as balanced binary trees with parent pointers, while preserving most desirable properties of context-free graph grammars. One strength of our analysis is that no artifacts apart from grammars are required from the user; it thus offers a high degree of automation. We implemented our analysis and successfully applied it to various programs manipulating AVL trees, (doubly-linked) lists, and combinations of both.