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.
|Title of host publication||Proceedings of the 26th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXVI, Ottawa ON, Canada, May 6-10, 2010)|
|Editors||M. Mislove, P. Selinger|
|Publication status||Published - 2010|
|Name||Electronic Notes in Theoretical Computer Science|