Bisimilarity and Simulatability of Processes Parameterized by Join Interactions
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908494641233920 |
|---|---|
| author | Grabmayer, Clemens Murgia, Maurizio |
| author_facet | Grabmayer, Clemens Murgia, Maurizio |
| contents | Departing from Larsen's concept of parameterized bisimilarity of processes with respect to interaction with environments, we start an exploration of its natural weakening: bisimilarity of unrestricted join interactions with environments. Parameterized bisimilarity relates processes p and q with respect to an environment e if p and q behave bi-similarly while joining -- respectively the same -- transitions from e. The weakened variant relates processes p and q with respect to environment e if the join-interaction processes p & e and q & e of p and q with e are bisimilar. (Hereby join interactions r & f facilitate a step with label a to r' & f' if and only if r and f permit a-steps to r' and f' , respectively.) Join-interaction parameterized (ji-parameterized) bisimilarity coincides with parameterized bisimilarity for deterministic environments, but that it is a coarser equivalence in general. We explain how Larsen's concept can be recovered from ji-parameterized bisimilarity by 'determinizing' interactions. We show that by adaptation to simulatability (simulation preorder) the same concept arises: parameterized simulatability coincides with ji-parameterized simulatability. For the discrimination preorder of (ji-)parameterized simulatability on environments we obtain the same result as Larsen did for parameterized bisimilarity. Also, we give a modal-logic characterization of (ji-)parameterized simulatability. Finally we gather open problems, and provide an outlook on our current related work. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_13611 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bisimilarity and Simulatability of Processes Parameterized by Join Interactions Grabmayer, Clemens Murgia, Maurizio Programming Languages Logic in Computer Science D.3.1; F.3.2 Departing from Larsen's concept of parameterized bisimilarity of processes with respect to interaction with environments, we start an exploration of its natural weakening: bisimilarity of unrestricted join interactions with environments. Parameterized bisimilarity relates processes p and q with respect to an environment e if p and q behave bi-similarly while joining -- respectively the same -- transitions from e. The weakened variant relates processes p and q with respect to environment e if the join-interaction processes p & e and q & e of p and q with e are bisimilar. (Hereby join interactions r & f facilitate a step with label a to r' & f' if and only if r and f permit a-steps to r' and f' , respectively.) Join-interaction parameterized (ji-parameterized) bisimilarity coincides with parameterized bisimilarity for deterministic environments, but that it is a coarser equivalence in general. We explain how Larsen's concept can be recovered from ji-parameterized bisimilarity by 'determinizing' interactions. We show that by adaptation to simulatability (simulation preorder) the same concept arises: parameterized simulatability coincides with ji-parameterized simulatability. For the discrimination preorder of (ji-)parameterized simulatability on environments we obtain the same result as Larsen did for parameterized bisimilarity. Also, we give a modal-logic characterization of (ji-)parameterized simulatability. Finally we gather open problems, and provide an outlook on our current related work. |
| title | Bisimilarity and Simulatability of Processes Parameterized by Join Interactions |
| topic | Programming Languages Logic in Computer Science D.3.1; F.3.2 |
| url | https://arxiv.org/abs/2508.13611 |