Loose Graph Simulations

Alessio Mansutti, Marino Miculan, Marco Peressotti

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer 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.
OriginalsprogEngelsk
TitelSoftware Technologies: Applications and Foundations : STAF 2017 Collocated Workshops, Marburg, Germany, July 17-21, 2017, Revised Selected Papers
RedaktørerMartina Seidl, Steffen Zschaler
ForlagSpringer
Publikationsdato2018
Sider109-126
ISBN (Trykt)978-3-319-74729-3
ISBN (Elektronisk)978-3-319-74730-9
DOI
StatusUdgivet - 2018
BegivenhedSoftware Technologies: Applications and Foundations Conference - Marburg, Tyskland
Varighed: 17. jul. 201721. jul. 2017

Konference

KonferenceSoftware Technologies: Applications and Foundations Conference
Land/OmrådeTyskland
ByMarburg
Periode17/07/201721/07/2017
NavnLecture Notes in Computer Science
Vol/bind10748
ISSN0302-9743
NavnProgramming and Software Engineering
Vol/bind10748

Fingeraftryk

Dyk ned i forskningsemnerne om 'Loose Graph Simulations'. Sammen danner de et unikt fingeraftryk.

Citationsformater