Loose Graph Simulations

Alessio Mansutti; Marino Miculan; Marco Peressotti

doi:10.1007/978-3-319-74730-9_9

Loose Graph Simulations

Alessio Mansutti, Marino Miculan, Marco Peressotti

Department of Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

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

Original language	English
Title of host publication	Software Technologies: Applications and Foundations : STAF 2017 Collocated Workshops, Marburg, Germany, July 17-21, 2017, Revised Selected Papers
Editors	Martina Seidl, Steffen Zschaler
Publisher	Springer
Publication date	2018
Pages	109-126
ISBN (Print)	978-3-319-74729-3
ISBN (Electronic)	978-3-319-74730-9
DOIs	https://doi.org/10.1007/978-3-319-74730-9_9
Publication status	Published - 2018
Event	Software Technologies: Applications and Foundations Conference - Marburg, Germany Duration: 17. Jul 2017 → 21. Jul 2017

Conference

Conference	Software Technologies: Applications and Foundations Conference
Country/Territory	Germany
City	Marburg
Period	17/07/2017 → 21/07/2017

Series	Lecture Notes in Computer Science
Volume	10748
ISSN	0302-9743

Series	Programming and Software Engineering
Volume	10748

Keywords

Graph theory
Graph transformation
Complexity
Graph Isomorphism
Formal graph languages

Documents & Links

10.1007/978-3-319-74730-9_9

https://arxiv.org/pdf/1705.08241

1 Working paper

Loose Graph Simulations
Mansutti, A., Miculan, M. & Peressotti, M., 23. May 2017.
Research output: Working paper › Research

Cite this

Mansutti, Alessio ; Miculan, Marino ; Peressotti, Marco. / Loose Graph Simulations. Software Technologies: Applications and Foundations: STAF 2017 Collocated Workshops, Marburg, Germany, July 17-21, 2017, Revised Selected Papers. editor / Martina Seidl ; Steffen Zschaler. Springer, 2018. pp. 109-126 (Lecture Notes in Computer Science, Vol. 10748). (Programming and Software Engineering, Vol. 10748).

@inproceedings{e3dfd36efe984d68a0b23e4eae97cb3c,

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 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.",

keywords = "Graph theory, Graph transformation, Complexity, Graph Isomorphism, Formal graph languages",

author = "Alessio Mansutti and Marino Miculan and Marco Peressotti",

year = "2018",

doi = "10.1007/978-3-319-74730-9_9",

language = "English",

isbn = "978-3-319-74729-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "109--126",

editor = "Martina Seidl and Steffen Zschaler",

booktitle = "Software Technologies: Applications and Foundations",

address = "Germany",

note = "Software Technologies: Applications and Foundations Conference, STAFF ; Conference date: 17-07-2017 Through 21-07-2017",

}

Mansutti, A, Miculan, M & Peressotti, M 2018, Loose Graph Simulations. in M Seidl & S Zschaler (eds), Software Technologies: Applications and Foundations: STAF 2017 Collocated Workshops, Marburg, Germany, July 17-21, 2017, Revised Selected Papers. Springer, Lecture Notes in Computer Science, vol. 10748, Programming and Software Engineering, vol. 10748, pp. 109-126, Software Technologies: Applications and Foundations Conference, Marburg, Hesse, Germany, 17/07/2017. https://doi.org/10.1007/978-3-319-74730-9_9

Loose Graph Simulations. / Mansutti, Alessio; Miculan, Marino; Peressotti, Marco.
Software Technologies: Applications and Foundations: STAF 2017 Collocated Workshops, Marburg, Germany, July 17-21, 2017, Revised Selected Papers. ed. / Martina Seidl; Steffen Zschaler. Springer, 2018. p. 109-126 (Lecture Notes in Computer Science, Vol. 10748). (Programming and Software Engineering, Vol. 10748).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Loose Graph Simulations

AU - Mansutti, Alessio

AU - Miculan, Marino

AU - Peressotti, Marco

PY - 2018

Y1 - 2018

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

KW - Graph theory

KW - Graph transformation

KW - Complexity

KW - Graph Isomorphism

KW - Formal graph languages

U2 - 10.1007/978-3-319-74730-9_9

DO - 10.1007/978-3-319-74730-9_9

M3 - Article in proceedings

SN - 978-3-319-74729-3

T3 - Lecture Notes in Computer Science

SP - 109

EP - 126

BT - Software Technologies: Applications and Foundations

A2 - Seidl, Martina

A2 - Zschaler, Steffen

PB - Springer

T2 - Software Technologies: Applications and Foundations Conference

Y2 - 17 July 2017 through 21 July 2017

ER -

Mansutti A, Miculan M, Peressotti M. Loose Graph Simulations. In Seidl M, Zschaler S, editors, Software Technologies: Applications and Foundations: STAF 2017 Collocated Workshops, Marburg, Germany, July 17-21, 2017, Revised Selected Papers. Springer. 2018. p. 109-126. (Lecture Notes in Computer Science, Vol. 10748). (Programming and Software Engineering, Vol. 10748). doi: 10.1007/978-3-319-74730-9_9

Loose Graph Simulations

Abstract

Conference

Keywords

Documents & Links

Fingerprint

Related research output

Loose Graph Simulations

Cite this