Polynomial-time algorithm for the orbit problem

DOI10.1145/6490.6496MaRDI QIDQ3462041zbMATH OpenOpenAlexFDO

Authors Richard J. Lipton, R. 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

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

Recommendations

• On the complexity of the orbit problem
• The orbit problem in higher dimensions
• The orbit problem is in the GapL hierarchy
• The Orbit-Stabilizer Problem for Linear Groups
• scientific article; zbMATH DE number 7204476

Cited in

(51)

• Algorithms for matrix groups and the Tits alternative
• On solutions of linear ordinary difference equations in their coefficient field
• Weighted automata on infinite words in the context of attacker-defender games
• Unbounded-time safety verification of guarded LTI models with inputs by abstract acceleration
• First-order orbit queries
• Algebraic model checking for discrete linear dynamical systems
• Polynomially ambiguous probabilistic automata on restricted languages
• Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem
• The invariance problem for matrix semigroups
• On the decidability of semigroup freeness.
• Orbits of linear maps and regular languages
• A linear-time algorithm for the orbit problem over cyclic groups
• Orbits of linear maps and properties of regular languages
• On the complexity of the orbit problem
• A linear-time algorithm for the orbit problem over cyclic groups
• The Orbit-Stabilizer Problem for Linear Groups
• Reachability in Linear Dynamical Systems
• The Orbit Problem Is in the GapL Hierarchy
• Equivalence of set- and bag-valued orbits
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• scientific article; zbMATH DE number 4034996 (Why is no real title available?)
• Continuous-time orbit problems are decidable in polynomial-time
• Products of matrices and recursively enumerable sets
• scientific article; zbMATH DE number 7559115 (Why is no real title available?)
• On Reachability Problems for Low-Dimensional Matrix Semigroups
• Polynomially Ambiguous Probabilistic Automata on Restricted Languages
• Semicomputable points in Euclidean spaces
• scientific article; zbMATH DE number 7204378 (Why is no real title available?)
• REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS
• The orbit problem in higher dimensions
• On generalized conjugacy and some related problems
• What's decidable about discrete linear dynamical systems?
• The orbit problem is in the GapL hierarchy
• Model checking linear dynamical systems under floating-point rounding
• On the Monniaux problem in abstract interpretation
• Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem
• Porous invariants for linear systems
• Quantifying orbit detection: \(\varphi\)-order and \(\varphi\)-spectrum
• Reachability in dynamical systems with rounding
• On the size of finite rational matrix semigroups
• Orbit problems for free-abelian times free groups and related families
• On the Monniaux problem in abstract interpretation
• Subsets of groups in public-key cryptography
• The continuous Skolem-Pisot problem
• On the dynamics of endomorphisms of the direct product of two free groups
• Monoids of upper triangular matrices over the Boolean semiring
• On large zeros of linear recurrence sequences
• On piecewise affine reachability with Bellman operators
• Porous invariants
• On the membership of invertible diagonal and scalar matrices
• Polynomial ring automorphisms, rational \((w,\sigma )\)-canonical forms, and the assignment problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3462041)