2026-07-25T15:15:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6157 2024-03-06T10:38:28Z ddc:004 open_access

Homogeneous Equations of Algebraic Petri Nets Triebel, Marvin Sürmeli, Jan Algebraic Petri Nets Invariants Linear Equations Validity Stability Algebraic Petri nets are a formalism for modeling distributed systems and algorithms, describing control and data flow by combining Petri nets and algebraic specification. One way to specify correctness of an algebraic Petri net model "N" is to specify a linear equation "E" over the places of "N" based on term substitution, and coefficients from an abelian group "G". Then, "E" is valid in "N" iff "E" is valid in each reachable marking of "N". Due to the expressive power of Algebraic Petri nets, validity is generally undecidable. Stable linear equations form a class of linear equations for which validity is decidable. Place invariants yield a well-understood but incomplete characterization of all stable linear equations. In this paper, we provide a complete characterization of stability for the subclass of homogeneous linear equations, by restricting ourselves to the interpretation of terms over the Herbrand structure without considering further equality axioms. Based thereon, we show that stability is decidable for homogeneous linear equations if "G" is a cyclic group. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marvin Triebel and Jan Sürmeli 2016 Is Part Of LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2016.14 urn:nbn:de:0030-drops-61574 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.14 eng https://creativecommons.org/licenses/by/3.0/legalcode