Coalgebraic Predicate Logic

Litak T, Pattinson D, Sano K, Schröder L (2012)

Publication Type: Conference contribution, Original article

Publication year: 2012

Journal

Lecture Notes in Computer Science Springer Verlag

Publisher: Springer-verlag

Edited Volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Series: Lecture Notes in Ciomputer Science

City/Town: Berlin

Book Volume: 7392

Pages Range: 299-311

Conference Proceedings Title: Automata, Languages, and Programming

Event location: University of Warwick

ISBN: 9783642315848

URI: http://link.springer.com/chapter/10.1007/978-3-642-31585-5_29

DOI: 10.1007/978-3-642-31585-5_29

Abstract

We propose a generalization of first-order logic originating in a neglected work by C.C. Chang: a natural and generic correspondence language for any types of structures which can be recast as Set-coalgebras. We discuss axiomatization and completeness results for two natural classes of such logics. Moreover, we show that an entirely general completeness result is not possible. We study the expressive power of our language, contrasting it with both coalgebraic modal logic and existing first-order proposals for special classes of Set-coalgebras (apart for relational structures, also neighbourhood frames and topological spaces). The semantic characterization of expressivity is based on the fact that our language inherits a coalgebraic variant of the Van Benthem-Rosen Theorem. Basic model-theoretic constructions and results, in particular ultraproducts, obtain for the two classes which allow for completeness-and in some cases beyond that. © 2012 Springer-Verlag Berlin Heidelberg.

Authors with CRIS profile

Tadeusz Litak Lehrstuhl für Informatik 8 (Theoretische Informatik) Lutz Schröder Lehrstuhl für Informatik 8 (Theoretische Informatik)

Related research project(s)

Coalgebra-based generic decision procedures and complexity bounds for modal and hybrid logics (GenMod) May 1, 2008 - Sept. 30, 2016 Probabilistische Beschreibungslogik als Fragment der Probabilistischen Logik Erster Stufe (ProbDL) April 1, 2011 - April 1, 2014

Involved external institutions

Australian National University (ANU) AU Australia (AU) Hokkaido University (Hokudai) / 北海道大学 JP Japan (JP)

How to cite

APA:

Litak, T., Pattinson, D., Sano, K., & Schröder, L. (2012). Coalgebraic Predicate Logic. In Automata, Languages, and Programming (pp. 299-311). University of Warwick: Berlin: Springer-verlag.

MLA:

Litak, Tadeusz, et al. "Coalgebraic Predicate Logic." Proceedings of the 39th International Colloquium on Automata, Languages, and Programming , ICALP 2012, University of Warwick Berlin: Springer-verlag, 2012. 299-311.

BibTeX: Download