The polyhedron-hitting problem

DOI10.1137/1.9781611973730.64MaRDI QIDQ5362998zbMATH OpenOpenAlexFDO

Authors Ventsislav Chonev, Joël Ouaknine, James Worrell

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) (n)-dimensional polytopes (52B11) Number-theoretic algorithms; complexity (11Y16) Decidability (number-theoretic aspects) (11U05)

Abstract: We consider polyhedral versions of Kannan and Lipton's Orbit Problem (STOC '80 and JACM '86)---determining whether a target polyhedron V may be reached from a starting point x under repeated applications of a linear transformation A in an ambient vector space Q^m. In the context of program verification, very similar reachability questions were also considered and left open by Lee and Yannakakis in (STOC '92). We present what amounts to a complete characterisation of the decidability landscape for the Polyhedron-Hitting Problem, expressed as a function of the dimension m of the ambient space, together with the dimension of the polyhedral target V: more precisely, for each pair of dimensions, we either establish decidability, or show hardness for longstanding number-theoretic open problems.

Recommendations

• scientific article; zbMATH DE number 7204476
• The orbit problem in higher dimensions
• On the complexity of the orbit problem
• scientific article; zbMATH DE number 7559115
• First-order orbit queries

Cited in

(16)

• Algebraic model checking for discrete linear dynamical systems
• The polyhedral Tammes problem
• scientific article; zbMATH DE number 7559115 (Why is no real title available?)
• scientific article; zbMATH DE number 7204476 (Why is no real title available?)
• Orbits of linear maps and regular languages
• Orbits of linear maps and properties of regular languages
• On the complexity of the orbit problem
• Reachability in dynamical systems with rounding
• The orbit problem in higher dimensions
• First-order orbit queries
• Porous invariants for linear systems
• Complexity of Restricted Variants of Skolem and Related Problems
• scientific article; zbMATH DE number 7559425 (Why is no real title available?)
• Affine Loop Invariant Generation via Matrix Algebra
• On the Skolem problem and the Skolem conjecture
• What's decidable about discrete linear dynamical systems?

This page was built for publication: The polyhedron-hitting problem

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