On the complexity of bounded time reachability for piecewise affine systems

Hugo Bazille; Olivier Bournez; Walid Gomaa; Amaury Pouly

doi:10.1007/978-3-319-11439-2_2

On the complexity of bounded time reachability for piecewise affine systems

Hugo Bazille
, Olivier Bournez
, Walid Gomaa
, Amaury Pouly

University of Rennes
Egypt-Japan University of Science and Technology
Alexandria University

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 N P-complete or co-N P-complete problems, starting from dimension 2.

Original language	English
Pages (from-to)	20-31
Number of pages	12
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8762
DOIs	https://doi.org/10.1007/978-3-319-11439-2_2
Publication status	Published - 1 Jan 2014

Access to Document

10.1007/978-3-319-11439-2_2

Cite this

@article{8034496f9a4e4a628ac8e17a86123ebd,

title = "On the complexity of bounded time 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 N P-complete or co-N P-complete problems, starting from dimension 2.",

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

note = "Publisher Copyright: {\textcopyright} 2014 Springer International Publishing Switzerland.",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-319-11439-2\_2",

language = "English",

volume = "8762",

pages = "20--31",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

}

On the complexity of bounded time reachability for piecewise affine systems. / Bazille, Hugo; Bournez, Olivier; Gomaa, Walid et al.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 8762, 01.01.2014, p. 20-31.

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

TY - JOUR

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

AU - Bazille, Hugo

AU - Bournez, Olivier

AU - Gomaa, Walid

AU - Pouly, Amaury

PY - 2014/1/1

Y1 - 2014/1/1

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 N P-complete or co-N P-complete problems, starting from dimension 2.

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 N P-complete or co-N P-complete problems, starting from dimension 2.

U2 - 10.1007/978-3-319-11439-2_2

DO - 10.1007/978-3-319-11439-2_2

M3 - Article

AN - SCOPUS:84921744439

SN - 0302-9743

VL - 8762

SP - 20

EP - 31

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

On the complexity of bounded time reachability for piecewise affine systems

Abstract

Access to Document

Fingerprint

Cite this