Please use this identifier to cite or link to this item:
Title: Strongly complete logics for coalgebras
Authors: Kurz, Alexander
Rosicky, Jiri
First Published: 12-Sep-2012
Publisher: IfCoLog (International Federation of Computational Logic)
Citation: Logical Methods in Computer Science, 2012, 8 (3), paper 14
Abstract: Coalgebras for a functor model different types of transition systems in a uniform way. This paper focuses on a uniform account of finitary logics for set-based coalgebras. In particular, a general construction of a logic from an arbitrary set-functor is given and proven to be strongly complete under additional assumptions. We proceed in three parts. Part I argues that sifted colimit preserving functors are those functors that preserve universal algebraic structure. Our main theorem here states that a functor preserves sifted colimits if and only if it has a finitary presentation by operations and equations. Moreover, the presentation of the category of algebras for the functor is obtained compositionally from the presentations of the underlying category and of the functor. Part II investigates algebras for a functor over ind-completions and extends the theorem of J{'o}nsson and Tarski on canonical extensions of Boolean algebras with operators to this setting. Part III shows, based on Part I, how to associate a finitary logic to any finite-sets preserving functor T. Based on Part II we prove the logic to be strongly complete under a reasonable condition on T.
DOI Link: 10.2168/LMCS-8(3:14)2012
ISSN: 1860-5974
Version: Publisher Version
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © the authors, 2012. This is an Open Access article distributed under the terms of the Creative Commons Attribution NoDerivs Licence ( ).
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
10.2168_LMCS-8(3-14)2012.pdfPublished (publisher PDF)442.48 kBUnknownView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.