Polynomial-time algorithm for the orbit problem

DOI10.1145/6490.6496zbMath1326.68162OpenAlexW2034774429MaRDI QIDQ3462041

Richard J. Lipton, Ravindran Kannan

Publication date: 4 January 2016

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/6490.6496

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear transformations, semilinear transformations (15A04)

Related Items (30)

Polynomially ambiguous probabilistic automata on restricted languages ⋮ Porous invariants ⋮ A linear-time algorithm for the orbit problem over cyclic groups ⋮ On the decidability of semigroup freeness ⋮ On the membership of invertible diagonal and scalar matrices ⋮ On generalized conjugacy and some related problems ⋮ What's decidable about discrete linear dynamical systems? ⋮ Reachability in Linear Dynamical Systems ⋮ The orbit problem is in the GapL hierarchy ⋮ The Orbit Problem Is in the GapL Hierarchy ⋮ Continuous-time orbit problems are decidable in polynomial-time ⋮ Products of matrices and recursively enumerable sets ⋮ Polynomial ring automorphisms, rational \((w,\sigma )\)-canonical forms, and the assignment problem ⋮ Weighted automata on infinite words in the context of attacker-defender games ⋮ The continuous Skolem-Pisot problem ⋮ MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM ⋮ Unnamed Item ⋮ Unbounded-time safety verification of guarded LTI models with inputs by abstract acceleration ⋮ Unnamed Item ⋮ The Invariance Problem for Matrix Semigroups ⋮ First-order orbit queries ⋮ Semicomputable points in Euclidean spaces ⋮ Polynomially Ambiguous Probabilistic Automata on Restricted Languages ⋮ On Reachability Problems for Low-Dimensional Matrix Semigroups ⋮ REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS ⋮ Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem ⋮ Algorithms for matrix groups and the Tits alternative ⋮ On solutions of linear ordinary difference equations in their coefficient field ⋮ O-Minimal Invariants for Discrete-Time Dynamical Systems ⋮ Algebraic model checking for discrete linear dynamical systems

This page was built for publication: Polynomial-time algorithm for the orbit problem