A Logic on Subobjects and Recognizability

Abstract : We introduce a simple logic that allows to quantify over the subobjects of a categorical object. We subsequently show that, for the category of graphs, this logic is equally expressive as second-order monadic graph logic (msogl). Furthermore we show that for the more general setting of hereditary pushout categories, a class of categories closely related to adhesive categories, we can recover Courcelle's result that every msogl-expressible property is recognizable. This is done by giving an inductive translation of formulas of our logic into so-called automaton functors which accept recognizable languages of cospans.
Type de document :
Communication dans un congrès
Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.197-212, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_15〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01054459
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 août 2014 - 16:25:45
Dernière modification le : mardi 20 mars 2018 - 14:50:05
Document(s) archivé(s) le : mercredi 26 novembre 2014 - 01:00:58

Fichier

03230198.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

H. J. Sander Bruggink, Barbara König. A Logic on Subobjects and Recognizability. Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.197-212, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_15〉. 〈hal-01054459〉

Partager

Métriques

Consultations de la notice

130

Téléchargements de fichiers

116