On the complexity of bounded time and precision reachability for piecewise affine systems

被引：1
|
作者：
Bazille, Hugo [3 ,4 ]
Bournez, Olivier [1 ]
Gomaa, Walid [2 ,5 ]
Pouly, Amaury [1 ]
机构：
[1] Ecole Polytech, LIX, F-91128 Palaiseau, France
[2] Egypt Japan Univ Sci & Technol, CSE, Alexandria, Egypt
[3] ENS Cachan Bretagne, Rennes, France
[4] Univ Rennes 1, Rennes, France
[5] Alexandria Univ, Fac Engn, Alexandria, Egypt
来源：
THEORETICAL COMPUTER SCIENCE | 2018年 / 735卷
关键词：
Complexity; Reachability; Piecewise affine; DYNAMICAL-SYSTEMS;
D O I：
10.1016/j.tcs.2016.09.021
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Reachability for piecewise affine systems is known to be undecidable, starting from dimension 2. In this paper we investigate the exact complexity of several decidable variants of reachability and control questions for piecewise affine systems. We show in particular that the region-to-region bounded time versions leads to NP-complete or co-NP-complete problems, starting from dimension 2. We also prove that a bounded precision version leads to PSPACE-complete problems. (C) 2016 Elsevier B.V. All rights
引用
收藏
页码：132 / 146
页数：15
相关论文
共 50 条
  • [1] On the Complexity of Reachability and Mortality for Bounded Piecewise Affine Maps
    Tveretina, Olga
    REACHABILITY PROBLEMS, RP 2024, 2024, 15050 : 141 - 153
  • [2] Reachability analysis of continuous-time piecewise affine systems
    Hamadeh, Abdullah
    Goncalves, Jorge
    AUTOMATICA, 2008, 44 (12) : 3189 - 3194
  • [3] THE COMPLEXITY OF REACHABILITY IN AFFINE VECTOR ADDITION SYSTEMS WITH STATES
    Blondin, Michael
    Raskin, Mikhail
    LOGICAL METHODS IN COMPUTER SCIENCE, 2021, 17 (03) : 3:1 - 3:31
  • [4] The Complexity of Reachability in Affine Vector Addition Systems with States
    Blondin, Michael
    Raskin, Mikhail
    PROCEEDINGS OF THE 35TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2020), 2020, : 224 - 236
  • [5] Reachability and control synthesis for piecewise-affine hybrid systems on simplices
    Habets, L. C. G. J. M.
    Collins, P. J.
    van Schuppen, J. H.
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2006, 51 (06) : 938 - 948
  • [6] 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
  • [7] Necessary and Sufficient Conditions for Reachability of Discrete Time Affine Systems on Simplices
    Wu, Min
    Yan, Gangfeng
    Lin, Zhiyun
    PROCEEDINGS OF THE 48TH IEEE CONFERENCE ON DECISION AND CONTROL, 2009 HELD JOINTLY WITH THE 2009 28TH CHINESE CONTROL CONFERENCE (CDC/CCC 2009), 2009, : 63 - 68
  • [8] Reachability of affine systems on polytopes
    Wu, Min
    Yan, Gang-Feng
    Lin, Zhi-Yun
    Zidonghua Xuebao/ Acta Automatica Sinica, 2009, 35 (12): : 1528 - 1533
  • [9] Reachability and stabilization of discrete-time affine systems with disturbances
    Lin, Zhiyun
    Wu, Min
    Yan, Gangfeng
    AUTOMATICA, 2011, 47 (12) : 2720 - 2727
  • [10] Reachability of Standard and Fractional Continuous-Time Systems with Piecewise Constant Inputs
    Rogowski, Krzysztof
    CHALLENGES IN AUTOMATION, ROBOTICS AND MEASUREMENT TECHNIQUES, 2016, 440 : 341 - 349
12345