Solving Linear Differential Problems with Parameters

  • Volker Weispfenning
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3718)


We present algorithms for parametric problems in differential algebra that can be formulated in a suitable first-order language L. The atomic L-formulas are linear ODEs of arbitrary order with parametric coefficients of arbitrary degrees. Using rather weak axioms on differential fields or differential algebras that are realized in natural function domains, we establish explicit quantifier elimination algorithms for L providing also parametric sample solutions for purely existential problems. These sample solutions are “generic” solutions of univariate parametric linear ODEs that can be realized by concrete functions in the natural function domains mentioned above. We establish upper complexity bounds for the elimination algorithms that are elementary recursive for formulas of bounded quantifier alternation, in particular doubly exponential for existential formulas. Our results are in contrast to Seidenberg’s model theoretic elimination theory for non-linear problems that is non elementary recursive, requires very strong axioms that are not realizable in natural function domains, and does not provide sample solutions.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Seidenberg, A.: An elimination theory for differential algebra. Univ. California Publ. Math (N.S.) 3, 31–66 (1956)MathSciNetGoogle Scholar
  2. 2.
    Robinson, A.: Complete theories. North-Holland, Amsterdam (1956)zbMATHGoogle Scholar
  3. 3.
    Robinson, A.: Relative model-completeness and the elimination of quantifiers. In: Kreisler, H.J., Körner, S., Luxemburg, W.A., Young, A.D. (eds.) Abraham Robinson. Selected Papers, vol. 1, pp. 146–159. Yale University Press, New Haven (1979); Originally in Dialectica 12, pp. 394–407 (1958); M.R. 21 #1265Google Scholar
  4. 4.
    Robinson, A.: On the concept of a differentially closed field. In: Kreisler, H.J., Körner, S., Luxemburg, W.A., Young, A.D. (eds.) Abraham Robinson. Selected Papers, vol. 1, pp. 440–455. Yale University Press, New Haven (1979); Originally in Bull. Res. Council Israel 8F, 113–128. M.R. 23 #2323 (1959)Google Scholar
  5. 5.
    Blum, L.: Generalized Algebraic Structures: A Model Theoretical Approach. Ph.D. thesis, MIT, Cambridge, MA (1968)Google Scholar
  6. 6.
    Blum, L.: Differentially closed fields: A model theoretic tour. In: Bass, H., Cassidy, P.J., Kovacic, J. (eds.) Contributions to Algebra. A Collection of Papers Dedicated to Ellis Kolchin, pp. 37–61. Academic Press, New York (1977)Google Scholar
  7. 7.
    Dolzmann, A., Sturm, T.: Generalized constraint solving over differential algebras. In: Ganzha, V.G., Mayr, E.M., Vorozhtsov, E.V. (eds.) Proceedings CASC 2004, TUM (2004)Google Scholar
  8. 8.
    Ritt, J.F.: Differential Algebra. AMS, New York (1950)zbMATHGoogle Scholar
  9. 9.
    Schnorr, C.P.: Rekursive Funktionen und ihre Komplexität. Teubner (1974)Google Scholar
  10. 10.
    Sturm, T., Weispfenning, V.: Quantifier elimination in term algebras. In: Computer Algebra in Scientific Computation - CASC 2002, pp. 285–330. TU München (2002)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Volker Weispfenning
    • 1
  1. 1.University of PassauGermany

Personalised recommendations