A Reversible Perspective on Petri Nets and Event Structures

• URL: http://arxiv.org/abs/2312.16714v1
• Date: Wed, 27 Dec 2023 20:47:48 GMT
• Title: A Reversible Perspective on Petri Nets and Event Structures
• Authors: Hern\'an Melgratti, Claudio Antares Mezzina, G. Michele Pinna
• Abstract summary: Event structures have emerged as a foundational model for concurrent computation. Event structures have been extended to address reversibility, where processes can undo previous computations. We introduce a subset of contextual Petri nets, dubbed reversible causal nets, that precisely correspond to reversible prime event structures.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Event structures have emerged as a foundational model for concurrent computation, explaining computational processes by outlining the events and the relationships that dictate their execution. They play a pivotal role in the study of key aspects of concurrent computation models, such as causality and independence, and have found applications across a broad range of languages and models, spanning realms like persistence, probabilities, and quantum computing. Recently, event structures have been extended to address reversibility, where computational processes can undo previous computations. In this context, reversible event structures provide abstract representations of processes capable of both forward and backward steps in a computation. Since their introduction, event structures have played a crucial role in bridging operational models, traditionally exemplified by Petri nets and process calculi, with denotational ones, i.e., algebraic domains. In this context, we revisit the standard connection between Petri nets and event structures under the lenses of reversibility. Specifically, we introduce a subset of contextual Petri nets, dubbed reversible causal nets, that precisely correspond to reversible prime event structures. The distinctive feature of reversible causal nets lies in deriving causality from inhibitor arcs, departing from the conventional dependence on the overlap between the post and preset of transitions. In this way, we are able to operationally explain the full model of reversible prime event structures.

Related papers

• Flow of dynamical causal structures with an application to correlations [0.9208007322096533]
  Causal models capture cause-effect relations both qualitatively - via the graphical causal structure - and quantitatively. Here, we introduce a tool - the flow of causal structures - to visualize and explore the dynamical aspect of classical-deterministic processes.
  arXiv  Detail & Related papers  (2024-10-24T13:40:02Z)
• Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformer [29.970200877158764]
  We investigate the influence of recurrent structures in neural models on their reasoning abilities and computability. We shed light on how the CoT approach can mimic recurrent computation and act as a bridge between autoregression and recurrence.
  arXiv  Detail & Related papers  (2024-09-14T00:30:57Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Advancing Counterfactual Inference through Nonlinear Quantile Regression [77.28323341329461]
  We propose a framework for efficient and effective counterfactual inference implemented with neural networks. The proposed approach enhances the capacity to generalize estimated counterfactual outcomes to unseen data. Empirical results conducted on multiple datasets offer compelling support for our theoretical assertions.
  arXiv  Detail & Related papers  (2023-06-09T08:30:51Z)
• Compositional Probabilistic and Causal Inference using Tractable Circuit Models [20.07977560803858]
  We introduce md-vtrees, a novel structural formulation of (marginal) determinism in structured decomposable PCs. We derive the first polytime algorithms for causal inference queries such as backdoor adjustment on PCs.
  arXiv  Detail & Related papers  (2023-04-17T13:48:16Z)
• Bayesian Recurrent Units and the Forward-Backward Algorithm [91.39701446828144]
  Using Bayes's theorem, we derive a unit-wise recurrence as well as a backward recursion similar to the forward-backward algorithm. The resulting Bayesian recurrent units can be integrated as recurrent neural networks within deep learning frameworks. Experiments on speech recognition indicate that adding the derived units at the end of state-of-the-art recurrent architectures can improve the performance at a very low cost in terms of trainable parameters.
  arXiv  Detail & Related papers  (2022-07-21T14:00:52Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test. We train a variational inference model to predict the causal structure from observational/interventional data. Our models exhibit robust generalization capabilities under substantial distribution shift.
  arXiv  Detail & Related papers  (2022-05-25T17:37:08Z)
• Acyclic and Cyclic Reversing Computations in Petri Nets [0.0]
  reversible computations constitute an unconventional form of computing where any sequence of performed operations can be undone by executing in reverse order at any point during a computation. We have proposed a structural way of translating Reversing Petri Nets (RPNs) to bounded Coloured Petri Nets (CPNs) Three reversing semantics are possible in RPNs: backtracking (reversing of the lately executed action), causal reversing (action can be reversed only when all its effects have been undone) and out of causal reversing (any previously performed action can be reversed)
  arXiv  Detail & Related papers  (2021-08-04T16:50:14Z)
• A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries [44.36335714431731]
  We show how complex inference scenarios for machine learning can be represented in terms of tractable modular operations over circuits. We derive a unified framework for reasoning about tractable models that generalizes several results in the literature and opens up novel tractable inference scenarios.
  arXiv  Detail & Related papers  (2021-02-11T17:26:32Z)
• Analogous Process Structure Induction for Sub-event Sequence Prediction [111.10887596684276]
  We propose an Analogous Process Structure Induction APSI framework to predict the whole sub-event sequence of previously unseen processes. As our experiments and analysis indicate, APSI supports the generation of meaningful sub-event sequences for unseen processes and can help predict missing events.
  arXiv  Detail & Related papers  (2020-10-16T17:35:40Z)
• Structural Causal Models Are (Solvable by) Credal Networks [70.45873402967297]
  Causal inferences can be obtained by standard algorithms for the updating of credal nets. This contribution should be regarded as a systematic approach to represent structural causal models by credal networks. Experiments show that approximate algorithms for credal networks can immediately be used to do causal inference in real-size problems.
  arXiv  Detail & Related papers  (2020-08-02T11:19:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.