Reachability problems in low-dimensional iterative maps

被引：9
|
作者：
Kurganskyy, Oleksiy [1 ]
Potapov, Igor [2 ]
Sancho-Caparrini, Fernando [3 ]
机构：
[1] Natl Acad Sci Ukraine, Inst Appl Math & Mech, Donetsk, Ukraine
[2] Univ Liverpool, Dept Comp Sci, Liverpool L69 3BX, Merseyside, England
[3] Univ Seville, Dept Comp Sci & Artificial Intelligence, E-41012 Seville, Spain
来源：
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2008年 / 19卷 / 04期
关键词：
theory of computing; reachability problems; iterative piecewise maps; pseudo-billiard systems; universality;
D O I：
10.1142/S0129054108006054
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper we analyze the dynamics of one-dimensional piecewise maps. We show that one-dimensional piecewise affine maps are equivalent to pseudo-billiard or so called "strange billiard" systems. We also show that use of more general classes of functions lead to undecidability of reachability problem for one-dimensional piecewise maps.
引用
收藏
页码：935 / 951
页数：17
相关论文
共 50 条
  • [1] Reachability problems in low-dimensional nondeterministic polynomial maps over integers
    Ko, S. K.
    Niskanen, R.
    Potapov, I
    INFORMATION AND COMPUTATION, 2021, 281
  • [2] CHAOS IN LOW-DIMENSIONAL HAMILTONIAN MAPS
    KANTZ, H
    GRASSBERGER, P
    PHYSICS LETTERS A, 1987, 123 (09) : 437 - 443
  • [3] On low-dimensional cancellation problems
    Belov, Alexei
    Yu, Jie-Tai
    JOURNAL OF ALGEBRA, 2008, 319 (06) : 2235 - 2242
  • [4] Reachability Problems for One-Dimensional Piecewise Affine Maps
    Bournez, Olivier
    Kurganskyy, Oleksiy
    Potapov, Igor
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2018, 29 (04) : 529 - 549
  • [5] Low-dimensional maps for piecewise smooth oscillators
    Pavlovskaia, Ekaterina
    Wiercigroch, Marian
    JOURNAL OF SOUND AND VIBRATION, 2007, 305 (4-5) : 750 - 771
  • [6] Inverse problems on low-dimensional manifolds
    Alberti, Giovanni S.
    Arroyo, Angel
    Santacesaria, Matteo
    NONLINEARITY, 2023, 36 (01) : 734 - 808
  • [7] Complicated dynamics for low-dimensional strongly monotone maps
    Smith, HL
    NONLINEAR ANALYSIS-THEORY METHODS & APPLICATIONS, 1997, 30 (03) : 1911 - 1914
  • [8] Nonextensivity: From low-dimensional maps to Hamiltonian systems
    Tsallis, C
    Rapisarda, AN
    Latora, V
    Baldovin, F
    DYNAMICS AND THERMODYNAMICS OF SYSTEMS WITH LONG-RANGE INTERACTIONS, 2002, 602 : 140 - 162
  • [9] Low-dimensional maps encoding dynamics in entorhinal cortex and hippocampus
    Pervouchine, Dmitri D.
    Netoff, Theoden I.
    Rotstein, Horacio G.
    White, John A.
    Cunningham, Mark O.
    Whittington, Miles A.
    Kopell, Nancy J.
    NEURAL COMPUTATION, 2006, 18 (11) : 2617 - 2650
  • [10] Reachability analysis of large-scale affine systems using low-dimensional polytopes
    Han, Zhi
    Krogh, Bruce H.
    HYBRID SYSTEMS: COMPUTATION AND CONTROL, PROCEEDINGS, 2006, 3927 : 287 - 301
12345