2026-07-23T01:18:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10245 2024-03-06T10:45:37Z ddc:004 open_access

The Semialgebraic Orbit Problem Almagor, Shaull Ouaknine, Joël Worrell, James linear dynamical systems Orbit Problem first order theory of the reals The Semialgebraic Orbit Problem is a fundamental reachability question that arises in the analysis of discrete-time linear dynamical systems such as automata, Markov chains, recurrence sequences, and linear while loops. An instance of the problem comprises a dimension d in N, a square matrix A in Q^{d x d}, and semialgebraic source and target sets S,T subseteq R^d. The question is whether there exists x in S and n in N such that A^nx in T. The main result of this paper is that the Semialgebraic Orbit Problem is decidable for dimension d <= 3. Our decision procedure relies on separation bounds for algebraic numbers as well as a classical result of transcendental number theory - Baker’s theorem on linear forms in logarithms of algebraic numbers. We moreover argue that our main result represents a natural limit to what can be decided (with respect to reachability) about the orbit of a single matrix. On the one hand, semialgebraic sets are arguably the largest general class of subsets of R^d for which membership is decidable. On the other hand, previous work has shown that in dimension d=4, giving a decision procedure for the special case of the Orbit Problem with singleton source set S and polytope target set T would entail major breakthroughs in Diophantine approximation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shaull Almagor and Joël Ouaknine and James Worrell 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.6 urn:nbn:de:0030-drops-102450 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.6 eng https://creativecommons.org/licenses/by/3.0/legalcode