Treewidth, pathwidth and cospan decompositions with applications to graph-accepting tree automata

J.J. Leifer, R. Milner, Deriving bisimulation congruences for reactive systems, in: Proceedings of CONCUR 2000, Lecture Notes in Computer Science, vol. 1877, Springer, 2000, pp. 243–258 . V. Sassone, P. Sobociński, Reactive systems over cospans, in: Proceedings of LICS '05, IEEE, 2005, pp. 311–320 . Robertson, 1986, Graph minors. II. Algorithmic aspects of tree width, Journal of Algorithms, 7, 309, 10.1016/0196-6774(86)90023-4 Courcelle, 1990, The monadic second-order logic of graphs I. Recognizable sets of finite graphs, Information and Computation, 85, 12, 10.1016/0890-5401(90)90043-H H.J.S. Bruggink, B. König, On the recognizability of arrow and graph languages, in: Proceedings of ICGT '08, Lecture Notes in Computer Science, vol. 5214, Springer, 2008, pp. 336–350. C. Blume, H.J.S. Bruggink, B. König, Recognizable graph languages for checking invariants, in: Proceedings of GT-VMT 2010, Electronic Communications of the EASST, vol. 29, 2010. Habel, 1993, A comparison of compatible, finite, and inductive graph properties, Theoretical Computer Science, 110, 145, 10.1016/0304-3975(93)90354-V H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison, M. Tommasi, Tree automata techniques and applications, Available from: 〈http://www.grappa.univ-lille3.fr/tata〉, 12 October 2007. F. Gécseg, M. Steinby, Tree Automata, Akadémiai Kiadó, Budapest, 1984. Habel, 1992, vol. 643 C. Lautemann, Decomposition trees: structured graph representation and efficient algorithms, in: Proceedings of CAAP '88, Lecture Notes in Computer Science, vol. 299, Springer, 1988, pp. 28–39. C. Lautemann, Tree automata, tree decomposition and hyperedge replacement, in: Proc. of Graph-Grammars and Their Application to Computer Science '90, Lecture Notes in Computer Science, Springer, 1991, pp. 520–537, 532. C. Blume, H.J.S. Bruggink, M. Friedrich, B. König, Treewidth, pathwidth and cospan decompositions, in: Proceedings of GT-VMT 2011, Electronic Communications of the EASST, vol. 41, 2011. Robertson, 1984, Graph minors. III. Planar tree-width, Journal of Combinatorial Theory, Series B, 36, 49, 10.1016/0095-8956(84)90013-3 Bauderon, 1987, Graph expressions and graph rewritings, Mathematical Systems Theory, 20, 83, 10.1007/BF01692060 F. Gadducci, R. Heckel, An inductive view of graph transformation, in: Proceedings of WADT '97 Lecture Notes in Computer Science, vol. 1376, 1997, pp. 223–237. Bozapalidis, 2006, Recognizability of graph and pattern languages, Acta Informatica, 42, 553, 10.1007/s00236-006-0006-z H.J.S. Bruggink, B. König, A logic on subobjects and recognizability, in: Proceedings of IFIP-TCS '10, IFIP-AICT, vol. 323, Springer, 2010, pp. 197–212 . H.J.S. Bruggink, M. Hülsbusch, Decidability and expressiveness of finitely representable recognizable graph languages, in: Proceedings of GT-VMT 2011, Electronic Communications of the EASST, vol. 41, 2011. C. Blume, Efficient implementation of automaton functors for the verification of graph transformation systems, in: Proceedings of ICGT '10, Proceedings of the Doctoral Symposium, Electronic Communications of the EASST, vol. 38, 2010. M. Friedrich, Baumautomaten und Baumzerlegungen für erkennbare Graphsprachen, Master's Thesis, Universität Duisburg-Essen, July 2010. Courcelle, 1997, The expression of graph properties and graph transformations in monadic second-order logic, vol. 1 Bodlaender, 1996, A linear time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing, 25, 1305, 10.1137/S0097539793251219 Bodlaender, 1996, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, Journal of Algorithms, 21, 358, 10.1006/jagm.1996.0049