6 papers
Eventual Nonnegativity of a Matrix Is in P
Julian D'Costa
Given a rational matrix , is every sufficiently large power entrywise nonnegative? We prove that this problem is decidable in deterministic polynomial time. This is in con…
Nonnegativity Problems for Matrix Semigroups
Julian D'Costa, Joel Ouaknine, James Worrell
The matrix semigroup membership problem asks, given square matrices of the same dimension, whether lies in the semigroup generated by . It is…
Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
Julian D'Costa, Engel Lefaucheux, Eike Neumann +2
We study the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets. We establish a uniform upper bound on the number of iterations it takes for…
The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems
Julian D'Costa, Toghrul Karimov, Rupak Majumdar +3
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-rea…
On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
Julian D'Costa, Engel Lefaucheux, Eike Neumann +2
We study the computational complexity of the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets, or equivalently the Termination Problem for…
How Fast Can You Escape a Compact Polytope?
Julian D'Costa, Engel Lefaucheux, Joël Ouaknine +1
The Continuous Polytope Escape Problem (CPEP) asks whether every trajectory of a linear differential equation initialised within a convex polytope eventually escapes the polytope.…