Logic in Computer Science (LICS 2005)

Paper: Inverse and Implicit Functions in Domain Theory (at LICS 2005)

Authors: Abbas Edalat Dirk Pattinson

Abstract

We construct a domain-theoretic calculus for Lipschitz and differentiable functions, which includes addition, subtraction and composition. We then develop a domain-theoretic version of the inverse function theorem for a Lipschitz function, in which the inverse function is obtained as a fixed point of a Scott continuous functional and is approximated by step functions. In the case of a C1 function, the inverse and its derivative are obtained as the least fixed point of a single Scott continuous functional on the domain of differentiable functions and are approximated by two sequences of step functions, which are effectively computed from two increasing sequences of step functions respectively converging to the original function and its derivative. In this case, we also effectively obtain an increasing sequence of polynomial step functions whose lower and upper bounds converge in the C1 norm to the inverse function. A similar result holds for implicit functions, which combined with the domain-theoretic model for computational geometry, provides a robust technique for construction of curves and surfaces.

BibTeX

  @InProceedings{EdalatPattinson-InverseandImplicitF,
    author = 	 {Abbas Edalat and Dirk Pattinson},
    title = 	 {Inverse and Implicit Functions in Domain Theory},
    booktitle =  {Proceedings of the Twentieth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2005},
    year =	 2005,
    editor =	 {Prakash Panangaden},
    month =	 {June}, 
    pages =      {417--426},
    location =   {Chicago, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }