Computer Science Logic and 8th Kurt Gödel Colloquium
Nicolai Vorobjov: Effective model completeness of the theory of restricted Pfaffian functions
Welcome and News
Host Institutions
Calls and Deadlines
Social Program
Location and Venue
Colocated Events
Authors' instructions
Print current pagePrint this page
Pfaffian functions, introduced by Khovanskii in late 70s, are analytic functions satisfying triangular systems of first order partial differential equations with polynomial coefficients. They include for instance algebraic and elementary transcendental functions in the appropriate domains, iterated exponentials, and {\em fewnomials}. A simple example, due to Osgood, shows that the first order theory of reals expanded by restricted Pfaffian functions does not admit quantifier elimination. On the other hand, Gabrielov and Wilkie proved (non-constructively) that this theory is model complete, i.e., {\em one type} of quantifiers can be eliminated. The talk will explain some ideas behind recent algorithms for this {\em quantifier simplification} which are based on effective cylindrical cell decompositions of sub-Pfaffian sets. Complexities of these algorithms are essentially the same as the ones which existed for a particular case of semialgebraic sets.
© 2002-2003 Kurt Gödel Society, Norbert Preining. 2003-07-09 Valid HTML 4.01! Valid CSS! Debian