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

Hugo Bazille; Olivier Bournez; Walid Gomaa; Amaury Pouly

doi:10.1016/j.tcs.2016.09.021

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

Hugo Bazille
, Olivier Bournez
, Walid Gomaa
, Amaury Pouly

University of Rennes
Egypt-Japan University of Science and Technology
Faculty of Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	132-146
Number of pages	15
Journal	Theoretical Computer Science
Volume	735
DOIs	https://doi.org/10.1016/j.tcs.2016.09.021
Publication status	Published - 29 Jul 2018

Keywords

Complexity
Piecewise affine
Reachability

Access to Document

10.1016/j.tcs.2016.09.021

Cite this

@article{6745f18f5ff1462b9a069729ac528687,

title = "On the complexity of bounded time and precision reachability for piecewise affine systems",

abstract = "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.",

keywords = "Complexity, Piecewise affine, Reachability",

author = "Hugo Bazille and Olivier Bournez and Walid Gomaa and Amaury Pouly",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2018",

month = jul,

day = "29",

doi = "10.1016/j.tcs.2016.09.021",

language = "English",

volume = "735",

pages = "132--146",

journal = "Theoretical Computer Science",

issn = "0304-3975",

}

TY - JOUR

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

AU - Bazille, Hugo

AU - Bournez, Olivier

AU - Gomaa, Walid

AU - Pouly, Amaury

PY - 2018/7/29

Y1 - 2018/7/29

N2 - 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.

AB - 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.

KW - Complexity

KW - Piecewise affine

KW - Reachability

U2 - 10.1016/j.tcs.2016.09.021

DO - 10.1016/j.tcs.2016.09.021

M3 - Article

AN - SCOPUS:85008600001

SN - 0304-3975

VL - 735

SP - 132

EP - 146

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this