[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Real World Verification

  • Conference paper
Automated Deduction – CADE-22 (CADE 2009)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 5663))

Included in the following conference series:

Abstract

Scalable handling of real arithmetic is a crucial part of the verification of hybrid systems, mathematical algorithms, and mixed analog/digital circuits. Despite substantial advances in verification technology, complexity issues with classical decision procedures are still a major obstacle for formal verification of real-world applications, e.g., in automotive and avionic industries. To identify strengths and weaknesses, we examine state of the art symbolic techniques and implementations for the universal fragment of real-closed fields: approaches based on quantifier elimination, Gröbner Bases, and semidefinite programming for the Positivstellensatz. Within a uniform context of the verification tool KeYmaera, we compare these approaches qualitatively and quantitatively on verification benchmarks from hybrid systems, textbook algorithms, and on geometric problems. Finally, we introduce a new decision procedure combining Gröbner Bases and semidefinite programming for the real Nullstellensatz that outperforms the individual approaches on an interesting set of problems.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Tarski, A.: A Decision Method for Elementary Algebra and Geometry, 2nd edn. University of California Press, Berkeley (1951)

    MATH  Google Scholar 

  2. Ratschan, S.: Efficient solving of quantified inequality constraints over the real numbers. ACM Trans. Comput. Log. 7, 723–748 (2006)

    Article  MathSciNet  Google Scholar 

  3. Collins, G.E., Hong, H.: Partial cylindrical algebraic decomposition for quantifier elimination. J. Symb. Comput. 12, 299–328 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  4. Weispfenning, V.: Quantifier elimination for real algebra - the quadratic case and beyond. Appl. Algebra Eng. Commun. Comput. 8, 85–101 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  5. Buchberger, B.: An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal. PhD thesis, University of Innsbruck (1965)

    Google Scholar 

  6. Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96, 293–320 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  7. Stengle, G.: A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Math. Ann. 207, 87–97 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  8. Platzer, A., Quesel, J.D.: KeYmaera: A hybrid theorem prover for hybrid systems. In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS, vol. 5195, pp. 171–178. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  9. Brown, C.W.: QEPCAD B: A program for computing with semi-algebraic sets using CADs. SIGSAM Bull. 37, 97–108 (2003)

    Article  MATH  Google Scholar 

  10. Dolzmann, A., Sturm, T.: Redlog: Computer algebra meets computer logic. ACM SIGSAM Bull. 31, 2–9 (1997)

    Article  Google Scholar 

  11. McLaughlin, S., Harrison, J.: A proof-producing decision procedure for real arithmetic. In: Nieuwenhuis, R. (ed.) CADE 2005. LNCS, vol. 3632, pp. 295–314. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  12. Borchers, B.: CSDP, a C library for semidefinite programming. Optimization Methods and Software 11, 613–623 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  13. Harrison, J.: Verifying nonlinear real formulas via sums of squares. In: Schneider, K., Brandt, J. (eds.) TPHOLs 2007. LNCS, vol. 4732, pp. 102–118. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  14. Platzer, A.: Differential dynamic logic for hybrid systems. J. Autom. Reasoning 41, 143–189 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  15. Beckert, B., Hähnle, R., Schmitt, P.H. (eds.): Verification of Object-Oriented Software: The KeY Approach. LNCS, vol. 4334. Springer, Heidelberg (2007)

    Google Scholar 

  16. Platzer, A., Quesel, J.D., Rümmer, P.: Real world verification. Reports of SFB/TR 14 AVACS 52, SFB/TR 14 AVACS (2009) ISSN: 1860-9821, http://www.avacs.org

  17. Rümmer, P.: A sequent calculus for integer arithmetic with counterexample generation. In: Beckert, B. (ed.) VERIFY 2007 at CADE, Bremen, Germany. CEUR-WS.org, vol. 259 (2007)

    Google Scholar 

  18. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986)

    MATH  Google Scholar 

  19. Platzer, A.: Combining deduction and algebraic constraints for hybrid system analysis. In: Beckert, B. (ed.) VERIFY 2007 at CADE, Bremen, Germany. CEUR Workshop Proceedings, vol. 259, pp. 164–178. CEUR-WS.org (2007)

    Google Scholar 

  20. Davenport, J.H., Heintz, J.: Real quantifier elimination is doubly exponential. J. Symb. Comput. 5, 29–35 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  21. Strzebonski, A.W.: Cylindrical algebraic decomposition using validated numerics. J. Symb. Comput. 41, 1021–1038 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  22. Bochnak, J., Coste, M., Roy, M.F.: Real Algebraic Geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 36. Springer, Heidelberg (1998)

    Book  MATH  Google Scholar 

  23. Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge Univ. Press, Cambridge (2004)

    Book  MATH  Google Scholar 

  24. Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Longman, Amsterdam (1994)

    MATH  Google Scholar 

  25. Platzer, A., Quesel, J.D.: Logical verification and systematic parametric analysis in train control. In: Egerstedt, M., Mishra, B. (eds.) HSCC 2008. LNCS, vol. 4981, pp. 646–649. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  26. Kovács, L.: Aligator: A mathematica package for invariant generation (system description). In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS, vol. 5195, pp. 275–282. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  27. de Moura, L.M., Bjørner, N.: Z3: An efficient SMT solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 337–340. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  28. Dolzmann, A., Sturm, T., Weispfenning, V.: A new approach for automatic theorem proving in real geometry. J. Autom. Reason. 21, 357–380 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  29. Nipkow, T.: Linear quantifier elimination. In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS, vol. 5195, pp. 18–33. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  30. Tiwari, A.: An algebraic approach for the unsatisfiability of nonlinear constraints. In: Ong, C.H.L. (ed.) CSL 2005. LNCS, vol. 3634, pp. 248–262. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  31. Akbarpour, B., Paulson, L.C.: Extending a resolution prover for inequalities on elementary functions. In: Dershowitz, N., Voronkov, A. (eds.) LPAR 2007. LNCS, vol. 4790, pp. 47–61. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  32. Warren, A., Hunt, J., Krug, R.B., Moore, J.S.: Linear and nonlinear arithmetic in ACL2. In: Geist, D., Tronci, E. (eds.) CHARME 2003. LNCS, vol. 2860, pp. 319–333. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  33. Platzer, A., Clarke, E.M.: Computing differential invariants of hybrid systems as fixedpoints. In: Gupta, A., Malik, S. (eds.) CAV 2008. LNCS, vol. 5123, pp. 176–189. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Carnegie Mellon University, Pittsburgh, PA, USA

    André Platzer

  2. University of Oldenburg, Germany

    Jan-David Quesel

  3. Computing Laboratory, Oxford University, UK

    Philipp Rümmer

Authors
  1. André Platzer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jan-David Quesel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Philipp Rümmer
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Computer Science, The University of Manchester, Manchester, UK

    Renate A. Schmidt

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Platzer, A., Quesel, JD., Rümmer, P. (2009). Real World Verification. In: Schmidt, R.A. (eds) Automated Deduction – CADE-22. CADE 2009. Lecture Notes in Computer Science(), vol 5663. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02959-2_35

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02959-2_35

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02958-5

  • Online ISBN: 978-3-642-02959-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation