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 条
  • [21] Reference governor for constrained piecewise affine systems
    Borrelli, Francesco
    Falcone, Paolo
    Pekar, Jaroslav
    Stewart, Greg
    JOURNAL OF PROCESS CONTROL, 2009, 19 (08) : 1229 - 1237
  • [22] Discontinuous piecewise quadratic Lyapunov functions for planar piecewise affine systems
    Eghbal, Najmeh
    Pariz, Naser
    Karimpour, Ali
    JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 2013, 399 (02) : 586 - 593
  • [23] Reachability of scope-bounded multistack pushdown systems
    La Torre, Salvatore
    Napoli, Margherita
    Parlato, Gennaro
    INFORMATION AND COMPUTATION, 2020, 275 (275)
  • [24] On the Decidability of Reachability in Continuous Time Linear Time-Invariant Systems
    Dantam, Mohan
    Pouly, Amaury
    HSCC2021: PROCEEDINGS OF THE 24TH INTERNATIONAL CONFERENCE ON HYBRID SYSTEMS: COMPUTATION AND CONTROL (PART OF CPS-IOT WEEK), 2021,
  • [25] Time-bounded reachability in tree-structured QBDs by abstraction
    Klink, Daniel
    Remke, Anne
    Haverkort, Boudewijn R.
    Katoen, Joost-Pieter
    PERFORMANCE EVALUATION, 2011, 68 (02) : 105 - 125
  • [26] Reachability of a set of facets for linear affine systems with n-1 inputs
    Roszak, Bartek
    Broucke, Mireille E.
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2007, 52 (02) : 359 - 364
  • [27] H∞ Control for Time-delay Piecewise Affine with Constrained Ellipsoid
    Liu, Zhilin
    Zhu, Qidan
    Wang, Lihui
    Cai, Chengtao
    CCDC 2009: 21ST CHINESE CONTROL AND DECISION CONFERENCE, VOLS 1-6, PROCEEDINGS, 2009, : 4236 - 4240
  • [28] Reachability of Hybrid Systems in Space-Time
    Frehse, Goran
    2015 PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON EMBEDDED SOFTWARE (EMSOFT), 2015, : 41 - 50
  • [29] Reachability and stabilizability for positive nonlinear systems on time scales
    Bartosiewicz, Z.
    OPTIMIZATION, 2022, 71 (11) : 3195 - 3210
  • [30] SAT-Reach: A Bounded Model Checker for Affine Hybrid Systems
    Kundu, Atanu
    Das, Sarthak
    Ray, Rajarshi
    ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS, 2023, 22 (02)
12345