Herde Efficient Solving of Large Arithmetic Constraint Systems with Complex Boolean Structure

Proof Engines for the Analysis of Hybrid Discrete-Continuous Systems
2011
ISBN: 978-3-8348-9949-1
Verlag: Vieweg & Teubner
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 163 Seiten, eBook

Christian Herde deals with the development of decision procedures as needed, e.g., for automatic verification of hardware and software systems via bounded model checking. He provides methods for efficiently solving formulae comprising complex Boolean combinations of linear, polynomial, and transcendental arithmetic constraints, involving thousands of Boolean-, integer-, and real-valued variables.

Dr. Christian Herde completed his doctoral thesis under the supervision of Prof. Dr. Martin Fränzle at the Department of Computing Science at the University of Oldenburg, Germany.

Zielgruppe

Research

Autoren/Hrsg.

Herde, Christian

Inhaltsverzeichnis

1;Foreword;6
2;Acknowledgements;7
3;Abstract;8
4;Zusammenfassung;10
5;Contents;12
6;List of Figures;14
7;List of Tables;16
8;1 Introduction;17
8.1;1.1 Formal Verification Using Satisfiability Checking;17
8.2;1.2 Bounded Model Checking of Hybrid Systems;19
8.3;1.3 Solvers for Boolean Combinations of Numerical Constraints;21
8.3.1;1.3.1 Constraint Solving in a Nutshell;22
8.3.2;1.3.2 Contributions of the Thesis;25
8.3.3;1.3.3 Structure;28
8.3.4;1.3.4 Sources;28
9;2 Hybrid Dynamical Systems;30
9.1;2.1 Modeling Hybrid Systems with Hybrid Automata;31
9.2;2.2 Predicative Encodings of Hybrid Automata;38
9.2.1;2.2.1 A Basic Encoding Scheme;39
9.2.2;2.2.2 Hybridization of Continuous Dynamics;45
9.2.3;2.2.3 Encoding Flows Using Taylor Expansions;48
10;3 Extending DPLL for Pseudo-Boolean Constraints;51
10.1;3.1 The Logics;53
10.2;3.2 State of the Art in SAT Solving;54
10.2.1;3.2.1 Conversion into CNF;56
10.2.2;3.2.2 SAT Checkers for CNFs;59
10.3;3.3 Optimizing DPLL-Based Pseudo-Boolean Solvers;63
10.3.1;3.3.1 DPLL for Pseudo-Boolean Constraints;64
10.3.2;3.3.2 Generalization of Lazy Clause Evaluation;65
10.3.3;3.3.3 Learning in Presence of Pseudo-Boolean Constraints;67
10.4;3.4 Benchmark Results;69
10.5;3.5 Discussion;71
11;4 Integration of DPLL-SAT and Linear Programming;73
11.1;4.1 The Logics;74
11.2;4.2 Lazy Approach to SMT;76
11.3;4.3 SAT Modulo the Theory of Linear Arithmetic;77
11.3.1;4.3.1 Feasibility Check Using LP;79
11.3.2;4.3.2 Extractions of Explanations;79
11.3.3;4.3.3 Learning from Feasible LPs;82
11.3.4;4.3.4 Putting It All Together: a Sample Run;82
11.4;4.4 Optimizations for BMC;84
11.5;4.5 Benchmark Results;86
11.6;4.6 Discussion;88
12;5 Integration of DPLL and Interval Constraint Solving;94
12.1;5.1 The Logics;98
12.2;5.2 Algorithmic Basis;101
12.3;5.3 The ISAT Algorithm;103
12.3.1;5.3.1 Definitional Translation into Conjunctive Form;103
12.3.2;5.3.2 Split-and-Deduce Search;107
12.3.3;5.3.3 Arithmetic Deduction Rules;111
12.3.4;5.3.4 Correctness;117
12.3.5;5.3.5 Algorithmic Enhancements;122
12.3.6;5.3.6 Progress and Termination;125
12.4;5.4 Benchmark Results;127
12.4.1;5.4.1 Impact of Conflict-Driven Learning;127
12.4.2;5.4.2 Comparison to ABSOLVER;128
12.4.3;5.4.3 Comparison to HYSAT-1;132
12.5;5.5 Reachability Analysis with HYSAT-2: a Case Study;132
12.5.1;5.5.1 ETCS Model;133
12.5.2;5.5.2 Encoding into HySAT;137
12.5.3;5.5.3 Results;141
12.6;5.6 Discussion;143
13;6 Conclusion;145
13.1;6.1 Achievements;145
13.2;6.2 Perspectives;147
13.3;6.3 Final Thoughts;155
14;Bibliography;157
15;Index;171

Hybrid Dynamical Systems; Extending DPLL for Pseudo-Boolean Constraints; Integration of DPLL-SAT and Linear Programming; Integration of DPLL and Interval Constraint Solving

Über Autor(innen)

Dr. Christian Herde completed his doctoral thesis under the supervision of Prof. Dr. Martin Fränzle at the Department of Computing Science at the University of Oldenburg, Germany.