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 -