DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2016.14

Homogeneous Equations of Algebraic Petri Nets

Authors: Marvin Triebel and Jan Sürmeli

Published in: LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016)

Abstract

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.

Cite as

Marvin Triebel and Jan Sürmeli. Homogeneous Equations of Algebraic Petri Nets. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{triebel_et_al:LIPIcs.CONCUR.2016.14,
  author =	{Triebel, Marvin and S\"{u}rmeli, Jan},
  title =	{{Homogeneous Equations of Algebraic Petri Nets}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Desharnais, Jos\'{e}e and Jagadeesan, Radha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.14},
  URN =		{urn:nbn:de:0030-drops-61574},
  doi =		{10.4230/LIPIcs.CONCUR.2016.14},
  annote =	{Keywords: Algebraic Petri Nets, Invariants, Linear Equations, Validity, Stability}
}

Search Results

Documents authored by Sürmeli, Jan

Homogeneous Equations of Algebraic Petri Nets

Abstract

Cite as

Thanks for your feedback!

Could not send message