Reversing Place Transition Nets
Petri nets are a well-known model of concurrency and provide an ideal setting for the study of fundamental aspects in concurrent systems. Despite their simplicity, they still lack a satisfactory causally reversible semantics. We develop such semantics for Place/Transitions Petri nets (P/T nets) base...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2020-10-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/5831/pdf |
| _version_ | 1827322705197662208 |
|---|---|
| author | Hernán Melgratti Claudio Antares Mezzina Irek Ulidowski |
| author_facet | Hernán Melgratti Claudio Antares Mezzina Irek Ulidowski |
| author_sort | Hernán Melgratti |
| collection | DOAJ |
| description | Petri nets are a well-known model of concurrency and provide an ideal setting
for the study of fundamental aspects in concurrent systems. Despite their
simplicity, they still lack a satisfactory causally reversible semantics. We
develop such semantics for Place/Transitions Petri nets (P/T nets) based on two
observations. Firstly, a net that explicitly expresses causality and conflict
among events, for example an occurrence net, can be straightforwardly reversed
by adding a reverse transition for each of its forward transitions. Secondly,
given a P/T net the standard unfolding construction associates with it an
occurrence net that preserves all of its computation. Consequently, the
reversible semantics of a P/T net can be obtained as the reversible semantics
of its unfolding. We show that such reversible behaviour can be expressed as a
finite net whose tokens are coloured by causal histories. Colours in our
encoding resemble the causal memories that are typical in reversible process
calculi. |
| first_indexed | 2024-04-25T01:34:06Z |
| format | Article |
| id | doaj.art-0c426f1da0b44a06ab2bc8a7b295ac93 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:34:06Z |
| publishDate | 2020-10-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-0c426f1da0b44a06ab2bc8a7b295ac932024-03-08T10:32:05ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742020-10-01Volume 16, Issue 410.23638/LMCS-16(4:5)20205831Reversing Place Transition NetsHernán MelgrattiClaudio Antares MezzinaIrek UlidowskiPetri nets are a well-known model of concurrency and provide an ideal setting for the study of fundamental aspects in concurrent systems. Despite their simplicity, they still lack a satisfactory causally reversible semantics. We develop such semantics for Place/Transitions Petri nets (P/T nets) based on two observations. Firstly, a net that explicitly expresses causality and conflict among events, for example an occurrence net, can be straightforwardly reversed by adding a reverse transition for each of its forward transitions. Secondly, given a P/T net the standard unfolding construction associates with it an occurrence net that preserves all of its computation. Consequently, the reversible semantics of a P/T net can be obtained as the reversible semantics of its unfolding. We show that such reversible behaviour can be expressed as a finite net whose tokens are coloured by causal histories. Colours in our encoding resemble the causal memories that are typical in reversible process calculi.https://lmcs.episciences.org/5831/pdfcomputer science - logic in computer sciencecomputer science - formal languages and automata theory |
| spellingShingle | Hernán Melgratti Claudio Antares Mezzina Irek Ulidowski Reversing Place Transition Nets Logical Methods in Computer Science computer science - logic in computer science computer science - formal languages and automata theory |
| title | Reversing Place Transition Nets |
| title_full | Reversing Place Transition Nets |
| title_fullStr | Reversing Place Transition Nets |
| title_full_unstemmed | Reversing Place Transition Nets |
| title_short | Reversing Place Transition Nets |
| title_sort | reversing place transition nets |
| topic | computer science - logic in computer science computer science - formal languages and automata theory |
| url | https://lmcs.episciences.org/5831/pdf |
| work_keys_str_mv | AT hernanmelgratti reversingplacetransitionnets AT claudioantaresmezzina reversingplacetransitionnets AT irekulidowski reversingplacetransitionnets |