Reachability in Injective Piecewise Affine Maps

Ghahremani, Faraz; Kelmendi, Edon; Ouaknine, Joël

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Paper

Reachability in Injective Piecewise Affine Maps

MPS-Authors

/persons/resource/persons217847

Ouaknine, Joël
Group J. Ouaknine, Max Planck Institute for Software Systems, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

arXiv:2301.09752.pdf
(Preprint), 986KB

Supplementary Material (public)

There is no public supplementary material available

Citation

Ghahremani, F., Kelmendi, E., & Ouaknine, J. (2023). Reachability in Injective Piecewise Affine Maps. Retrieved from https://arxiv.org/abs/2301.09752.

Cite as: https://hdl.handle.net/21.11116/0000-000D-0DD0-A

Abstract

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.