Reading Guide for Publications by André Platzer

Landmark Papers

My most important landmark papers are

• The logic, compositional proof calculus, and the first relative completeness result for hybrid systems in 2008 [27] based on [30]
• The article introducing differential invariants, differential variants, and a verification logic for more general hybrid systems and differential-algebraic hybrid systems with differential inequalities in 2008 [26]
• The procedures for computing differential invariants [23][19]
• The first logic and the first relatively complete compositional proof calculus for distributed hybrid systems [5]
• The first compositional verification approach and logic for stochastic hybrid systems [1]

My book [6] also contains more information.

Important Applications

My most important verified applications are

• Air traffic collision avoidance [11] with the first formal verification results for fully curved flight.
• European train control system ETCS [10]
• Distributed adaptive cruise control [3]

Publication Reading Guide

The primary paper for logic for hybrid systems verification appeared in the Journal of Automated Reasoning [27]. For a first understanding the logical approach to hybrid systems verification, I also recommend a conference paper [30] that introduces the first logic for hybrid systems that can be used to verify actual hybrid systems. This paper does not contain all details, but is a shorter read to start with. The major paper giving a detailed exploration of logic for hybrid systems verification and the theory behind KeYmaera, is the longer journal article [27]. This article also explains several aspects that are important for automation, including real generalizations of free variables and Skolem functions. This article is a major breakthrough, because it presents and proves the first sound and relatively complete axiomatization of hybrid systems relative to differential equations. This shows that hybrid systems verification can be reduced by recursive decomposition to elementary properties of differential equations.

A brief overview about the tool KeYmaera itself is reported in a tool paper [22]. But this paper does not describe all capabilities of KeYmaera, it describes a very outdated version of KeYmaera, and it only gives an overview of the features and refers to other articles for the actual verification techniques [27][26][6]. A more comprehensive survey on using logic for hybrid systems and the KeYmaera tool can be found in the CAV tutorial [2].

Another major step is the handling of more complex differential equations by an approach that I call differential invariants, which were first introduced in 2008 [26]. This article also presents an advanced verification logic for hybrid systems that can even have disturbances and differential inequalities in the dynamics. This work has been the basis for subsequent automatic verification techniques to compute differential invariants [23][19]. Applications of these verification techniques have been described for air traffic control [11] and train control [10]. A comprehensive treatment of logic for hybrid systems, its theory, practice, and applications, can be found in my book [6].

In a recent breakthrough [5], I have presented the first verification approach for distributed hybrid systems and a logic for distributed hybrid systems. This paper also presents verification technique for reconfigurable distributed hybrid systems. Extensions to distributed hybrid systems with complicated continuous dynamics can be found in [4]

Numerical techniques and the image computation problem for hybrid systems are discussed in a paper at HSCC'07 [35]. This paper further discusses computable versions of Weierstrass approximation theorems and their limits. The paper also shows that a stochastic view of hybrid systems, as later pursued in statistical model checking [8], is possible at all. A more comprehensive verification approach and logic for stochastic hybrid systems can be found in [1].

Publications

1. André Platzer.
   Stochastic differential dynamic logic for stochastic hybrid programs.
   In Nikolaj Bjørner and Viorica Sofronie-Stokkermans, editors, International Conference on Automated Deduction, CADE'11, Wroclaw, Poland, Proceedings, volume 6803 of LNCS, pages 431-445. Springer, 2011. © Springer-Verlag
   [bib | pdf | doi | TR]
   
   
2. André Platzer.
   Logic and compositional verification of hybrid systems.
   In Ganesh Gopalakrishnan and Shaz Qadeer, editors, Computer Aided Verification, CAV 2011, Snowbird, UT, USA, Proceedings, volume 6806 of LNCS, pages 28-43. Springer, 2011. © Springer-Verlag
   Invited tutorial.
   [bib | pdf | doi | slides]
   
   
3. Sarah M. Loos, André Platzer, and Ligia Nistor.
   Adaptive cruise control: Hybrid, distributed, and now formally verified.
   In Michael Butler and Wolfram Schulte, editors, 17th International Symposium on Formal Methods, FM, Limerick, Ireland, Proceedings, volume 6664 of LNCS, pages 42-56. Springer, 2011. © Springer-Verlag
   [bib | pdf | doi | study | TR]
   
   
4. André Platzer.
   Quantified differential invariants.
   In Emilio Frazzoli and Radu Grosu, editors, Proceedings of the 14th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2011, Chicago, USA, April 12-14, Pages 63-72. ACM, 2011. © ACM
   [bib | pdf | doi]
   
   
5. André Platzer.
   Quantified differential dynamic logic for distributed hybrid systems.
   In Anuj Dawar and Helmut Veith, editors, Computer Science Logic, 19th EACSL Annual Conference, CSL 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings, volume 6247 of LNCS, pages 469-483. Springer, 2010. © Springer-Verlag
   [bib | pdf | doi | TR]
   
   
6. André Platzer.
   Logical Analysis of Hybrid Systems: Proving Theorems for Complex Dynamics.
   Springer, 2010. 426 p. ISBN 978-3-642-14508-7.
   [bib | book | doi | web]
   
   
7. Paolo Zuliani, André Platzer, and Edmund M. Clarke.
   Bayesian Statistical Model Checking with Application to Simulink/Stateflow Verification.
   School of Computer Science, Carnegie Mellon University, CMU-CS-10-100, 2010.
   [bib | pdf | HSCC'10]
   
   
8. Paolo Zuliani, André Platzer, and Edmund M. Clarke.
   Bayesian statistical model checking with application to Simulink/Stateflow verification.
   In Karl Henrik Johansson and Wang Yi, editors, Proceedings of the 13th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2010, Stockholm, Sweden, April 12-15, pages 243-252. ACM, 2010. © ACM
   [bib | pdf | report | doi | TR]
   
   
9. André Platzer and Jan-David Quesel.
   European Train Control System: A Case Study in Formal Verification.
   Reports of SFB/TR 14 AVACS 54, 2009. ISSN: 1860-9821, www.avacs.org.
   [bib | pdf | study | ICFEM'09]
   
   
10. André Platzer and Jan-David Quesel.
    European Train Control System: A case study in formal verification.
    In Karin Breitman and Ana Cavalcanti, editors, 11th International Conference on Formal Engineering Methods, ICFEM, Rio de Janeiro, Brasil, Proceedings, volume 5885 of LNCS, pages 246-265. Springer, 2009. © Springer-Verlag
    [bib | pdf | doi | slides | study | TR]
    
    
11. André Platzer and Edmund M. Clarke.
    Formal verification of curved flight collision avoidance maneuvers: A case study.
    In Ana Cavalcanti and Dennis Dams, editors, 16th International Symposium on Formal Methods, FM, Eindhoven, Netherlands, Proceedings, volume 5850 of LNCS, pages 547-562. Springer, 2009. © Springer-Verlag
    This paper was awarded the FM Best Paper Award.
    [bib | pdf | doi | slides | study | TR]
    
    
12. André Platzer and Edmund M. Clarke.
    Formal Verification of Curved Flight Collision Avoidance Maneuvers: A Case Study.
    School of Computer Science, Carnegie Mellon University, CMU-CS-09-147, 2009.
    [bib | pdf | study | FM'09]
    
    
13. André Platzer.
    Verification of cyberphysical transportation systems.
    IEEE Intelligent Systems, 24(4), pages 10-13, Jul/Aug, 2009. © IEEE.
    Invited paper.
    [bib | doi]
    
    
14. Sumit Kumar Jha, Edmund Clarke, Christopher Langmead, Axel Legay, André Platzer, and Paolo Zuliani.
    A Bayesian approach to model checking biological systems.
    In Pierpaolo Degano and Roberto Gorrieri, editors, Computational Methods in Systems Biology, 7th International Conference, CMSB 2009, Bologna, Italy, Proceedings, volume 5688 of LNCS, pages 218-234. Springer, 2009. © Springer-Verlag
    [bib | pdf | doi | TR]
    
    
15. Sumit Kumar Jha, Edmund Clarke, Christopher Langmead, Axel Legay, André Platzer, and Paolo Zuliani.
    A Bayesian Approach to Model Checking Biological Systems.
    School of Computer Science, Carnegie Mellon University, CMU-CS-09-110, 2009.
    [bib | pdf | CMSB'09]
    
    
16. André Platzer.
    Differential dynamic logic: Automated theorem proving for hybrid systems.
    Künstliche Intelligenz, 24(1), pages 75-77, 2010. © Springer-Verlag
    Invited paper.
    [bib | doi]
    
    
17. André Platzer, Jan-David Quesel, and Philipp Rümmer.
    Real World Verification.
    Reports of SFB/TR 14 AVACS 52, 2009. ISSN: 1860-9821, www.avacs.org.
    [bib | pdf | CADE'09]
    
    
18. André Platzer, Jan-David Quesel, and Philipp Rümmer.
    Real world verification.
    In Renate A. Schmidt, editor, International Conference on Automated Deduction, CADE'09, Montreal, Canada, Proceedings, volume 5663 of LNCS, pages 485-501. Springer, 2009. © Springer-Verlag
    Introduces a decision procedure for universal nonlinear real arithmetic combining Gröbner bases and semidefinite programming for the Real Nullstellensatz. An extended set of real arithmetic benchmarks from KeYmaera is available in smtlib, including the examples from CADE'09 paper and other KeYmaera-related papers.
    [bib | pdf | doi | smtlib | TR]
    
    
19. André Platzer and Edmund M. Clarke.
    Computing differential invariants of hybrid systems as fixedpoints.
    Formal Methods in System Design, 35(1), pages 98-120, 2009. © Springer-Verlag
    [bib | pdf | doi | study]
    
    
20. Edmund M. Clarke, Bruce Krogh, André Platzer, and Raj Rajkumar.
    Analysis and verification challenges for cyber-physical transportation systems.
    In NITRD National Workshop for Research on Transportation Cyber-Physical Systems: Automotive, Aviation, and Rail, 2008.
    Position paper.
    [bib | pdf]
    
    
21. André Platzer.
    Differential Dynamic Logics: Automated Theorem Proving for Hybrid Systems.
    PhD Thesis, Department of Computing Science, University of Oldenburg, 2008.
    Appeared with Springer as Logical Analysis of Hybrid Systems: Proving Theorems for Complex Dynamics.
    [bib]
    
    
22. André Platzer and Jan-David Quesel.
    KeYmaera: A hybrid theorem prover for hybrid systems.
    In Alessandro Armando, Peter Baumgartner, and Gilles Dowek, editors, Automated Reasoning, Fourth International Joint Conference, IJCAR 2008, Sydney, Australia, Proceedings, volume 5195 of LNCS, pages 171-178. Springer, 2008. © Springer-Verlag
    [bib | pdf | doi | slides | tool]
    
    
23. André Platzer and Edmund M. Clarke.
    Computing differential invariants of hybrid systems as fixedpoints.
    In Aarti Gupta and Sharad Malik, editors, Computer Aided Verification, CAV 2008, Princeton, USA, Proceedings, volume 5123 of LNCS, pages 176-189, Springer, 2008. © Springer-Verlag
    [bib | pdf | doi | study | TR]
    
    
24. André Platzer and Edmund M. Clarke.
    Computing Differential Invariants of Hybrid Systems as Fixedpoints.
    School of Computer Science, Carnegie Mellon University, CMU-CS-08-103, Feb, 2008.
    [bib | pdf | study | CAV'08]
    
    
25. André Platzer and Jan-David Quesel.
    Logical verification and systematic parametric analysis in train control.
    In Magnus Egerstedt and Bud Mishra, editors, Hybrid Systems: Computation and Control, 11th International Conference, HSCC 2008, St. Louis, USA, Proceedings, volume 4981 of LNCS, pages 646-649. Springer, 2008. © Springer-Verlag
    [bib | pdf | doi]
    
    
26. André Platzer.
    Differential-algebraic dynamic logic for differential-algebraic programs.
    Journal of Logic and Computation, 20(1), pages 309-352, 2010. Advance Access published on November 18, 2008 by Oxford University Press.
    [bib | pdf | doi | example]
    
    
27. André Platzer.
    Differential dynamic logic for hybrid systems.
    Journal of Automated Reasoning, 41(2), pages 143-189, 2008. © Springer-Verlag
    [bib | pdf | doi | example]
    
    
28. André Platzer.
    Combining deduction and algebraic constraints for hybrid system analysis.
    In Bernhard Beckert, editor, 4th International Verification Workshop, VERIFY'07, Workshop at Conference on Automated Deduction (CADE), Bremen, Germany, CEUR Workshop Proceedings, 259:164-178, 2007.
    [bib | pdf]
    
    
29. Werner Damm, Alfred Mikschl, Jens Oehlerking, Ernst-Rüdiger Olderog, Jun Pang, André Platzer, Marc Segelken, and Boris Wirtz.
    Automating verification of cooperation, control, and design in traffic applications.
    In Cliff Jones, Zhiming Liu, and Jim Woodcock, editors, Formal Methods and Hybrid Real-Time Systems, volume 4700 of LNCS, pages 115-169. Springer, 2007. © Springer-Verlag
    Invited paper.
    [bib | pdf | doi]
    
    
30. André Platzer.
    Differential dynamic logic for verifying parametric hybrid systems.
    In Nicola Olivetti, editor, Automated Reasoning with Analytic Tableaux and Related Methods, International Conference, TABLEAUX 2007, Aix en Provence, France, July 3-6, 2007, Proceedings, volume 4548 of LNCS, pages 216-232. Springer, 2007. © Springer-Verlag
    This paper was awarded the TABLEAUX Best Paper Award.
    [bib | pdf | doi | slides | example | TR]
    
    
31. André Platzer.
    Differential Dynamic Logic for Verifying Parametric Hybrid Systems.
    Reports of SFB/TR 14 AVACS 15, May 2007. ISSN: 1860-9821, www.avacs.org.
    [bib | pdf | TABLEAUX'07]
    
    
32. André Platzer.
    A temporal dynamic logic for verifying hybrid system invariants.
    In Sergei Artemov and Anil Nerode, editors, Logical Foundations of Computer Science, International Symposium, LFCS 2007, New York, USA, Proceedings, volume 4514 of LNCS, pages 457-471. Springer, 2007. © Springer-Verlag
    [bib | pdf | doi | slides | example | TR]
    
    
33. André Platzer.
    A Temporal Dynamic Logic for Verifying Hybrid System Invariants.
    Reports of SFB/TR 14 AVACS 12, February 2007. ISSN: 1860-9821, www.avacs.org.
    [bib | pdf | LFCS'07]
    
    
34. André Platzer.
    Differential logic for reasoning about hybrid systems.
    In Alberto Bemporad, Antonio Bicchi, and Giorgio Buttazzo, editors, Hybrid Systems: Computation and Control, 10th International Conference, HSCC 2007, Pisa, Italy, Proceedings, volume 4416 of LNCS, pages 746-749. Springer, 2007. © Springer-Verlag
    [bib | pdf | doi]
    
    
35. André Platzer and Edmund M. Clarke.
    The image computation problem in hybrid systems model checking.
    In A. Bemporad, A. Bicchi, and G. Buttazzo, editors, Hybrid Systems: Computation and Control, 10th International Conference, HSCC 2007, Pisa, Italy, Proceedings, volume 4416 of LNCS, pages 473-486. Springer, 2007, © Springer-Verlag
    [bib | pdf | doi | slides]
    
    
36. Stephanie Kemper and André Platzer.
    SAT-based abstraction refinement for real-time systems.
    In Frank S. de Boer and Vladimir Mencl, editors, Formal Aspects of Component Software, Third International Workshop, FACS 2006, Prague, Czech Republic, Proceedings, Electr. Notes Theor. Comput. Sci., 182:107-122, 2007
    [bib | pdf | doi | slides]
    
    
37. André Platzer.
    Towards a hybrid dynamic logic for hybrid dynamic systems.
    In Patrick Blackburn, Thomas Bolander, Torben Braüner, Valeria de Paiva, and Jørgen Villadsen, editors, Proc., International Workshop on Hybrid Logic, HyLo 2006, Seattle, USA, Electr. Notes Theor. Comput. Sci. 174(6):63-77, 2007.
    [bib | pdf | doi]
    
    
38. Bernhard Beckert and André Platzer.
    Dynamic logic with non-rigid functions: A basis for object-oriented program verification.
    In U. Furbach and N. Shankar, editors, Automated Reasoning, Third International Joint Conference, IJCAR 2006, Seattle, WA, USA, August 17-20, 2006, Proceedings, volume 4130 of LNCS, pages 266-280. Springer, 2006. © Springer-Verlag
    [bib | pdf | doi | slides]
    
    
39. André Platzer.
    An Object-oriented Dynamic Logic with Updates.
    Master's Thesis, University of Karlsruhe, Department of Computer Science. Institute for Logic, Complexity and Deduction Systems, September 2004.
    [bib | pdf]
    
    
40. André Platzer.
    Using a Program Verification Calculus for Constructing Specifications from Implementations.
    Minor Thesis (Studienarbeit), University of Karlsruhe, Department of Computer Science. Institute for Logic, Complexity and Deduction Systems, February 2004.
    [bib | pdf]