2008-03: On the recognizability of Arrow and Graph Languages

Derivate 20228

471.2 KB in one file, last changed at 10.07.2008

File list / details

FileFiles changed onSize
techreport200803.pdf10.07.2008 14:44:22471.2 KB
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.
Bookmark:
Permalink | Share/Save
Dokumententyp:
Wissenschaftliche Texte » Heft, Band
Fakultät / Institut:
Fakultät für Ingenieurwissenschaften » Informatik und Angewandte Kognitionswissenschaft » Informatik » Theoretische Informatik
Dewey Dezimal-Klassifikation:
000 Informatik, Informationswissenschaft, allgemeine Werke » 000 Informatik, Wissen, Systeme » 004 Datenverarbeitung; Informatik
Keywords:
Recognizability, Graph Languages
Language:
Englisch
Collection / Status:
E-Publications / Document published
Files changed on:
10.07.2008
Medientyp:
Text