Transition Systems from Casual Reversible Prime Event Structures
Article's language
Russian
Abstract
Reversible computing is a new paradigm that extends the traditional forwards-only computing mode with the ability to execute in backwards, so that computation can run in reverse as easily as in forward. Event structures are a well-established model in concurrency theory and so they are widely used to establish relationships between different models. Two approaches to developing transition system (automaton-like) semantics for event structure models are distinguished in the literature. In the first case, states are considered as configurations (sets of already executed events), and transitions between states are built by starting from the initial configuration and repeatedly adding executable events. In the second approach, states are understood as residuals (model fragments that have not yet been executed), and transitions are created as residual structures are built. The present paper focuses on an investigation of how the two approaches are interrelated for the model of prime event structures extended with causal reversibility. The bisimilarity of the resulting transition systems is proved, taking into account step semantics of the model under consideration.
Keywords
Pages
59-90
File
grib_virb_causal-rpes_si2024.pdf502.14 KB
Number