Document Open Access Logo

On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets

Authors Julian D'Costa, Engel Lefaucheux , Eike Neumann, Joël Ouaknine , James Worrell

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.33.pdf
  • Filesize: 0.77 MB
  • 21 pages

Document Identifiers

Author Details

Julian D'Costa
  • Department of Computer Science, University of Oxford, UK
Engel Lefaucheux
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
Eike Neumann
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
Joël Ouaknine
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
James Worrell
  • Department of Computer Science, University of Oxford, UK

Funding

  • D'Costa, Julian: emmy.network foundation under the aegis of the Fondation de Luxembourg.
  • Ouaknine, Joël: ERC grant AVS-ISS (648701), and DFG grant 389792660 as part of TRR 248 (see https://perspicuous-computing.science). Joël Ouaknine is also affiliated with Keble College, Oxford as http://emmy.network/ Fellow.
  • Worrell, James: EPSRC Fellowship EP/N008197/1.

Cite As Get BibTex

Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell. On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.33

Abstract

We study the computational complexity of the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets, or equivalently the Termination Problem for affine loops with compact semialgebraic guard sets. Consider the fragment of the theory of the reals consisting of negation-free ∃ ∀-sentences without strict inequalities. We derive several equivalent characterisations of the associated complexity class which demonstrate its robustness and illustrate its expressive power. We show that the Compact Escape Problem is complete for this class.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic and verification
Keywords
  • Discrete linear dynamical systems
  • Program termination
  • Compact semialgebraic sets
  • Theory of the reals

Metrics

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

Related Versions

References

  1. Rajeev Alur. Principles of Cyber-Physical Systems. MIT Press, 2015. Google Scholar
  2. Andrea Bacciotti and Luisa Mazzi. Stability of dynamical polysystems via families of Lyapunov functions. J. Nonlinear Analysis, 67:2167-2179, 2007. Google Scholar
  3. Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry. Springer, 2006. Google Scholar
  4. Saugata Basu and Marie-Françoise Roy. Bounding the radii of balls meeting every connected component of semi-algebraic sets. Journal of Symbolic Computation, 45(12):1270-1279, 2010. Google Scholar
  5. Vincent D. Blondel and John N. Tsitsiklis. A survey of computational complexity results in systems and control. Automatica, 36(9):1249-1274, 2000. URL: https://doi.org/10.1016/S0005-1098(00)00050-9.
  6. Mark Braverman. Termination of integer linear programs. In CAV'06, volume 4144 of LNCS. Springer, 2006. Google Scholar
  7. Jin-Yi Cai. Computing Jordan normal forms exactly for commuting matrices in polynomial time. International Journal of Foundations of Computer Science, 5(3/4):293-302, 1994. URL: https://doi.org/10.1142/S0129054194000165.
  8. Jin-Yi Cai, Richard J. Lipton, and Yechezkel Zalcstein. The complexity of the A B C problem. J. Computing, 29(6), 2000. Google Scholar
  9. John Canny. Some algebraic and geometric computations in PSPACE. In STOC'88, pages 460-467. ACM, 1988. Google Scholar
  10. Eugênio B. Castelan and Jean-Claude Hennet. On invariant polyhedra of continuous-time linear systems. IEEE Transactions on Automatic Control, 38(11):1680-85, 1993. Google Scholar
  11. Henri Cohen. A Course in Computational Algebraic Number Theory. Springer-Verlag, 1993. Google Scholar
  12. George E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decompostion. In Automata Theory and Formal Languages, pages 134-183. Springer Berlin Heidelberg, 1975. Google Scholar
  13. Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell. On the complexity of the escape problem for linear dynamical systems over compact semialgebraic sets, 2021. URL: http://arxiv.org/abs/2107.02060.
  14. Dima Grigoriev. Complexity of deciding Tarski algebra. J. Symbolic Computation, 5(1-2):65-108, 1988. Google Scholar
  15. Dima Grigoriev and Nicolai Vorobjov. Solving systems of polynomial inequalities in subexponential time. J. Symbolic Computation, 5:37-64, 1988. Google Scholar
  16. Joos Heintz, Marie-Françoise Roy, and Pablo Solernó. Sur la complexité du princie de Tarski-Seidenberg. Bull. Soc. Math. France, 118(1):101-126, 1990. Google Scholar
  17. David W. Masser. Linear relations on algebraic groups, page 248–262. Cambridge University Press, 1988. Google Scholar
  18. Eike Neumann, Joël Ouaknine, and James Worrell. On ranking function synthesis and termination for polynomial programs. In CONCUR'20, volume 171, pages 15:1-15:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  19. Joël Ouaknine and James Worrell. Positivity Problems for Low-Order Linear Recurrence Sequences, page 366–379. Society for Industrial and Applied Mathematics, USA, 2014. Google Scholar
  20. James Renegar. On the computational complexity and geometry of the first-order theory of the reals. i-iii. J. Symbolic Computation, 13(3):255-352, 1992. Google Scholar
  21. Sriram Sankaranarayanan, Thao Dang, and Franjo Ivancic. A policy iteration technique for time elapse over template polyhedra. In HSCC'08, volume 4981 of LNCS. Springer, 2008. Google Scholar
  22. Marcus Schaefer and Daniel Štefankovič. Fixed Points, Nash Equilibria, and the Existential Theory of the Reals. Theory Computing Systems, 60(2):172-193, 2017. Google Scholar
  23. Shashi M. Srivastava. A course on Mathematical Logic. Springer, 2008. Google Scholar
  24. Ashish Tiwari. Termination of linear programs. In CAV'04, volume 3114 of LNCS. Springer, 2004. Google Scholar
  25. Dirk van Dalen. Logic and Structure. Springer Berlin Heidelberg, fourth edition, 2004. Google Scholar
  26. Nicolai Vorobjov. Bounds of real roots of a system of algebraic equations. Zap. Nauchn. Sem. LOMI, 137:7-19, 1984. (in Russian). Google Scholar
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 About DROPS Imprint Privacy Contact