3 papers
cs.DM2026
On the Subspace Orbit Problem and the Simultaneous Skolem Problem
Piotr Bacik, Anton Varonka
The Orbit Problem asks whether the orbit of a point under a matrix reaches a given target set. When the target is a single point, the problem was shown to be decidable in polynomia…
cs.CC2025
Determination Problems for Orbit Closures and Matrix Groups
Rida Ait El Manssour, George Kenison, Mahsa Shirmohammadi +2
Computational problems concerning the orbit of a point under the action of a matrix group occur throughout computer science, including in program analysis, complexity theory, quant…
cs.CC2024
Simple Linear Loops: Algebraic Invariants and Applications
Rida Ait El Manssour, George Kenison, Mahsa Shirmohammadi +1
The automatic generation of loop invariants is a fundamental challenge in software verification. While this task is undecidable in general, it is decidable for certain restricted c…