<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>9322</REFNUM><AUTHORS><AUTHOR>Sevegnani,M.</AUTHOR><AUTHOR>Unsworth,C.</AUTHOR><AUTHOR>Calder,M.</AUTHOR></AUTHORS><YEAR>2010</YEAR><TITLE>A SAT based algorithm for the matching problem in bigraphs with sharing</TITLE><PLACE_PUBLISHED>DCS Technical Report Series</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><ISBN>TR-2010-311</ISBN><LABEL>Sevegnani:2010:9322</LABEL><KEYWORDS><KEYWORD>bigraph</KEYWORD></KEYWORDS<ABSTRACT>Bigraphical reactive systems are a formalism for modelling mobile computation. A bigraph consists of a place graph and a link graph; reaction rules define how place and link graphs evolve. Bigraphs originally supported only tree structures as place graphs, we have extended the formalism to bigraphs with sharing, which allow directed acyclic graphs as place graphs. A major challenge for bigraph tool support (with or without sharing) is defining bigraph matching and providing an efficient algorithm. In the case of bigraphs with sharing, place graph matching is a special case of the NP-complete, sub-graph isomorphism problem. We present the details of place graph matching and give a sound and complete, efficient algorithm in SAT.</ABSTRACT></RECORD></RECORDS></XML>