2017/05/23 by Alessio Mansutti, Marino Miculan, Mansutti, Alessio +3
Computer Science · #F.2.2 #FOS: Computer and information sciences #Formal Methods in Verification #G.2.2 #Graph Theory and Algorithms #Logic in Computer Science (cs.LO) #Model-Driven Software Engineering Techniques
paper · pdf · doi:10.48550/arxiv.1705.08241
openalex publication_date 2017/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce loose graph simulations (LGS), a new notion about labelled graphs which subsumes in an intuitive and natural way subgraph isomorphism (SGI), regular language pattern matching (RLPM) and graph simulation (GS). Being a unification of all these notions, LGS allows us to express directly also problems which are "mixed" instances of previous ones, and hence which would not fit easily in any of them. After the definition and some examples, we show that the problem of finding loose graph simulations is NP-complete, we provide formal translation of SGI, RLPM, and GS into LGSs, and we give the representation of a problem which extends both SGI and RLPM. Finally, we identify a subclass of the LGS problem that is polynomial.