On the recognizability of Arrow and Graph Languages
In this paper we give a category-based characterization of recognizability. A recognizable subset of arrows is de ned via a functor into the category of relations on sets, which can be seen as a straightforward generalization of a nite 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.
In diesem Papier geben wir eine kategoriebasierte Charakterisierung von Erkennbarkeit. Eine erkennbare Teilmenge von Pfeilen wird mit einem Funktor in die Kategorie von Relationen auf Mengen definiert. Dies kann als Verallgemeinerung eines endlichen Automaten gesehen werden. Im zweiten Teil des Papiers wenden wir die Theorie auf Graphen an, und wir zeigen, dass unser Ansatz eine Verallgemeinerung der Courcelles erkennbaren Graphsprachen ist.
Vorschau
Technische Berichte
Zitieren
Zitierform:
Zitierform konnte nicht geladen werden.