TY - JOUR
T1 - A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems
AU - DasGupta, Bhaskar
AU - D. Sontag, Eduardo
N1 - Funding Information:
An Extended Abstract of these results without most proofs appeared under the title A Polynomial-Time Algorithm for an Equivalence Problem which Arises in Hybrid Systems Theory in proceedings of the 37th IEEE Conference on Decision and Control, December 1998, IEEE Publications, pp. 1629–1634 ∗Corresponding author. E-mail addresses: bhaskar@crab.rutgers.edu (B. DasGupta), sontag@control.rutgers.edu (E.D. Sontag). 1Supported in part by US Air Force Grant AFOSR-97-0159 and by NSF Grant CCR-9800086. 2Supported in part by US Air Force Grant AFOSR-97-0159.
PY - 2001
Y1 - 2001
N2 - This paper presents a polynomial-time algorithm for equivalence under certain semiring congruences. These congruences arise when studying the isomorphism of state spaces for a class of hybrid systems. The area of hybrid systems concerns issues of modeling, computation, and control for systems which combine discrete and continuous components. The subclass of piecewise linear (PL) systems provides one systematic approach to discrete-time hybrid systems, naturally blending switching mechanisms with classical linear components. PL systems model arbitrary interconnections of finite automata and linear systems. Tools from automata theory, logic, and related areas of computer science and finite mathematics are used in the study of PL systems, in conjunction with linear algebra techniques, all in the context of a "PL algebra" formalism. PL systems are of interest as controllers as well as identification models. Basic questions for any class of systems are those of equivalence, and, in particular, whether state spaces are equivalent under a change of variables. This paper studies this state-space equivalence problem for PL systems. The problem was known to be decidable, but its computational complexity was potentially exponential; here it is shown to be solvable in polynomial time.
AB - This paper presents a polynomial-time algorithm for equivalence under certain semiring congruences. These congruences arise when studying the isomorphism of state spaces for a class of hybrid systems. The area of hybrid systems concerns issues of modeling, computation, and control for systems which combine discrete and continuous components. The subclass of piecewise linear (PL) systems provides one systematic approach to discrete-time hybrid systems, naturally blending switching mechanisms with classical linear components. PL systems model arbitrary interconnections of finite automata and linear systems. Tools from automata theory, logic, and related areas of computer science and finite mathematics are used in the study of PL systems, in conjunction with linear algebra techniques, all in the context of a "PL algebra" formalism. PL systems are of interest as controllers as well as identification models. Basic questions for any class of systems are those of equivalence, and, in particular, whether state spaces are equivalent under a change of variables. This paper studies this state-space equivalence problem for PL systems. The problem was known to be decidable, but its computational complexity was potentially exponential; here it is shown to be solvable in polynomial time.
KW - Hybrid systems
KW - Piecewise-linear systems
KW - Polynomial-time algorithms
KW - Semiring congruences
KW - State-space equivalence
UR - http://www.scopus.com/inward/record.url?scp=0034916639&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0034916639&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(00)00188-2
DO - 10.1016/S0304-3975(00)00188-2
M3 - Article
AN - SCOPUS:0034916639
VL - 262
SP - 161
EP - 189
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
IS - 1-2
ER -