Reachability problems for one-dimensional piecewise affine maps

DOI10.1142/S0129054118410046MaRDI QIDQ3177337zbMATH OpenWikidataFDO

Authors O. Kurganskyy, Igor Potapov, Olivier Bournez

Publication date 24 July 2018

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054118410046

zbMATH Keywords

\(\beta\)-expansion\(p\)-adic analysispiecewise affine mapreachability problem

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Undecidability and degrees of sets of sentences (03D35) (p)-adic theory (11E95)

Recommendations

• Reachability problems for PAMs
• On reachability problem in 1-dimensional 2-interval piecewise-affine mappings
• REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
• Computation in One-Dimensional Piecewise Maps
• Reachability problems in low-dimensional nondeterministic polynomial maps over integers

Cites work

• A survey of computational complexity results in systems and control
• Almost Every Number Has a Continuum of b-Expansions
• Computability with low-dimensional dynamical systems
• Computer-Assisted Verification Method for Invariant Densities and Rates of Decay of Correlations
• Decidability of the membership problem for \(2\times 2\) integer matrices
• Deciding stability and mortality of piecewise affine dynamical systems
• scientific article; zbMATH DE number 1927563 (Why is no real title available?)
• scientific article; zbMATH DE number 7204378 (Why is no real title available?)
• Low dimensional hybrid systems -- decidable, undecidable, don't know
• Mortality of iterated piecewise affine functions over the integers: decidability and complexity
• On termination of integer linear loops
• On the complexity of bounded time reachability for piecewise affine systems
• On the Identity Problem for the Special Linear Group and the Heisenberg Group.
• On the isolated spectrum of the Perron-Frobenius operator
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• On undecidability bounds for matrix decision problems
• Percentile queries in multi-dimensional Markov decision processes
• Reachability analysis of dynamical systems having piecewise-constant derivatives
• Reachability and mortality problems for restricted hierarchical piecewise constant derivatives
• REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
• Representations for real numbers and their ergodic properties
• Switched flow systems: pseudo billiard dynamics
• The stability of saturated linear dynamical systems is undecidable
• The target discounted-sum problem
• The topological entropy of iterated piecewise affine maps is uncomputable
• Unconventional Computation
• Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\)

Cited in

(9)

• Reachability problems in low-dimensional nondeterministic polynomial maps over integers
• Reachability problems for PAMs
• REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
• Computation in One-Dimensional Piecewise Maps
• On Affine Reachability Problems
• On reachability problem in 1-dimensional 2-interval piecewise-affine mappings
• On the decidability of reachability in continuous time linear time-invariant systems
• Discounted-sum automata with real-valued discount factors
• On piecewise affine reachability with Bellman operators

This page was built for publication: Reachability problems for one-dimensional piecewise affine maps

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