Document Open Access Logo

Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set

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

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.39.pdf
  • Filesize: 0.68 MB
  • 14 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, Germany
  • Université de Lorraine, Inria, LORIA, Nancy, France
Eike Neumann
  • Swansea University, Swansea, UK
Joël Ouaknine
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, 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: Also affiliated with Keble College, Oxford as http://emmy.network/ Fellow, and supported by DFG grant 389792660 as part of TRR 248 (see https://perspicuous-computing.science).

Cite AsGet BibTex

Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell. Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.39

Abstract

We study the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets. We establish a uniform upper bound on the number of iterations it takes for every orbit of a rational matrix to escape a compact semialgebraic set defined over rational data. Our bound is doubly exponential in the ambient dimension, singly exponential in the degrees of the polynomials used to define the semialgebraic set, and singly exponential in the bitsize of the coefficients of these polynomials and the bitsize of the matrix entries. We show that our bound is tight by providing a matching lower bound.

Subject Classification

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

Metrics

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

Related Versions

References

  1. Alan Baker and Gisbert Wüstholz. Logarithmic forms and group varieties. Journal für die reine und angewandte Mathematik, 442:19-62, 1993. Google Scholar
  2. Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry. Springer, 2006. Google Scholar
  3. 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
  4. Yuval Bistritz and Alexander Lifshitz. Bounds for resultants of univariate and bivariate polynomials. Linear Algebra and its Applications, 432(8):1995-2005, 2010. Google Scholar
  5. Mark Braverman. Termination of integer linear programs. In CAV'06, volume 4144 of LNCS. Springer, 2006. Google Scholar
  6. 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: http://dx.doi.org/10.1142/S0129054194000165.
  7. Jin-Yi Cai, Richard J. Lipton, and Yechezkel Zalcstein. The complexity of the A B C problem. J. Computing, 29(6), 2000. Google Scholar
  8. Henri Cohen. A Course in Computational Algebraic Number Theory. Springer-Verlag, 1993. Google Scholar
  9. 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 Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1-33:21, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2021.33.
  10. Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell. Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set, 2022. URL: http://arxiv.org/abs/2207.01550.
  11. Julian D'Costa, Engel Lefaucheux, Joël Ouaknine, and James Worrell. How fast can you escape a compact polytope? In STACS'20, volume 154 of LIPIcs, pages 49:1-49:11, 2020. Google Scholar
  12. Steven M. Gonek and Hugh L. Montgomery. Kronecker’s approximation theorem. Indagationes Mathematicae, 27(2):506-523, 2016. Google Scholar
  13. Dima Grigoriev and Nicolai Vorobjov. Solving systems of polynomial inequalities in subexponential time. J. Symbolic Computation, 5:37-64, 1988. Google Scholar
  14. 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
  15. Gabriella Jeronimo, Daniel Perrucci, and Elias Tsigaridas. On the minimum of a polynomial function on a basic closed semialgebraic set and applications. SIAM Journal on Optimization, 23(1):241-255, 2013. Google Scholar
  16. David W. Masser. Linear relations on algebraic groups, pages 248-262. Cambridge University Press, 1988. Google Scholar
  17. M. Mignotte. Some useful bounds. In Computer Algebra, 1982. 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, pages 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. 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
  22. Ashish Tiwari. Termination of linear programs. In CAV'04, volume 3114 of LNCS. Springer, 2004. Google Scholar
  23. 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 Imprint Privacy Contact