{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T04:45:03Z","timestamp":1768884303548,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T00:00:00Z","timestamp":1645574400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T00:00:00Z","timestamp":1645574400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001538","name":"Victoria University of Wellington","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001538","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Hlin\u011bn\u00fd\u2019s Theorem shows that any sentence in the monadic second-order logic of matroids can be tested in polynomial time, when the input is limited to a class of <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathbb {F}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>F<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-representable matroids with bounded branch-width (where <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathbb {F}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>F<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a finite field). If each matroid in a class can be decomposed by a subcubic tree in such a way that only a bounded amount of information flows across displayed separations, then the class has bounded decomposition-width. We introduce the pigeonhole property for classes of matroids: if every subclass with bounded branch-width also has bounded decomposition-width, then the class is pigeonhole. An efficiently pigeonhole class has a stronger property, involving an efficiently-computable equivalence relation on subsets of the ground set. We show that Hlin\u011bn\u00fd\u2019s Theorem extends to any efficiently pigeonhole class. In a sequel paper, we use these ideas to extend Hlin\u011bn\u00fd\u2019s Theorem to the classes of fundamental transversal matroids, lattice path matroids, bicircular matroids, and <jats:inline-formula><jats:alternatives><jats:tex-math>$$H$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-gain-graphic matroids, where <jats:italic>H<\/jats:italic> is any finite group. We also give a characterisation of the families of hypergraphs that can be described via tree automata: a family is defined by a tree automaton if and only if it has bounded decomposition-width. Furthermore, we show that if a class of matroids has the pigeonhole property, and can be defined in monadic second-order logic, then any subclass with bounded branch-width has a decidable monadic second-order theory.\n<\/jats:p>","DOI":"10.1007\/s00453-022-00939-7","type":"journal-article","created":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T08:03:24Z","timestamp":1645603404000},"page":"1795-1834","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Tree Automata and Pigeonhole Classes of Matroids: I"],"prefix":"10.1007","volume":"84","author":[{"given":"Daryl","family":"Funk","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4086-0980","authenticated-orcid":false,"given":"Dillon","family":"Mayhew","sequence":"additional","affiliation":[]},{"given":"Mike","family":"Newman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,23]]},"reference":[{"key":"939_CR1","unstructured":"Bixby, R.E., Cunningham, W.H.: Matroid optimization and algorithms. In: Handbook of Combinatorics, vol. 1, 2, pp. 551\u2013609. Elsevier, Amsterdam (1995)"},{"issue":"6","key":"939_CR2","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1016\/j.jctb.2010.05.001","volume":"100","author":"JE Bonin","year":"2010","unstructured":"Bonin, J.E.: Lattice path matroids: the excluded minors. J. Comb. Theory Ser. B 100(6), 585\u2013599 (2010)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"939_CR3","first-page":"106, 16","volume":"18","author":"JE Bonin","year":"2011","unstructured":"Bonin, J.E., Kung, J.P.S., de Mier, A.: Characterizations of transversal and fundamental transversal matroids. Electron. J. Comb. 18(1), 106, 16 (2011)","journal-title":"Electron. J. Comb."},{"issue":"1","key":"939_CR4","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"4","key":"939_CR5","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1137\/0215066","volume":"15","author":"WH Cunningham","year":"1986","unstructured":"Cunningham, W.H.: Improved bounds for matroid partition and intersection algorithms. SIAM J. Comput. 15(4), 948\u2013957 (1986)","journal-title":"SIAM J. Comput."},{"key":"939_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.aam.2014.08.002","volume":"61","author":"M DeVos","year":"2014","unstructured":"DeVos, M., Funk, D., Pivotto, I.: When does a biased graph come from a group labelling? Adv. Appl. Math. 61, 1\u201318 (2014)","journal-title":"Adv. Appl. Math."},{"key":"939_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity. Monographs in Computer Science","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"939_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)"},{"key":"939_CR9","unstructured":"Engelfriet, J.: Tree automata and tree grammars. arXiv e-prints (2015). arXiv:1510.02036"},{"key":"939_CR10","unstructured":"Funk, D., Mayhew, D., Newman, M.: Tree automata and pigeonhole classes of matroids\u2014II. arXiv e-prints (2019). arXiv:1910.04361"},{"key":"939_CR11","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/haab020","author":"D Funk","year":"2021","unstructured":"Funk, D., Mayhew, D., Newman, M.: Defining bicircular matroids in monadic logic. Q. J. Math. (2021). https:\/\/doi.org\/10.1093\/qmath\/haab020","journal-title":"Q. J. Math."},{"issue":"7","key":"939_CR12","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1090\/noti1139","volume":"61","author":"J Geelen","year":"2014","unstructured":"Geelen, J., Gerards, B., Whittle, G.: Solving Rota\u2019s conjecture. Notices Am. Math. Soc. 61(7), 736\u2013743 (2014)","journal-title":"Notices Am. Math. Soc."},{"issue":"2","key":"939_CR13","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0095-8956(02)00046-1","volume":"88","author":"JF Geelen","year":"2003","unstructured":"Geelen, J.F., Gerards, A.M.H., Robertson, N., Whittle, G.P.: On the excluded minors for the matroids of branch-width $$k$$. J. Comb. Theory Ser. B 88(2), 261\u2013265 (2003)","journal-title":"J. Comb. Theory Ser. B"},{"key":"939_CR14","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd, P.: On matroid properties definable in the MSO logic. In: Mathematical Foundations of Computer Science 2003, volume 2747 of Lecture Notes in Comput. Sci., pp. 470\u2013479. Springer, Berlin (2003)","DOI":"10.1007\/978-3-540-45138-9_41"},{"issue":"3","key":"939_CR15","doi-asserted-by":"publisher","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 Ser. B 96(3), 325\u2013351 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"939_CR16","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1016\/j.tcs.2005.10.006","volume":"351","author":"P Hlin\u011bn\u00fd","year":"2006","unstructured":"Hlin\u011bn\u00fd, P., Seese, D.: Trees, grids, and MSO decidability: from graphs to matroids. Theor. Comput. Sci. 351(3), 372\u2013393 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"939_CR17","doi-asserted-by":"crossref","unstructured":"Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Automata Studies, Annals of Mathematics Studies, no 34, pp. 3\u201341. Princeton University Press, Princeton, NJ (1956)","DOI":"10.1515\/9781400882618-002"},{"issue":"6","key":"939_CR18","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1016\/j.dam.2011.03.016","volume":"160","author":"D Kr\u00e1l","year":"2012","unstructured":"Kr\u00e1l, D.: Decomposition width of matroids. Discrete Appl. Math. 160(6), 913\u2013923 (2012)","journal-title":"Discrete Appl. Math."},{"key":"939_CR19","doi-asserted-by":"crossref","unstructured":"Libkin, L.: Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2004)","DOI":"10.1007\/978-3-662-07003-1"},{"issue":"8","key":"939_CR20","doi-asserted-by":"publisher","first-page":"5907","DOI":"10.1090\/tran\/7408","volume":"370","author":"D Mayhew","year":"2018","unstructured":"Mayhew, D., Newman, M., Whittle, G.: Yes, the missing axiom of matroid theory is lost forever. Trans. Am. Math. Soc. 370(8), 5907\u20135929 (2018)","journal-title":"Trans. Am. Math. Soc."},{"issue":"4","key":"939_CR21","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S-I Oum","year":"2006","unstructured":"Oum, S.-I., Seymour, P.: Approximating clique-width and branch-width. J. Comb. Theory Ser. B 96(4), 514\u2013528 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"key":"939_CR22","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001","volume-title":"Matroid Theory","author":"J Oxley","year":"2011","unstructured":"Oxley, J.: Matroid Theory, 2nd edn. Oxford University Press, New York (2011)","edition":"2"},{"key":"939_CR23","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"issue":"2","key":"939_CR24","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0168-0072(91)90054-P","volume":"53","author":"D Seese","year":"1991","unstructured":"Seese, D.: The structure of the models of decidable monadic theories of graphs. Ann. Pure Appl. Logic 53(2), 169\u2013195 (1991)","journal-title":"Ann. Pure Appl. Logic"},{"key":"939_CR25","unstructured":"Strozecki, Y.: Enumeration Complexity and Matroid Decomposition. Ph.D. thesis, Universit\u00e9 Paris Diderot (2010)"},{"issue":"10","key":"939_CR26","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1016\/j.dam.2011.02.005","volume":"159","author":"Y Strozecki","year":"2011","unstructured":"Strozecki, Y.: Monadic second-order model-checking on decomposable matroids. Discrete Appl. Math. 159(10), 1022\u20131039 (2011)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00939-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00939-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00939-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T11:04:44Z","timestamp":1655982284000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00939-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,23]]},"references-count":26,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["939"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00939-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,23]]},"assertion":[{"value":"25 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}