SAT Modulo Differential Equation Simulations

0531242 - ÚI 2021 RIV CH eng C - Conference Paper (international conference)
Kolárik, T. - Ratschan, Stefan
SAT Modulo Differential Equation Simulations.
Tests and Proofs. Cham: Springer, 2020 - (Ahrendt, W.; Wehrheim, H.), s. 80-99. Lecture Notes on Computer Science, 12165. ISBN 978-3-030-50994-1. ISSN 0302-9743.
[TAP 2020: The International Conference on Tests and Proofs /14./. Bergen (NO), 22.06.2020-23.06.2020]
Institutional support: RVO:67985807
Keywords : constraint solving * Boolean satisfiability * formal verification
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Differential equations are of immense importance for modeling physical phenomena, often in combination with discrete modeling formalisms. In current industrial practice, properties of the resulting models are checked by testing, using simulation tools. Research on SAT solvers that are able to handle differential equations has aimed at replacing tests by correctness proofs. However, there are fundamental limitations to such approaches in the form of undecidability, and moreover, the resulting solvers do not scale to problems of the size commonly handled by simulation tools. Also, in many applications, classical mathematical semantics of differential equations often does not correspond well to the actual intended semantics, and hence a correctness proof wrt. mathematical semantics does not ensure correctness of the intended system. In this paper, we head at overcoming those limitations by an alternative approach to handling differential equations within SAT solvers. This approach is usually based on the semantics used by tests in simulation tools, but still may result in mathematically precise correctness proofs wrt. that semantics. Experiments with a prototype implementation confirm the promise of such an approach.
Permanent Link: http://hdl.handle.net/11104/0309940