Efficient Local Computation of Differential Bisimulations via Coupling and Up-to Methods

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

1 Citation (Scopus)

Abstract

We introduce polynomial couplings, a generalization of probabilistic couplings, to develop an algorithm for the computation of equivalence relations which can be interpreted as a lifting of probabilistic bisimulation to polynomial differential equations, a ubiquitous model of dynamical systems across science and engineering. The algorithm enjoys polynomial time complexity and complements classical partition-refinement approaches because: (a) it implements a local exploration of the system, possibly yielding equivalences that do not necessarily involve the inspection of the whole system of differential equations; (b) it can be enhanced by up-to techniques; and (c) it allows the specification of pairs which ought not be included in the output. Using a prototype, these advantages are demonstrated on case studies from systems biology for applications to model reduction and comparison. Notably, we report four orders of magnitude smaller runtimes than partition-refinement approaches when disproving equivalences between Markov chains.
Original languageEnglish
Title of host publication36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Number of pages14
PublisherIEEE
Publication date2021
Pages1-14
ISBN (Print)978-1-6654-4896-3
ISBN (Electronic)978-1-6654-4895-6
DOIs
Publication statusPublished - 2021
Event36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) - Virtual, Rome, Italy
Duration: 29 Jun 20212 Jul 2021

Conference

Conference36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
LocationVirtual
Country/TerritoryItaly
CityRome
Period29/06/202102/07/2021

Fingerprint

Dive into the research topics of 'Efficient Local Computation of Differential Bisimulations via Coupling and Up-to Methods'. Together they form a unique fingerprint.

Cite this