TY - GEN
T1 - Computation of the Transient in Max-Plus Linear Systems via SMT-Solving
AU - Abate, Alessandro
AU - Cimatti, Alessandro
AU - Micheli, Andrea
AU - Mufid, Muhammad Syifa’ul
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - This paper proposes a new approach, grounded in Satisfiability Modulo Theories (SMT), to study the transient of a Max-Plus Linear (MPL) system, that is the number of steps leading to its periodic regime. Differently from state-of-the-art techniques, our approach allows the analysis of periodic behaviors for subsets of initial states, as well as the characterization of sets of initial states exhibiting the same specific periodic behavior and transient. Our experiments show that the proposed technique dramatically outperforms state-of-the-art methods based on max-plus algebra computations for systems of large dimensions.
AB - This paper proposes a new approach, grounded in Satisfiability Modulo Theories (SMT), to study the transient of a Max-Plus Linear (MPL) system, that is the number of steps leading to its periodic regime. Differently from state-of-the-art techniques, our approach allows the analysis of periodic behaviors for subsets of initial states, as well as the characterization of sets of initial states exhibiting the same specific periodic behavior and transient. Our experiments show that the proposed technique dramatically outperforms state-of-the-art methods based on max-plus algebra computations for systems of large dimensions.
UR - https://www.scopus.com/pages/publications/85090175215
U2 - 10.1007/978-3-030-57628-8_10
DO - 10.1007/978-3-030-57628-8_10
M3 - Conference contribution
AN - SCOPUS:85090175215
SN - 9783030576271
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 161
EP - 177
BT - Formal Modeling and Analysis of Timed Systems - 18th International Conference, FORMATS 2020, Proceedings
A2 - Bertrand, Nathalie
A2 - Jansen, Nils
PB - Springer
T2 - 18th International Conference on Formal Modeling and Analysis of Timed Systems, FORMATS 2020
Y2 - 1 September 2020 through 3 September 2020
ER -