A canonical string encoding for pure bigraphs

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
Aufsatznummer246
Seitenumfang14
FachzeitschriftSN Computer Science
Jahrgang2
Ausgabenummer4
PublikationsstatusVeröffentlicht - 30 Apr. 2021
Peer-Review-StatusJa

Externe IDs

Scopus 85131801491