The continuous Skolem-Pisot problem
The authors consider a dynamical system with the updating trajectory \(\frac{dx(t)}{dt}=Ax(t)\), where \(A\in {\mathbb R}^{n\times n}\) and the initial point \(x(0)\in {\mathbb R}^n\) are given with entries being algebraic numbers. They are interested in determining whether this trajectory ever reaches a given hyperplane, thus the problem is equivalent to determining whether there exists \(t\in {\mathbb R}_{\geq 0}\) such that \(c^T\exp(At)x(0)=0\), where \(c\in {\mathbb R}^n\) defines the hyperplane (the entries of \(c\) are algebraic numbers, too.) This is the continuous Skolem-Pisot problem. The authors show that for instances of size two or less this problem is decidable. The decidability in general is left open. Determining if \(c^T\exp(At)x(0)=0\) reaches zero is computationally equivalent to determining whether a given real-valued exponential polynomial \(f(z)=\sum_{j=1}^m P_j(z)\exp(\theta_j z)\), where each \(P_j\) is a polynomial, ever reaches zero for a positive real value. This is also equivalent to determining whether the solution \(y(t)\) of an ordinary differential equation \(y^{(k)}+a_{k-1}y^{(k-1)}+\dots+a_0y=0\) with given initial conditions \(y^{(k-1)}(0),y^{(k-2)}(0),\dots,y(0)\) ever reaches zero. The authors also show that it is NP-hard to decide if a given linear recurrent sequence is nonnegative.
- On the Skolem problem for continuous linear dynamical systems
- Complexity of Restricted Variants of Skolem and Related Problems
- Decision problems for linear recurrence sequences
- The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
- On recurrent reachability for continuous linear dynamical systems
- A note on recurring series
- A survey of computational complexity results in systems and control
- Deux propriétés décidables des suites récurrentes linéaires
- Dissipative dynamical systems. II: Linear systems with quadratic supply rates
- scientific article; zbMATH DE number 3125787 (Why is no real title available?)
- scientific article; zbMATH DE number 3498237 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1973372 (Why is no real title available?)
- scientific article; zbMATH DE number 3421166 (Why is no real title available?)
- Improved matrix pair undecidability results
- Linear forms in the logarithms of algebraic numbers
- Occurrence of zero in a linear recursive sequence
- On the combinatorial and algebraic complexity of quantifier elimination
- On the Distribution of Values of Trigonometric Sums with Linearly Independent Frequencies
- Polynomial-time algorithm for the orbit problem
- Positivity of second order linear recurrent sequences
- Reachability in Linear Dynamical Systems
- The First Sign Change of a Cosine Polynomial
- The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
- Ghizzetti's theorem for piecewise continuous solutions
- The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
- Characterizing regions of attraction for piecewise affine systems by continuity of discrete transition functions
- Reset control for synchronization of multi-agent systems
- Reset control for consensus of double-integrator multi-agent systems
- Continuous-time orbit problems are decidable in polynomial-time
- On the Skolem problem for continuous linear dynamical systems
- On recurrent reachability for continuous linear dynamical systems
- A biology-inspired approach to the positive integral control of positive systems: the antithetic, exponential, and logistic integral controllers
- Complexity of Restricted Variants of Skolem and Related Problems
- Scalable control of positive systems
- On the polytope escape problem for continuous linear dynamical systems
- The Continuumproblem
- On a Continuous Sárközy-Type Problem
- The computability of LQR and LQG control
- On the decidability of reachability in continuous time linear time-invariant systems
- On the complexity of robust eventual inequality testing for C-finite functions
- On decidability of time-bounded reachability in CTMDPs
- Invariants for continuous linear dynamical systems
- Axiomatization of compact initial value problems: open properties
- On the zeros of exponential polynomials
- Reduction of transcendental decision problems over the reals
- Safely learning dynamical systems
- Analyzing ultimate positivity for solvable systems
This page was built for publication: The continuous Skolem-Pisot problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q708215)
