2018/08/08 by H. J. Sander Bruggink, Barbara König · 1 citation
Computer Science · #semigroups and automata theory #Logic, programming, and type systems #Advanced Graph Theory Research
paper · doi:10.1017/s096012951800018x
openalex publication_date 2018/08/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
In this article, we generalize Courcelle's recognizable graph languages and results on monadic second-order logic to more general structures. First, we give a category-theoretical characterization of recognizability. A recognizable subset of arrows in a category is defined via a functor into the category of relations on finite sets. This can be seen as a straightforward generalization of finite automata. We show that our notion corresponds to recognizable graph languages if we apply the theory to the category of cospans of graphs. In the second part of the paper, we introduce a simple logic that allows to quantify over the subobjects of a categorical object. Again, we show that, for the category of graphs, this logic is equally expressive as monadic second-order graph logic ( msogl ). Furthermore, we show that in 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 automaton functors.