2019/06/11 by Graham Campbell, Campbell, Graham
Computer Science · #68Q25 #68Q42 #Computational Complexity (cs.CC) #F.2.2 #F.4.2 #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Model-Driven Software Engineering Techniques #Programming Languages (cs.PL) #Software Testing and Debugging Techniques #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1906.05170
openalex publication_date 2019/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graph transformation is the rule-based modification of graphs, and is a discipline dating back to the 1970s. The declarative nature of graph rewriting rules comes at a cost. In general, to match the left-hand graph of a fixed rule within a host graph requires polynomial time. To improve matching performance, Dörr proposed to equip rules and host graphs with distinguished root nodes. This model was implemented by Plump and Bak, but unfortunately, is not invertible. We address this problem by defining rootedness using a partial function onto a two-point set rather than pointing graphs with root nodes. We show a new result that the graph class of trees can be recognised by a rooted GT system in linear time, given an input graph of bounded degree. Finally, we define a new notion of confluence modulo garbage and non-garbage critical pairs, showing it is sufficient to require strong joinability of only the non-garbage critical pairs to establish confluence modulo garbage.