Aarhus University Seal / Aarhus Universitets segl

Solutions of generalized recursive metric-space equations

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Lars Birkedal
  • Kristian Støvring, IT University of Copenhagen, Denmark
  • Jacob Thamsborg, IT University of Copenhagen, Denmark
t is well known that one can use an adaptation of the inverse-limit construction to solve recursive
equations in the category of complete ultrametric spaces. We show that this construction generalizes
to a large class of categories with metric-space structure on each set of morphisms: the exact nature of
the objects is less important. In particular, the construction immediately applies to categories where
the objects are ultrametric spaces with ‘extra structure’, and where the morphisms preserve this extra
structure. The generalization is inspired by classical domain-theoretic work by Smyth and Plotkin.
Our primary motivation for solving generalized recursive metric-space equations comes from recent
and ongoing work on Kripke-style models in which the sets of worlds must be recursively defined.
For many of the categories we consider, there is a natural subcategory in which each set of
morphisms is required to be a compact metric space. Our setting allows for a proof that such a
subcategory always inherits solutions of recursive equations from the full category.
As another application, we present a construction that relates solutions of generalized domain
equations in the sense of Smyth and Plotkin to solutions of equations in our class of categories
Original languageEnglish
Title of host publication6th Workshop on Fixed Points in Computer Science, FICS 2009 : Coimbr a, P ortugal, 12-13 September 2009, Proceedings
EditorsRalph Matthes, Tarmo Uustalu
Number of pages7
PublisherInstitute of Cybernetics at Tallinn University of Technology
Publication year2009
ISBN (print)978-9949-430-29-1
Publication statusPublished - 2009
Externally publishedYes

See relations at Aarhus University Citationformats

ID: 81420781