One of the most basic, longstanding open problems in the theory of
dynamical systems is whether reachability is decidable for
one-dimensional piecewise affine maps with two
intervals. In this paper we prove that for injective maps,
it is decidable.
We also study various related problems, in each case either
establishing decidability, or showing that they are closely connected
to Diophantine properties of certain transcendental numbers,
analogous to the positivity problem for linear recurrence
sequences. Lastly, we consider topological properties of orbits of
one-dimensional piecewise affine maps, not necessarily with two
intervals, and negatively answer a question of Bournez, Kurganskyy,
and Potapov, about the set of orbits in expanding maps.
Proceedings of LICS 23, 2023. 22 pages.
PDF
© 2023 IEEE.