A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems

Bhaskar DasGupta, Eduardo D. Sontag

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)161-189
Number of pages29
JournalTheoretical Computer Science
Volume262
Issue number1-2
DOIs
StatePublished - 2001

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Hybrid systems
  • Piecewise-linear systems
  • Polynomial-time algorithms
  • Semiring congruences
  • State-space equivalence

Fingerprint Dive into the research topics of 'A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems'. Together they form a unique fingerprint.

Cite this