Loose Graph Simulations

Alessio Mansutti, Marino Miculan, Marco Peressotti

Publikation: Working paperForskning

Resumé

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 a 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.
OriginalsprogEngelsk
StatusUdgivet - 23. maj 2017

Fingeraftryk

Graph in graph theory
Regular Languages
Pattern Matching
Simulation
Subgraph
Isomorphism
Unification
Intuitive
Express
NP-complete problem
Polynomial

Citer dette

Mansutti, A., Miculan, M., & Peressotti, M. (2017). Loose Graph Simulations.
Mansutti, Alessio ; Miculan, Marino ; Peressotti, Marco. / Loose Graph Simulations. 2017.
@techreport{7a8f3c29ee404f9787946d6168a522e7,
title = "Loose Graph Simulations",
abstract = "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 a 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.",
author = "Alessio Mansutti and Marino Miculan and Marco Peressotti",
year = "2017",
month = "5",
day = "23",
language = "English",
type = "WorkingPaper",

}

Mansutti, A, Miculan, M & Peressotti, M 2017 'Loose Graph Simulations'.

Loose Graph Simulations. / Mansutti, Alessio; Miculan, Marino; Peressotti, Marco.

2017.

Publikation: Working paperForskning

TY - UNPB

T1 - Loose Graph Simulations

AU - Mansutti, Alessio

AU - Miculan, Marino

AU - Peressotti, Marco

PY - 2017/5/23

Y1 - 2017/5/23

N2 - 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 a 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.

AB - 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 a 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.

M3 - Working paper

BT - Loose Graph Simulations

ER -

Mansutti A, Miculan M, Peressotti M. Loose Graph Simulations. 2017 maj 23.