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