The Library
O-minimal invariants for discrete-time dynamical systems
Tools
Almagor, Shaull, Chistikov, Dmitry, Ouaknine, Joël and Worrell, James (2022) O-minimal invariants for discrete-time dynamical systems. ACM Transactions on Computational Logic (TOCL), 23 (2). pp. 1-20. 9. doi:10.1145/3501299 ISSN 1529-3785.
|
PDF
WRAP-O-minimal-invariants-discrete-time-dynamical-systems-Dmitry-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (702Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/3501299
Abstract
Termination analysis of linear loops plays a key rôle in several areas of computer science, including program verification and abstract interpretation. Already for the simplest variants of linear loops the question of termination relates to deep open problems in number theory, such as the decidability of the Skolem and Positivity Problems for linear recurrence sequences, or equivalently reachability questions for discrete-time linear dynamical systems. In this article, we introduce the class of o-minimal invariants, which is broader than any previously considered, and study the decidability of the existence and algorithmic synthesis of such invariants as certificates of non-termination for linear loops equipped with a large class of halting conditions. We establish two main decidability results, one of them conditional on Schanuel’s conjecture is transcendental number theory.
Item Type: | Journal Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Invariants, Computational complexity, Logic, Symbolic and mathematical, Linear systems, Loops (Group theory) | |||||||||||||||
Journal or Publication Title: | ACM Transactions on Computational Logic (TOCL) | |||||||||||||||
Publisher: | Association for Computing Machinery, Inc. | |||||||||||||||
ISSN: | 1529-3785 | |||||||||||||||
Official Date: | April 2022 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 23 | |||||||||||||||
Number: | 2 | |||||||||||||||
Page Range: | pp. 1-20 | |||||||||||||||
Article Number: | 9 | |||||||||||||||
DOI: | 10.1145/3501299 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
Date of first compliant deposit: | 31 January 2022 | |||||||||||||||
Date of first compliant Open Access: | 1 February 2022 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year