The Fixed-Point Theory of Strictly Contracting Functions on Generalized Ultrametric Semilattices

Eleftherios Matsikoudis
(University of California, Berkeley)
Edward A. Lee
(University of California, Berkeley)

We introduce a new class of abstract structures, which we call generalized ultrametric semilattices, and in which the meet operation of the semilattice coexists with a generalized distance function in a tightly coordinated way. We prove a constructive fixed-point theorem for strictly contracting functions on directed-complete generalized ultrametric semilattices, and introduce a corresponding induction principle. We cite examples of application in the semantics of logic programming and timed computation, where, until now, the only tool available has been the non-constructive fixed-point theorem of Priess-Crampe and Ribenboim for strictly contracting functions on spherically complete generalized ultrametric semilattices.

In David Baelde and Arnaud Carayol: Proceedings Workshop on Fixed Points in Computer Science (FICS 2013), Turino, Italy, September 1st, 2013, Electronic Proceedings in Theoretical Computer Science 126, pp. 56–71.
Published: 28th August 2013.

ArXived at: https://dx.doi.org/10.4204/EPTCS.126.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org