1 December 2020 in Future Generation Computer Systems
LDLúcia Maria de A. Drummond
Lúcia Maria de A. Drummond
25 April 2014 in Logic Journal of the IGPL
Propositional Dynamic Logic (PDL) is a multi-modal logic used for specifying and reasoning on sequential programs. Petri Net is a widely used formalism to specify and to analyse concurrent programs with a very nice graphical representation. In this work, we propose a PDL to reasoning about Petri Nets. First we define a compositional encoding of Petri Nets from basic nets as terms. Second, we use these terms as PDL programs and provide a compositional semantics to PDL Formulas. Finally, we present an axiomatization and prove completeness w.r.t. our semantics. The advantage of our approach is that we can do reasoning about Petri Nets using our dynamic logic and we do not need to to translate it to other formalisms. Moreover our approach is compositional allowing for construction of complex nets using basic ones.
1 July 2014 in Electronic Notes in Theoretical Computer Science
EHEdward Hermann Haeusler
Propositional Dynamic Logic (PDL) is a multi-modal logic used for specifying and reasoning on sequential programs. Petri Nets is a widely used formalism to specify and analyze concurrent programs with a very intuitive graphical representation. Petri-PDL is an extension of PDL, whose programs are Petri Nets, which combines the advantages of both formalisms using a compositional and structural approach to deal with Petri Nets.In this work we present an extension of Petri-PDL to deal with Stochastic Petri Nets, the DS3 logic. This system is an alternative to model performance evaluation in a compositional and structural approach. We discuss about its soundness, decidability and completeness regarding our semantics and present a proof of EXPTime-completeness of its SAT problem. A usage example is presented
21 May 2024 in Journal of Logic and Computation
Guarded Kleene Algebra with Tests (GKAT) was presented as a fragment of KAT to abstract imperative programming languages, where only if-then-else and while-do statements are allowed in the language. The loss of expressiveness is, nevertheless, compensated by a clear advantage over KAT: it allows almost linear decidability of program equivalence. In this work, we give the first step to optimizing the complexity of dynamic logic equivalence, which is EXPTIME-complete in propositional dynamic logic (PDL). First, and based on strict deterministic PDL, we present guarded propositional dynamic logic (GPDL), a fragment of PDL where programs correspond to GKAT terms. It comes embedded, as expected, with a semantics over relational models and a sound axiomatisation. Then, we present a Natural Deduction system for GPDL, proving its soundness and completeness, concerning the axiomatisation. Based on Smolka et al. (2019, Proceedings of the ACM Programming Language 4), we obtain the main result of this work—the equivalence of GPDL programs can be established in almost linear time.
28 February 2025 in Concurrency and Computation: Practice and Experience
1 April 2015 in Electronic Notes in Theoretical Computer Science
EHEdward Hermann Haeusler
Petri Nets are a widely used formalism to deal with concurrent systems. Dynamic Logics (DL) are a family of modal logics where each modality corresponds to a program. This works presents a resolution-based method for Petri-PDL, a DL where programs are replaced by Petri Nets. We present a procedure to convert any Petri-PDL formula into a normal form, a set of resolution-based inference rules, examples of application of the method, and discuss soundness and completeness