What's decidable about linear loops?
Toghrul Karimov, Engel Lefaucheux, Joël Ouaknine, David Purser, Anton Varonka, Markus A. Whiteland, James Worrell
摘要
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.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
引用它的顶会 Paper5
- Affine Loop Invariant Generation via Matrix AlgebraYucheng Ji, Hongfei Fu, Bin Fang, Haibo ChenCAV 2022 · 被引用 10 次
- Strong Invariants Are Hard: On the Hardness of Strongest Polynomial Invariants for (Probabilistic) ProgramsJulian Müllner, Marcel Moosbrugger, Laura KovácsPOPL 2024 · 被引用 7 次
- On the Skolem Problem and the Skolem ConjectureRichard Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine 等LICS 2022 · 被引用 6 次
- On the Decidability of Monadic Second-Order Logic with Arithmetic PredicatesValérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine 等LICS 2024 · 被引用 3 次
- On the Subspace Orbit Problem and the Simultaneous Skolem ProblemPiotr Bacik, Anton VaronkaLICS 2026
它引用的顶会 Paper2
相关 Paper
- The Power of PositivityToghrul Karimov, Edon Kelmendi, Joris Nieuwveld, Joël Ouaknine 等LICS 2023 · 被引用 3 次
- Implicit Semi-Algebraic Abstraction for Polynomial Dynamical SystemsSergio Mover, Alessandro Cimatti, Alberto Griggio, Ahmed Irfan 等CAV 2021 · 被引用 4 次
- Multiple Reachability in Linear Dynamical SystemsToghrul Karimov, Edon Kelmendi, Joël Ouaknine, James WorrellLICS 2025 · 被引用 1 次
- Simple Linear Loops: Algebraic Invariants and ApplicationsRida Ait El Manssour, George Kenison, Mahsa Shirmohammadi, Anton VaronkaPOPL 2025 · 被引用 2 次
- Monitoring Arithmetic Temporal Properties on Finite TracesPaolo Felli, Marco Montali, Fabio Patrizi, Sarah WinklerAAAI 2023 · 被引用 14 次
