Document Open Access Logo

The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems

Authors Julian D'Costa , Toghrul Karimov , Rupak Majumdar , Joël Ouaknine , Mahmoud Salamati , James Worrell

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.40.pdf
  • Filesize: 0.71 MB
  • 13 pages

Document Identifiers

Author Details

Julian D'Costa
  • Department of Computer Science, University of Oxford, UK
Toghrul Karimov
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Germany
Rupak Majumdar
  • Max Planck Institute for Software Systems, Kaiserslautern, Germany
Joël Ouaknine
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Germany
Mahmoud Salamati
  • Max Planck Institute for Software Systems, Kaiserslautern, 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.
  • Majumdar, Rupak: DFG grant 389792660 as part of TRR 248 (see https://perspicuous-computing.science).
  • Ouaknine, Joël: 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.

Cite AsGet BibTex

Julian D'Costa, Toghrul Karimov, Rupak Majumdar, Joël Ouaknine, Mahmoud Salamati, and James Worrell. The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.40

Abstract

We study fundamental reachability problems on pseudo-orbits of linear dynamical systems. Pseudo-orbits can be viewed as a model of computation with limited precision and pseudo-reachability can be thought of as a robust version of classical reachability. Using an approach based on o-minimality of ℝ_exp we prove decidability of the discrete-time pseudo-reachability problem with arbitrary semialgebraic targets for diagonalisable linear dynamical systems. We also show that our method can be used to reduce the continuous-time pseudo-reachability problem to the (classical) time-bounded reachability problem, which is known to be conditionally decidable.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic and verification
Keywords
  • pseudo-orbits
  • Orbit problem
  • Skolem problem
  • linear dynamical systems
  • reachability

Metrics

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

Related Versions

References

  1. S. Akshay, Hugo Bazille, Blaise Genest, and Mihir Vahanwala. On Robustness for the Skolem and Positivity Problems. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), volume 219 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1-5:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2022.5.
  2. Dmitri V. Anosov. Geodesic flows on closed Riemannian manifolds of negative curvature. Proc. Steklov Inst. Math., 90, 1967. Google Scholar
  3. Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, and Filip Mazowiecki. A Robust Class of Linear Recurrence Sequences. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020), volume 152 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1-9:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CSL.2020.9.
  4. Rufus Bowen. Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms, volume 470 of Lecture Notes in Mathematics. Springer-Verlag, 1975. Google Scholar
  5. Ventsislav Chonev, Joël Ouaknine, and James Worrell. On the Skolem Problem for Continuous Linear Dynamical Systems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 100:1-100:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.100.
  6. Charles C. Conley. Isolated invariant sets and the Morse index, volume 25 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1978. Google Scholar
  7. Julian D'Costa, Toghrul Karimov, Rupak Majumdar, Joël Ouaknine, Mahmoud Salamati, Sadegh Soudjani, and James Worrell. The Pseudo-Skolem Problem is Decidable. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1-34:21, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.34.
  8. Nathanaël Fijalkow, Joël Ouaknine, Amaury Pouly, João Sousa-Pinto, and James Worrell. On the decidability of reachability in linear time-invariant systems. In Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control, HSCC '19, pages 77-86, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3302504.3311796.
  9. Godfrey H. Hardy and Edward M. Wright. An Introduction to the Theory of Numbers. Oxford University Press, 1999. Google Scholar
  10. Toghrul Karimov, Engel Lefaucheux, Joël Ouaknine, David Purser, Anton Varonka, Markus A. Whiteland, and James Worrell. What’s decidable about linear loops? Proc. ACM Program. Lang., 6(POPL), January 2022. URL: https://doi.org/10.1145/3498727.
  11. Serge Lang. Introduction to transcendental numbers. Addison-Wesley series in mathematics. Addison-Wesley Pub. Co., 1966. Google Scholar
  12. Richard Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser, and James Worrell. On the skolem problem and the skolem conjecture. To appear in LICS 2022, 2022. URL: https://people.mpi-sws.org/~joel/publications/skolem_five22.pdf.
  13. Angus Macintyre and Alex J. Wilkie. On the decidability of the real exponential field. In Kreiseliana. About and Around Georg Kreisel, pages 441-467. A K Peters, 1996. Google Scholar
  14. David W. Masser. Linear relations on algebraic groups. In New Advances in Transcendence Theory. Camb. Univ. Press, 1988. Google Scholar
  15. Kenji Nagasaka and Jau-Shyong Shiue. Asymptotic positiveness of linear recurrence sequences. Fibonacci Quart, 28(4):340-346, 1990. Google Scholar
  16. Joël Ouaknine and James Worrell. Positivity problems for low-order linear recurrence sequences. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 366-379, 2014. Google Scholar
  17. Joël Ouaknine and James Worrell. On linear recurrence sequences and loop termination. ACM SIGLOG News, 2(2):4-13, April 2015. URL: https://doi.org/10.1145/2766189.2766191.
  18. Laurentius Petrus Dignus "Lou" van den Dries. Tame Topology and O-minimal Structures. Cambridge University Press, 1998. Google Scholar
  19. Alex J. Wilkie. Schanuel’s conjecture and the decidability of the real exponential field. In Algebraic Model Theory, pages 223-230. Springer Netherlands, Dordrecht, 1997. 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