A canonical string encoding for pure bigraphs
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
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
Originalsprache | Englisch |
---|---|
Aufsatznummer | 246 |
Seitenumfang | 14 |
Fachzeitschrift | SN Computer Science |
Jahrgang | 2 |
Ausgabenummer | 4 |
Publikationsstatus | Veröffentlicht - 30 Apr. 2021 |
Peer-Review-Status | Ja |
Externe IDs
Scopus | 85131801491 |
---|---|
ORCID | /0000-0001-6334-2356/work/168719934 |
ORCID | /0000-0002-3513-6448/work/168720176 |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Bigraph matching, Bigraphs, Canonical labeling, Isomorphism test, String encoding