ausblenden:
Schlagwörter:
Mathematics, Dynamical Systems, math.DS,Computer Science, Formal Languages and Automata Theory, cs.FL,Computer Science, Logic in Computer Science, cs.LO
Zusammenfassung:
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.