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

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

1 Citationer (Scopus)

Abstrakt

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.
OriginalsprogEngelsk
Titel36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Antal sider14
ForlagIEEE
Publikationsdato2021
Sider1-14
ISBN (Trykt)978-1-6654-4896-3
ISBN (Elektronisk)978-1-6654-4895-6
DOI
StatusUdgivet - 2021
Begivenhed36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) - Virtual, Rome, Italien
Varighed: 29 jun. 20212 jul. 2021

Konference

Konference36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
LokationVirtual
Land/OmrådeItalien
ByRome
Periode29/06/202102/07/2021

Fingeraftryk

Dyk ned i forskningsemnerne om 'Efficient Local Computation of Differential Bisimulations via Coupling and Up-to Methods'. Sammen danner de et unikt fingeraftryk.

Citationsformater