A Logic on Subobjects and Recognizability - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

A Logic on Subobjects and Recognizability

Résumé

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.
Fichier principal
Vignette du fichier
03230198.pdf (252.23 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01054459 , version 1 (06-08-2014)

Licence

Paternité

Identifiants

Citer

H. J. Sander Bruggink, Barbara König. A Logic on Subobjects and Recognizability. 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. pp.197-212, ⟨10.1007/978-3-642-15240-5_15⟩. ⟨hal-01054459⟩
90 Consultations
133 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More