A canonical string encoding for pure bigraphs
Research output: Contribution to journal › Research article › Contributed › peer-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 language | English |
---|---|
Article number | 246 |
Number of pages | 14 |
Journal | SN Computer Science |
Volume | 2 |
Issue number | 4 |
Publication status | Published - 30 Apr 2021 |
Peer-reviewed | Yes |
External IDs
Scopus | 85131801491 |
---|---|
ORCID | /0000-0001-6334-2356/work/168719934 |
ORCID | /0000-0002-3513-6448/work/168720176 |
Keywords
ASJC Scopus subject areas
Keywords
- Bigraph matching, Bigraphs, Canonical labeling, Isomorphism test, String encoding