Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich.
mehr Informationen...
Graph Grammars and Their Application to Computer Science, 1991, p.70-83
1991
Details
- Autor(en) / Beteiligte
- Titel
- An algebraic theory of graph reduction
- Ist Teil von
- Graph Grammars and Their Application to Computer Science, 1991, p.70-83
- Ort / Verlag
- Berlin, Heidelberg: Springer Berlin Heidelberg
- Erscheinungsjahr
- 1991
- Link zum Volltext
- Quelle
- Alma/SFX Local Collection
- Beschreibungen/Notizen
- We show how membership in classes of graphs definable in monadic second order logic and of bounded treewidth can be decided by finite sets of terminating reduction rules. The method is constructive in the sense that we describe an algorithm which will produce, from a formula in monadic second order logic and an integer k such that the class defined by the formula is of treewidth ≤ k, a set of rewrite rules that reduces any member of the class to one of finitely many graphs, in a number of steps bounded by the size of the graph. This reduction system corresponds to an algorithm that runs in time linear in the size of the graph.