Erratum to: Analyzing restricted fragments of the theory of linear arithmetic

1. Basu, S., Pollack, R., Roy, M.-F.: Existential theory of the reals, volume 10 of algorithms and computation in mathematics. Springer, Berlin (2006)

   Google Scholar 

2. Berman, L.: The complexity of logical theories. Theor. Comput. Sci. 11, 71–77 (1980)

   Article  MathSciNet  MATH  Google Scholar 

3. Bialas, W.F., Karwan, M.H.: Two-level linear programming. Manag. Sci. 30 (8), 1004–1020 (1984)

   Article  MathSciNet  MATH  Google Scholar 

4. Bradley, A.R., Manna, Z.: The calculus of computation - decision procedures with applications to verification, first edition. Springer, Berlin (2007)

   MATH  Google Scholar 

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

   Article  MATH  Google Scholar 

6. Büning, H.K., Karpinski, M., Flögel, A.: Resolution for quantified boolean formulas. Inf. Comput. 117(1), 12–18 (1995)

   Article  MathSciNet  MATH  Google Scholar 

7. Canny, J.: Some algebraic and geometric computations in PSPACE. Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, 460–467 (1988)

8. Choi, S., Agrawala, A.: Dynamic dispatching of cyclic real-time tasks with relative timing constraints. Real-Time Syst. 19(1), 5–40 (2000)

   Article  Google Scholar 

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

   Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

13. Dolzmann, A., Sturm, T., Weispfenning, V.: Real quantifier elimination in practice. In: Matzat, B.H., et al. (eds.) Algorithmic Algebra and Number Theory, pages 221–248. Springer (1998)

    Google Scholar 

14. Eirinakis, P., Ruggieri, S., Subramani, K., Wojciechowski, P.: On quantified linear implications. Ann. Math. Artif. Intell. 71(4), 301–325 (2014)

    Article  MathSciNet  MATH  Google Scholar 

15. Ferrante, J., Rackoff, C.: A decision procedure for the first order theory of real addition with order. SIAM J. Comput. 4(1), 69–76 (1975)

    Article  MathSciNet  MATH  Google Scholar 

16. Gerber, R., Pugh, W., Saksena, M.: Parametric dispatching of hard real-time tasks. IEEE Trans. Comput. 44(3), 471–479 (1995)

    Article  MATH  Google Scholar 

17. Hall, R.J.: Specification, validation, and synthesis of email agent controllers: A case study in function rich reactive system design. Autom. Softw. Eng. 9(3), 233–261 (2002)

    Article  MATH  Google Scholar 

18. Harel, D.: A grand challenge for computing: Towards full reactive modeling of a multi-cellular animal. Verification, Model Checking, Abstr. Interpretation 2937, 39–60 (2004)

    MATH  Google Scholar 

19. Kam, N., Cohen, I.R., Harel, D.: The immune system as a reactive system: modeling t cell activation with statecharts Proceedings of the 2001 IEEE Symposia on Human-Centric Computing Languages and Environments, pp 15–22 (2001)

    Google Scholar 

20. Khachiyan, L.G.: A polynomial algorithm in linear programming. Doklady Akademiia Nauk SSSR 224, 1093–1096 (1979). English Translation: Soviet Mathematics Doklady, Volume 20, pp. 1093–1096

    MathSciNet  MATH  Google Scholar 

21. Koo, T.J., Sinopoli, B., Sangiovanni-Vincentelli, A., Sastry, S.: A formal approach to reactive system design: unmanned aerial vehicle flight management system design example Proceedings of the 1999 IEEE International Symposium on Computer Aided Control System Design, pp 522–527 (1999)

    Google Scholar 

22. Christos, H.: Papadimitriou computational complexity Addison-Wesley (1994)

23. Pfitzmann, B., Waidner, M.: Composition and integrity preservation of secure reactive systems Proceedings of the 2000 ACM Conference on Computer Communications Security, pp 245–254 (2000)

    Google Scholar 

24. Pfitzmann, B., Waidner, M.: A model for asynchronous reactive systems and its application to secure message transmission Proceedings of the 2001 IEEE Symposium on Security and Privacy, pp 184–200 (2001)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

26. Ratschan, S.: RSOLVER. http://rsolver.sourceforge.net (2013)

27. Schaefer, M., Umans, C.: Completeness in the polynomial-time hierarchy A compendium. SIGACT News 33(3), 32–49 (2002)

    Article  Google Scholar 

28. Schaefer, M., Umans, C.: Completeness in the polynomial-time hierarchy Part II. SIGACT News 33(4), 22–36 (2002)

    Article  Google Scholar 

29. Schrijver, A.: Theory of linear and integer programming. John Wiley and Sons, New York (1987)

    MATH  Google Scholar 

30. Shor, P.W.: Stretchability of pseudolines is NP-hard. DIMACS 4, 531–534 (1991)

    MathSciNet  MATH  Google Scholar 

31. Sontag, E.D.: Real addition and the polynomial hierarchy. Inf. Process. Lett. 20 (3), 115–120 (1985)

    Article  MathSciNet  MATH  Google Scholar 

32. Stockmeyer, L.J.: The polynomial-time hierarchy. Theor. Comput. Sci. 3, 1–22 (1977)

    Article  MathSciNet  MATH  Google Scholar 

33. Subramani, K.: On a decision procedure for quantified linear programs. Ann. Math. Artif. Intell. 51(1), 55–77 (2007)

    Article  MathSciNet  MATH  Google Scholar 

34. Tarski, A.: A decision method for elementary algebra and geometry. Technical report r-109 rand corporation (1948)

35. Weispfenning, V.: The complexity of linear problems in fields. J. Symb. Comput. 4(1-2), 3–27 (1988)

    Article  MathSciNet  MATH  Google Scholar 

Download references