{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T15:58:29Z","timestamp":1778083109471,"version":"3.51.4"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,2,26]],"date-time":"2015-02-26T00:00:00Z","timestamp":1424908800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s00453-015-9977-x","type":"journal-article","created":{"date-parts":[[2015,2,25]],"date-time":"2015-02-25T14:52:56Z","timestamp":1424875976000},"page":"696-729","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Myhill\u2013Nerode Methods for Hypergraphs"],"prefix":"10.1007","volume":"73","author":[{"given":"Ren\u00e9","family":"van Bevern","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodney G.","family":"Downey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Serge","family":"Gaspers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,2,26]]},"reference":[{"key":"9977_CR1","unstructured":"Abrahamson, K.R., Fellows, M.R.: Cutset Regularity Beats Well-Quasi-Ordering for Bounded Treewidth. Tech. rep., Dept. Computer Science, University Victoria, Canada (1989)"},{"key":"9977_CR2","doi-asserted-by":"crossref","unstructured":"Abrahamson, K.R., Fellows, M.R.: Finite automata, bounded treewidth, and well-quasiordering. In: Graph Structure Theory, American Mathematical Society, Contemporary Mathematics, vol. 147, pp. 539\u2013564 (1991)","DOI":"10.1090\/conm\/147\/01199"},{"key":"9977_CR3","doi-asserted-by":"crossref","unstructured":"Bern, M.W., Lawler, E.L., Wong, A.L.: Why certain subgraph computations require only linear time. In: Proceedings of the 26th FOCS, IEEE Computer Society, pp. 117\u2013125 (1985)","DOI":"10.1109\/SFCS.1985.66"},{"key":"9977_CR4","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Downey, R.G., Fellows, M.R., Gaspers, S., Rosamond, F.A.: Myhill\u2013Nerode Methods for Hypergraphs. arXiv:1211.1299v5 [cs.DM] (2015)","DOI":"10.1007\/s00453-015-9977-x"},{"key":"9977_CR5","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Fellows, M.R., Gaspers, S., Rosamond, F.A.: Myhill\u2013Nerode methods for hypergraphs. In: Proceedings of the 24th ISAAC, LNCS, vol. 8283, pp. 372\u2013382. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-45030-3_35"},{"issue":"6","key":"9977_CR6","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9977_CR7","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"key":"9977_CR8","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fellows, M.R., Warnow, T.J.: Two strikes against perfect phylogeny. In: Proceedings of the 19th ICALP, LNCS, vol. 623, pp. 273\u2013283. Springer, Berlin (1992)","DOI":"10.1007\/3-540-55719-9_80"},{"key":"9977_CR9","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallett, M.T.: Beyond NP-completeness for problems of bounded width (extended abstract): hardness for the W hierarchy. In: Proceedings of the 26th STOC, pp. 449\u2013458. ACM (1994)","DOI":"10.1145\/195058.195229"},{"issue":"1\u20132","key":"9977_CR10","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0304-3975(98)00342-9","volume":"244","author":"HL Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallett, M.T., Wareham, H.T., Warnow, T.J.: The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theor. Comput. Sci. 244(1\u20132), 167\u2013188 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9977_CR11","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.jcss.2008.10.003","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Fellows, M.R., Thilikos, D.M.: Derivation of algorithms for cutwidth and related graph layout parameters. J. Comput. Syst. Sci. 75(4), 231\u2013244 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9977_CR12","doi-asserted-by":"crossref","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Solving problems on recursively constructed graphs. ACM Comput. Surv. 41(1) (2009). doi: 10.1145\/1456650.1456654","DOI":"10.1145\/1456650.1456654"},{"key":"9977_CR13","unstructured":"Cahoon, J., Sahni, S.: Exact algorithms for special cases of the board permutation problem. In: Proceedings of the 21st Annual Allerton Conference on Communication, Control, and Computing, pp. 246\u2013255 (1983)"},{"key":"9977_CR14","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic\u2014A Language-Theoretic Approach, Encyclopedia of mathematics and Its Applications, vol. 138. Cambridge University Press, Cambridge (2012)","DOI":"10.1017\/CBO9780511977619"},{"issue":"2","key":"9977_CR15","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1017\/S096012950000092X","volume":"6","author":"B Courcelle","year":"1996","unstructured":"Courcelle, B., Lagergren, J.: Equivalent definitions of recognizability for sets of graphs of bounded tree-width. Math. Struct. Comput. Sci. 6(2), 141\u2013165 (1996)","journal-title":"Math. Struct. Comput. Sci."},{"key":"9977_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9977_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"key":"9977_CR18","doi-asserted-by":"crossref","unstructured":"Fellows, M., Langston, M.: An analogue of the Myhill\u2013Nerode theorem and its use in computing finite-basis characterizations. In: Proceedings of the 30th FOCS, pp. 520\u2013525. IEEE Computer Society (1989)","DOI":"10.1109\/SFCS.1989.63528"},{"issue":"1","key":"9977_CR19","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1137\/0405010","volume":"5","author":"MR Fellows","year":"1992","unstructured":"Fellows, M.R., Langston, M.A.: On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM J. Discrete Math. 5(1), 117\u2013126 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"9977_CR20","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1016\/S0022-0000(05)80079-0","volume":"49","author":"MR Fellows","year":"1994","unstructured":"Fellows, M.R., Langston, M.A.: On search, decision, and the efficiency of polynomial-time algorithms. J. Comput. Syst. Sci. 49(3), 769\u2013779 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9977_CR21","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"MR Fellows","year":"2013","unstructured":"Fellows, M.R., Jansen, B.M.P., Rosamond, F.: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity. Eur. J. Combin. 34(3), 541\u2013566 (2013)","journal-title":"Eur. J. Combin."},{"key":"9977_CR22","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9977_CR23","unstructured":"Fomin, F.V., Golovach, P.A., Thilikos, D.M.: Approximating acyclicity parameters of sparse hypergraphs. In: Proceedings of the 26th STACS, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, LIPIcs, vol. 3, pp. 445\u2013456 (2009)"},{"issue":"7","key":"9977_CR24","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1016\/j.dam.2009.10.018","volume":"158","author":"R Ganian","year":"2010","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P.: On parse trees and Myhill\u2013Nerode-type tools for handling graphs of bounded rank-width. Discrete Appl. Math. 158(7), 851\u2013867 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9977_CR25","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"MR Garey","year":"1978","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S., Knuth, D.E.: Complexity results for bandwidth minimization. SIAM J. Appl. Math. 34(3), 477\u2013495 (1978)","journal-title":"SIAM J. Appl. Math."},{"key":"9977_CR26","unstructured":"Gaspers, S., Naroditskiy, V., Narodytska, N., Walsh, T.: Possible and necessary winner problem in social polls. In: Proceedings of the AAMAS\u201913, IFAAMAS, pp. 1131\u20131132 (2013)"},{"key":"9977_CR27","unstructured":"Gavril, F.: Some NP-complete problems on graphs. In: Proceedings of the 1977 Conference on Information Science and Systems, Johns Hopkins University, pp. 91\u201395 (1977)"},{"key":"9977_CR28","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Grohe, M., Musliu, N., Samer, M., Scarcello, F.: Hypertree decompositions: structure, algorithms, and applications. In: Proceedings of the 31st WG, LNCS, vol. 3787, pp. 1\u201315. Springer, Berlin (2005)","DOI":"10.1007\/11604686_1"},{"key":"9977_CR29","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Mikl\u00f3s, Z., Schwentick, T.: Generalized hypertree decompositions: NP-hardness and tractable variants. J. ACM 56(6) (2009). doi: 10.1145\/1568318.1568320","DOI":"10.1145\/1568318.1568320"},{"issue":"3","key":"9977_CR30","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2005.08.005","volume":"96","author":"P Hlin\u011bn\u00fd","year":"2006","unstructured":"Hlin\u011bn\u00fd, P.: Branch-width, parse trees, and monadic second-order logic for matroids. J. Comb. Theory B 96(3), 325\u2013351 (2006)","journal-title":"J. Comb. Theory B"},{"issue":"2","key":"9977_CR31","first-page":"302","volume":"61","author":"PG Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. J. Comput. Sci. 61(2), 302\u2013332 (2000)","journal-title":"J. Comput. Sci."},{"key":"9977_CR32","doi-asserted-by":"crossref","unstructured":"Komusiewicz, C., Niedermeier, R.: New races in parameterized algorithmics. In: Proceedings of the 37th MFCS, LNCS, vol. 7464, pp. 19\u201330. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32589-2_2"},{"key":"9977_CR33","doi-asserted-by":"crossref","unstructured":"Lagergren, J., Arnborg, S.: Finding minimal forbidden minors using a finite congruence. In: Proceedings of the 18th ICALP, LCNS, vol. 510, pp. 532\u2013543. Springer, Berlin (1991)","DOI":"10.1007\/3-540-54233-7_161"},{"issue":"3","key":"9977_CR34","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(86)90038-3","volume":"32","author":"N Lakshmipathy","year":"1986","unstructured":"Lakshmipathy, N., Winklmann, K.: \u201cGlobal\u201d graph problems tend to be intractable. J. Comput. Syst. Sci. 32(3), 407\u2013428 (1986)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2\u20133","key":"9977_CR35","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0166-218X(94)90025-6","volume":"54","author":"S Mahajan","year":"1994","unstructured":"Mahajan, S., Peters, J.G.: Regularity and locality in $$k$$ k -terminal graphs. Discrete Appl. Math. 54(2\u20133), 229\u2013250 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9977_CR36","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1145\/1721837.1721845","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Approximating fractional hypertree width. ACM Trans Algorithms 6(2), 29 (2010)","journal-title":"ACM Trans Algorithms"},{"issue":"1","key":"9977_CR37","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BF02090388","volume":"24","author":"Z Miller","year":"1991","unstructured":"Miller, Z., Sudborough, I.H.: A polynomial algorithm for recognizing bounded cutwidth in hypergraphs. Math. Syst. Theory 24(1), 11\u201340 (1991)","journal-title":"Math. Syst. Theory"},{"key":"9977_CR38","unstructured":"Myhill, J.: Finite Automata and Representation of Events. Tech. Rep. WADD TR-57-624, Wright-Patterson Air Force Base, Ohio, USA (1957)"},{"key":"9977_CR39","doi-asserted-by":"crossref","unstructured":"Nagamochi, H.: Linear layouts in submodular systems. In: Proceedings of the 23rd ISAAC, LNCS, vol. 7676, pp. 475\u2013484. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-35261-4_50"},{"issue":"4","key":"9977_CR40","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","volume":"9","author":"A Nerode","year":"1958","unstructured":"Nerode, A.: Linear automaton transformations. Proc. Am. Math. Soc. 9(4), 541\u2013544 (1958)","journal-title":"Proc. Am. Math. Soc."},{"key":"9977_CR41","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"9977_CR42","unstructured":"Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: Proceedings of the 27th STACS, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, LIPIcs, vol. 5, pp. 17\u201332 (2010)"},{"key":"9977_CR43","doi-asserted-by":"crossref","unstructured":"Prasad, M.R., Chong, P., Keutzer, K.: Why is ATPG easy? In: Proceedings of the 36th DAC, pp. 22\u201328. ACM (1999)","DOI":"10.1109\/DAC.1999.781224"},{"issue":"2","key":"9977_CR44","first-page":"103","volume":"76","author":"M Samer","year":"2010","unstructured":"Samer, M., Szeider, S.: Constraint satisfaction with bounded treewidth revisited. J. Comput. Sci. 76(2), 103\u2013114 (2010)","journal-title":"J. Comput. Sci."},{"issue":"1","key":"9977_CR45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth I: a linear time fixed parameter algorithm. J. Algorithms 56(1), 1\u201324 (2005)","journal-title":"J. Algorithms"},{"key":"9977_CR46","doi-asserted-by":"crossref","unstructured":"Wang, D., Clarke, E., Zhu, Y., Kukula, J.: Using cutwidth to improve symbolic simulation and Boolean satisfiability. In: Proceedings of the 6th HLDVT, pp. 165\u2013170. IEEE (2001)","DOI":"10.1109\/HLDVT.2001.972824"},{"key":"9977_CR47","unstructured":"Wimer, T.V.: Linear Algorithms on $$k$$ k -Terminal Graphs. PhD thesis, Clemson University (1987)"},{"key":"9977_CR48","first-page":"43","volume":"50","author":"TV Wimer","year":"1985","unstructured":"Wimer, T.V., Hedetniemi, S.T., Laskar, R.: A methodology for constructing linear graph algorithms. Congr. Numer. 50, 43\u201360 (1985)","journal-title":"Congr. Numer."},{"key":"9977_CR49","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Some complexity questions related to distributed computing. In: Proceedings of the 11th STOC, pp. 209\u2013213. ACM (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9977-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9977-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9977-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T07:35:30Z","timestamp":1566372930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9977-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,26]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["9977"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9977-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,26]]}}}