On Decidability of Bigraphical Sortings

Giorgio Bacci, Davide Grohmann

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

242 Downloads (Pure)

Abstract

Bigraphs are a general framework for mobile, concurrent, and communicating systems. They have been shown to be suitable for representing several process calculi formalisms, but despite their expressive power, in many cases some disciplines on the structure of bigraphs are needed to faithfully encode the computational model at hand. Sortings have been proposed as an abstract technique to discipline bigraphs.
In this paper, we study the decidability problem of bigraphical sorting: to decide whether a bigraph belongs to some sorted bigraph category. Whilst the general problem is undecidable, we propose a decidable sub-class of bigraphical sortings, named match predicate sortings, which are expressive enough to capture homomorphic sortings and local bigraphs.
Original languageEnglish
Title of host publicationCTIT Workshop Proceedings WP 2010-05
Publication date2010
Pages33-47
Publication statusPublished - 2010
Externally publishedYes
EventWorkshop on Graph Computation Models - Enschede, Netherlands
Duration: 2 Oct 20102 Oct 2010
Conference number: 3

Workshop

WorkshopWorkshop on Graph Computation Models
Number3
Country/TerritoryNetherlands
CityEnschede
Period02/10/201002/10/2010

Fingerprint

Dive into the research topics of 'On Decidability of Bigraphical Sortings'. Together they form a unique fingerprint.

Cite this