On the Complexity of the Orbit Problem

DOI10.1145/2857050zbMath1426.68116arXiv1303.2981OpenAlexW2963416205MaRDI QIDQ3177796

Joël Ouaknine, Ventsislav Chonev, James Worrell

Publication date: 2 August 2018

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

Full work available at URL: https://arxiv.org/abs/1303.2981

zbMATH Keywords

linear transformationslinear recurrence sequencesSkolem's problemmatrix orbitstermination of linear programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability (number-theoretic aspects) (11U05) Recurrences (11B37) Linear transformations, semilinear transformations (15A04)

Related Items (15)

Polynomially ambiguous probabilistic automata on restricted languages ⋮ Effective results on the Skolem problem for linear recurrence sequences ⋮ What's decidable about discrete linear dynamical systems? ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Solving Skolem's problem for the \(k\)-generalized Fibonacci sequence with negative indices ⋮ On the Identity Problem for the Special Linear Group and the Heisenberg Group. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ First-order orbit queries ⋮ On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond ⋮ On Affine Reachability Problems ⋮ Polynomially Ambiguous Probabilistic Automata on Restricted Languages ⋮ On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond ⋮ O-Minimal Invariants for Discrete-Time Dynamical Systems ⋮ Algebraic model checking for discrete linear dynamical systems

This page was built for publication: On the Complexity of the Orbit Problem