Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism

Abiteboul, 2000 Aho, 1974 Andersson, 1998, Sorting in linear time?, J. Comput. System Sci., 57, 74, 10.1006/jcss.1998.1580 Baeza-Yates, 1992, A new approach to text searching, Commun. ACM, 35, 74, 10.1145/135239.135243 Benedikt, 2008, XPath leashed, ACM Comput. Surv., 41, 1, 10.1145/1456650.1456653 Bille, 2006, New algorithms for regular expression matching, vol. 4051, 643 Bille, 2005, A survey on tree edit distance and related problems, Theoret. Comput. Sci., 337, 217, 10.1016/j.tcs.2004.12.030 Bille, 2011, The tree inclusion problem: In optimal space and faster, ACM Trans. Algorithms, 7, 1, 10.1145/1978782.1978793 Bruno, 2002, Holistic twig joins: Optimal XML pattern matching, 310 Chen, 1998, More efficient algorithm for ordered tree inclusion, J. Algorithms, 26, 370, 10.1006/jagm.1997.0899 Gottlob, 2002, Monadic queries over tree-structured data, 189 Gottlob, 2005, Efficient algorithms for processing XPath queries, ACM Trans. Database Syst., 30, 444, 10.1145/1071610.1071614 Gottlob, 2006, Conjunctive queries over trees, J. ACM, 53, 238, 10.1145/1131342.1131345 Götz, 2009, Efficient algorithms for descendant-only tree pattern queries, Inf. Syst., 34, 602, 10.1016/j.is.2009.03.010 Hoffmann, 1982, Pattern matching in trees, J. ACM, 29, 68, 10.1145/322290.322295 Jordan, 1869, Sur les assemblages de lignes, J. Reine Angew. Math., 70, 185, 10.1515/crll.1869.70.185 Kaneta, 2010, Fast bit-parallel matching for network and regular expressions, vol. 6393, 372 P. Kilpeläinen, Tree matching problems with applications to structured text databases, Ph.D. thesis, Report A-1992-6, Department of Computer Science, University of Helsinki, November 1992. Kilpeläinen, 1995, Ordered and unordered tree inclusion, SIAM J. Comput., 24, 340, 10.1137/S0097539791218202 Knuth, 2009 Kosaraju, 1989, Efficient tree pattern matching, 178 Leighton, 1992 Martens, 2006, Expressiveness and complexity of XML schema, ACM Trans. Database Syst., 31, 770, 10.1145/1166074.1166076 Murata, 2005, Taxonomy of XML schema languages using formal language theory, ACM Trans. Internet Technol., 5, 660, 10.1145/1111627.1111631 Myers, 1992, A four Russian algorithm for regular expression pattern matching, J. ACM, 39, 430, 10.1145/128749.128755 Navarro, 2002 F. Neven, T. Schwentick, Expressive and efficient pattern languages for tree-structured data, in: Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODSʼ00), 2000, pp. 145–156. Olteanu, 2004, Evaluating complex queries against xml streams with polynomial combined complexity, vol. 3112, 31 Tsuji, 2005, A bit-parallel tree matching algorithm for patterns with horizontal VLDCʼs, vol. 3772, 388 Valiente, 2005, Constrained tree inclusion, J. Discrete Algorithms, 3, 431, 10.1016/j.jda.2004.08.017 Vigna, 2008, Broadword implementation of rank/select queries, vol. 5038, 154 W3C Warren, 1977, Functions realizable with word-parallel logical and twoʼs-complement addition instructions, Commun. ACM, 20, 439, 10.1145/359605.359632 Warren, 2003 Wu, 1992, Fast text searching: allowing errors, Commun. ACM, 35, 83, 10.1145/135239.135244 Yamamoto, 2009, Bit-parallel tree pattern matching algorithms for unordered labeled trees, vol. 5664, 554