A canonical string encoding for pure bigraphs

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

Abstract

The bigraph theory, devised by Robin Milner, is a recent mathematical framework for concurrent processes. Its generality is able to subsume many existing process calculi, for example, CCS, CSP, and Petri nets. Further, it provides a uniform proof of bisimilarity, which is a congruence. We present the first canonical string encoding for pure and lean bigraphs by lifting the breadth-first canonical form of rooted unordered trees to a unique representation for bigraphs up to isomorphism (i.e., lean-support equivalence). The encoding’s applicability is limited to atomic alphabets. The time complexity is O(n2kdlogd), where n is the number of places, d the degree of the place graph and k the maximum arity of a bigraph’s signature. We provide proof of the correctness of our method and also conduct experimental measurements to assess the complexity.

Details

Original languageEnglish
Article number246
Number of pages14
JournalSN Computer Science
Volume2
Issue number4
Publication statusPublished - 30 Apr 2021
Peer-reviewedYes

External IDs

Scopus 85131801491