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

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

langue originale	Anglais
Pages (de - à)	20-31
Nombre de pages	12
journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8762
Les DOIs	https://doi.org/10.1007/978-3-319-11439-2_2
état	Publié - 1 janv. 2014

Accès au document

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

Contient cette citation

@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.
Dans: 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.

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

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

Résumé

Accès au document

Empreinte digitale

Contient cette citation