Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01054459
Contributor : Hal Ifip <>
Submitted on : Wednesday, August 6, 2014 - 4:25:45 PM
Last modification on : Tuesday, March 20, 2018 - 2:50:05 PM
Long-term archiving on: : Wednesday, November 26, 2014 - 1:00:58 AM

File

03230198.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

304

Files downloads

354