Document Open Access Logo

Linear Equations with Ordered Data

Authors Piotr Hofman , Slawomir Lasota

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2018.24.pdf
  • Filesize: 0.54 MB
  • 17 pages

Document Identifiers

Author Details

Piotr Hofman
  • University of Warsaw, ul. Banacha 2, 02-097 Warsaw, Poland
Slawomir Lasota
  • University of Warsaw, ul. Banacha 2, 02-097 Warsaw, Poland

Funding

  • Hofman, Piotr: Partially supported by Polish NCN grant 2016/21/D/ST6/01368.
  • Lasota, Slawomir: Partially supported by Polish NCN grant 2016/21/B/ST6/01505.

Cite AsGet BibTex

Piotr Hofman and Slawomir Lasota. Linear Equations with Ordered Data. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CONCUR.2018.24

Abstract

Following a recently considered generalization of linear equations to unordered data vectors, we perform a further generalization to ordered data vectors. These generalized equations naturally appear in the analysis of vector addition systems (or Petri nets) extended with ordered data. We show that nonnegative-integer solvability of linear equations is computationally equivalent (up to an exponential blowup) to the reachability problem for (plain) vector addition systems. This high complexity is surprising, and contrasts with NP-completeness for unordered data vectors. This also contrasts with our second result, namely polynomial time complexity of the solvability problem when the nonnegative-integer restriction on solutions is relaxed.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parallel computing models
  • Theory of computation → Timed and hybrid models
  • Theory of computation → Automata over infinite objects
Keywords
  • Linear equations
  • Petri nets
  • Petri nets with data
  • vector addition systems
  • sets with atoms
  • orbit-finite sets

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Michael Blondin, Alain Finkel, Christoph Haase, and Serge Haddad. Approaching the coverability problem continuously. In Proc. TACAS 2016, pages 480-496, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49674-9_28.
  2. Michael Blondin and Christoph Haase. Logics for continuous reachability in Petri nets and vector addition systems with states. In Proc. LICS 2017, pages 1-12, 2017. URL: http://dx.doi.org/10.1109/LICS.2017.8005068.
  3. Mikołaj Bojańczyk. Slightly infinite sets. A draft of a book available at URL: https://www.mimuw.edu.pl/~bojan/paper/atom-book.
  4. Mikołaj Bojańczyk, Bartek Klin, Slawomir Lasota, and Szymon Toruńczyk. Turing machines with atoms. In Proc. LICS 2013, pages 183-192, 2013. URL: http://dx.doi.org/10.1109/LICS.2013.24.
  5. Rémi Bonnet, Alain Finkel, Serge Haddad, and Fernando Rosa-Velardo. Comparing Petri data nets and timed Petri nets. Technical Report LSV-10-23, Laboratoire Spécification et Vérification, ENS Cachan, France, 2010. Google Scholar
  6. Dmitry Chistikov and Christoph Haase. The taming of the semi-linear set. In Proc. ICALP'16, pages 128:1-128:13, 2016. Google Scholar
  7. Eric Domenjoud. Solving systems of linear Diophantine equations: An algebraic approach. In Proc. MFCS 1991, pages 141-150, 1991. Google Scholar
  8. Estíbaliz Fraca and Serge Haddad. Complexity analysis of continuous Petri nets. Fundam. Inform., 137(1):1-28, 2015. URL: http://dx.doi.org/10.3233/FI-2015-1168.
  9. Thomas Geffroy, Jérôme Leroux, and Grégoire Sutre. Occam’s razor applied to the Petri net coverability problem. In Proc. Reachability Problems 2016, pages 77-89, 2016. URL: http://dx.doi.org/10.1007/978-3-319-45994-3_6.
  10. Piotr Hofman and Sławomir Lasota. Linear equations with ordered data. CoRR, arXiv:1802.06660, 2018. URL: http://arxiv.org/abs/1802.06660.
  11. Piotr Hofman, Slawomir Lasota, Ranko Lazić, Jérôme Leroux, Sylvain Schmitz, and Patrick Totzke. Coverability Trees for Petri Nets with Unordered Data. In Proc. FoSSaCS, Eindhoven, Netherlands, 2016. URL: https://hal.inria.fr/hal-01252674.
  12. Piotr Hofman, Jérôme Leroux, and Patrick Totzke. Linear combinations of unordered data vectors. In Proc. LICS 2017, pages 1-11, 2017. Google Scholar
  13. Richard M. Karp. Reducibility among combinatorial problems. In Proc. Complexity of Computer Computations, pages 85-103, 1972. URL: http://www.cs.berkeley.edu/~luca/cs172/karp.pdf.
  14. Bartek Klin, Eryk Kopczyński, Joanna Ochremiak, and Szymon Toruńczyk. Locally finite constraint satisfaction problems. In Proc. LICS 2015, pages 475-486, 2015. URL: http://dx.doi.org/10.1109/LICS.2015.51.
  15. S. Rao Kosaraju. Decidability of reachability in vector addition systems. In STOC'82, pages 267-281. ACM, 1982. URL: http://dx.doi.org/10.1145/800070.802201.
  16. Slawomir Lasota. Decidability border for Petri nets with data: WQO dichotomy conjecture. In Proc. PETRI NETS 2016, pages 20-36, 2016. URL: http://dx.doi.org/10.1007/978-3-319-39086-4_3.
  17. Ranko Lazic, Thomas Christopher Newcomb, Joël Ouaknine, A. W. Roscoe, and James Worrell. Nets with tokens which carry data. Fundam. Inform., 88(3):251-274, 2008. Google Scholar
  18. Jérôme Leroux and Sylvain Schmitz. Demystifying reachability in vector addition systems. In Proc. LICS 2015, pages 56-67, 2015. URL: http://dx.doi.org/10.1109/LICS.2015.16.
  19. Richard Lipton. The reachability problem requires exponential space. Technical Report 62, Yale University, 1976. Google Scholar
  20. Ernst W. Mayr. An algorithm for the general Petri net reachability problem. In Proc. STOC 1981, pages 238-246. ACM, 1981. URL: http://dx.doi.org/10.1145/800076.802477.
  21. Loic Pottier. Minimal solutions of linear Diophantine systems: Bounds and algorithms. In Proc. RTA 1991, pages 162-173, 1991. URL: http://dl.acm.org/citation.cfm?id=647192.720494.
  22. Laura Recalde, Serge Haddad, and Manuel Silva Suárez. Continuous Petri nets: Expressive power and decidability issues. Int. J. Found. Comput. Sci., 21(2):235-256, 2010. URL: http://dx.doi.org/10.1142/S0129054110007222.
  23. Fernando Rosa-Velardo and David de Frutos-Escrig. Decidability and complexity of Petri nets with unordered data. Theor. Comput. Sci., 412(34):4439-4451, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.05.007.
  24. Manuel Silva Suárez, Enrique Teruel, and José Manuel Colom. Linear algebraic and linear programming techniques for the analysis of place or transition net systems. In Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, pages 309-373, 1996. URL: http://dx.doi.org/10.1007/3-540-65306-6_19.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact