What's decidable about linear loops?
Toghrul Karimov, Engel Lefaucheux, Joël Ouaknine, David Purser, Anton Varonka, Markus A. Whiteland, James Worrell
Abstract
We consider the MSO model-checking problem for simple linear loops, or equivalently discrete-time linear dynamical systems, with semialgebraic predicates (i.e., Boolean combinations of polynomial inequalities on the variables). We place no restrictions on the number of program variables, or equivalently the ambient dimension. We establish decidability of the model-checking problem provided that each semialgebraic predicate either has intrinsic dimension at most 1, or is contained within some three-dimensional subspace. We also note that lifting either of these restrictions and retaining decidability would necessarily require major breakthroughs in number theory.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext e386af59-2d8c-4a05-8673-87f7efc54719Cited by top-tier papers5
- Affine Loop Invariant Generation via Matrix AlgebraYucheng Ji, Hongfei Fu, Bin Fang, Haibo ChenCAV 2022 · 10 citations
- Strong Invariants Are Hard: On the Hardness of Strongest Polynomial Invariants for (Probabilistic) ProgramsJulian Müllner, Marcel Moosbrugger, Laura KovácsPOPL 2024 · 7 citations
- On the Skolem Problem and the Skolem ConjectureRichard Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine et al.LICS 2022 · 6 citations
- On the Decidability of Monadic Second-Order Logic with Arithmetic PredicatesValérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine et al.LICS 2024 · 3 citations
- On the Subspace Orbit Problem and the Simultaneous Skolem ProblemPiotr Bacik, Anton VaronkaLICS 2026
Builds on2
Related papers
- The Power of PositivityToghrul Karimov, Edon Kelmendi, Joris Nieuwveld, Joël Ouaknine et al.LICS 2023 · 3 citations
- Implicit Semi-Algebraic Abstraction for Polynomial Dynamical SystemsSergio Mover, Alessandro Cimatti, Alberto Griggio, Ahmed Irfan et al.CAV 2021 · 4 citations
- Multiple Reachability in Linear Dynamical SystemsToghrul Karimov, Edon Kelmendi, Joël Ouaknine, James WorrellLICS 2025 · 1 citation
- Simple Linear Loops: Algebraic Invariants and ApplicationsRida Ait El Manssour, George Kenison, Mahsa Shirmohammadi, Anton VaronkaPOPL 2025 · 2 citations
- Monitoring Arithmetic Temporal Properties on Finite TracesPaolo Felli, Marco Montali, Fabio Patrizi, Sarah WinklerAAAI 2023 · 14 citations
