A Decidable Equivalence for a Turing-Complete, Distributed Model of Computation
| Autor: | Cesco, Arnaldo, Gorrieri, Roberto |
|---|---|
| Přispěvatelé: | Bonchi, Filippo and Puglisi, Simon J., Arnaldo Cesco, Roberto Gorrieri |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science 68Q85 Theory of computation → Distributed computing models Petri nets Inhibitor arc Bisimulation Decidability Petri nets Inhibitor arc Behavioral equivalence Bisimulation Decidability Behavioral equivalence F.1.1 Logic in Computer Science (cs.LO) |
| DOI: | 10.4230/lipics.mfcs.2021.28 |
| Popis: | Place/Transition Petri nets with inhibitor arcs (PTI nets for short), which are a well-known Turing-complete, distributed model of computation, are equipped with a decidable, behavioral equivalence, called pti-place bisimilarity, that conservatively extends place bisimilarity defined over Place/Transition nets (without inhibitor arcs). We prove that pti-place bisimilarity is sensible, as it respects the causal semantics of PTI nets. Comment: arXiv admin note: substantial text overlap with arXiv:2104.01392 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|