Observational ultraproducts of polynomial coalgebras

Annals of Pure and Applied Logic 123 (1-3):235-290 (2003)
  Copy   BIBTEX

Abstract

Coalgebras of polynomial functors constructed from sets of observable elements have been found useful in modelling various kinds of data types and state-transition systems. This paper continues the study of equational logic and model theory for polynomial coalgebras begun in Goldblatt , where it was shown that Boolean combinations of equations between terms of observable type form a natural language of observable formulas for specifying properties of polynomial coalgebras, and for giving a Hennessy–Milner style logical characterisation of observational indistinguishability of states.Here we give a structural characterisation of classes of coalgebras definable by observable formulas. This is an analogue for polynomial coalgebras of Birkhoff's celebrated characterisation of equationally definable classes of abstract algebras as being those closed under homomorphic images, subalgebras, and direct products. The coalgebraic characterisation involves new notions of observational ultraproduct and ultrapower of coalgebras, obtained from the classical construction of ultraproducts by deleting states that assign “nonstandard” values to terms of observable type. A class of polynomial coalgebras is shown to be the class of all models of a set of observable formulas if, and only if, it is closed under images of bisimulation relations, disjoint unions and observational ultrapowers.Observational ultraproducts are also used to discuss compactness—which holds only under limited conditions; to characterise finitely, axiomatisable classes of polynomial coalgebras; and to show that there are axiomatisable classes that are not finitely axiomatisable

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Expressive Logics for Coalgebras via Terminal Sequence Induction.Dirk Pattinson - 2004 - Notre Dame Journal of Formal Logic 45 (1):19-33.
Final coalgebras and the Hennessy–Milner property.Robert Goldblatt - 2006 - Annals of Pure and Applied Logic 138 (1):77-93.
Coalgebras, Chu Spaces, and Representations of Physical Systems.Samson Abramsky - 2013 - Journal of Philosophical Logic 42 (3):551-574.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
Light affine lambda calculus and polynomial time strong normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
Polynomial clone reducibility.Quinn Culver - 2014 - Archive for Mathematical Logic 53 (1-2):1-10.
Applications of PCF theory.Saharon Shelah - 2000 - Journal of Symbolic Logic 65 (4):1624-1674.
Polynomial time operations in explicit mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.

Analytics

Added to PP
2014-01-16

Downloads
15 (#809,553)

6 months
2 (#670,035)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references