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

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	132-146
Nombre de pages	15
journal	Theoretical Computer Science
Volume	735
Les DOIs	https://doi.org/10.1016/j.tcs.2016.09.021
état	Publié - 29 juil. 2018

Accès au document

10.1016/j.tcs.2016.09.021

Contient cette citation

@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

Résumé

Accès au document

Empreinte digitale

Contient cette citation