Bruggink, Sander; König, Barbara:
On the recognizability of arrow and graph languages
Essen: Abteilung für Informatik und Angewandte Kognitionswissenschaft, Fakultät für Ingenieurwissenschaften, Universität Duisburg-Essen, 2008
(Technischer Bericht ; 2008-3)
Buch / Fach: Informatik
Fakultät für Ingenieurwissenschaften » Informatik und Angewandte Kognitionswissenschaft » Informatik » Theoretische Informatik
Titel:
On the recognizability of arrow and graph languages
Autor(in):
Bruggink, Sander im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen; König, Barbara im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen
Erscheinungsort:
Essen
Verlag:
Abteilung für Informatik und Angewandte Kognitionswissenschaft, Fakultät für Ingenieurwissenschaften, Universität Duisburg-Essen
Erscheinungsjahr:
2008
In Serie:
Technischer Bericht, Band 2008-3
Umfang:
27
DuEPublico ID:
URN:
Link URL:

Abstract:

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.