Coalgebraic representation theory of fractals

I. Hasuo, B.P.F. Jacobs, M. Niqui

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

We develop a representation theory in which a point of a fractal specified by metric means (by a variant of an iterated function system, IFS) is represented by a suitable equivalence class of infinite streams of symbols. The framework is categorical: symbolic representatives carry a final coalgebra; an IFS-like metric specification of a fractal is an algebra for the same functor. Relating the two there canonically arises a representation map, much like in America and Rutten's use of metric enrichment in denotational semantics. A distinctive feature of our framework is that the canonical representation map is bijective. In the technical development, gluing of shapes in a fractal specification is a major challenge. On the metric side we introduce the notion of injective IFS to be used in place of conventional IFSs. On the symbolic side we employ Leinster's presheaf framework that uniformly addresses necessary identification of streams—such as .0111…=.1000… in the binary expansion of real numbers. Our leading example is the unit interval I=[0,1]. Keywords: Fractal; Coalgebra; Category Theory; Denotational Semantics; Real Number Computation.
Original languageEnglish
Title of host publicationProceedings of the 26th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXVI, Ottawa ON, Canada, May 6-10, 2010)
EditorsM. Mislove, P. Selinger
Pages351-368
DOIs
Publication statusPublished - 2010

Publication series

NameElectronic Notes in Theoretical Computer Science
Volume265
ISSN (Print)1571-0061

Fingerprint

Dive into the research topics of 'Coalgebraic representation theory of fractals'. Together they form a unique fingerprint.

Cite this