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

DOI10.1016/S0304-3975(00)00188-2zbMath0983.68078OpenAlexW2144383687MaRDI QIDQ5958118

Bhaskar Das Gupta

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00188-2

zbMATH Keywords

hybrid systemspolynomial-time algorithmspiecewise-linear systemssemiring congruencesstate-space equivalence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Reduction relations for monoid semirings ⋮ Algebraic switching time identification for a class of linear hybrid systems

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The algorithmic analysis of hybrid systems
• Hybrid systems
• Real addition and the polynomial hierarchy
• Remarks on piecewise-linear algebra
• A theory of timed automata
• Decidable hybrid systems
• O-minimal hybrid systems.
• Rational sets in commutative monoids
• Nonlinear regulation: The piecewise linear approach
• Hybrid automata with finite bisimulations
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Bounded Algol-Like Languages

This page was built for publication: A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems