On the recognizability of arrow and graph languages


H.J. Sander Bruggink and Barbara König. On the recognizability of arrow and graph languages. Technical Report 2008-03, Universität Duisburg-Essen, 2008.


In this paper we give a category-based characterization of recognizability. A recognizable subset of arrows is defined via a functor into the category of relations on sets, which can be seen as a straightforward generalization of a finite automaton. In the second part of the paper we apply the theory to graphs, and we show that our approach is a generalization of Courcelle's recognizable graph languages.

Suggested BibTeX entry:

    author = {H.J. Sander Bruggink and Barbara K{\"o}nig},
    institution = {Universit{\"a}t {D}uisburg-{E}ssen},
    number = {2008-03},
    series = {Technische {B}erichte der {A}bteilung f{\"u}r {I}nformatik und angewandte {K}ognitionswissenschaften},
    title = {On the recognizability of arrow and graph languages},
    year = {2008}

PDF (471 kB)Conference version
© University of Duisburg-Essen, Theoretical Computer Science group