×

Tree automata and pigeonhole classes of matroids. I. (English) Zbl 1494.68136

The contribution translates the celebrated result of Courcelle, which shows that testing whether a graph of limited tree-width satisfies a given monadic second-order formula is efficient, to the realm of matroids, which are the algebraic structures used for correct greedy algorithms. More precisely, the theorem is adjusted for efficiently pigeonhole matroids. Roughly speaking, matroids are the algebraic structures that form the basis for the correctness of many greedy algorithms. The pigeonhole property of a class \(\mathcal{C}\) of matroids essentially requires that every subclass of \(\mathcal{C}\) that has bounded branch-width also has bounded decomposition-width. Efficiently pigeonhole additionally requires that a certain equivalence relation can efficiently be determined. With the help of the translation the contribution shows that for an efficiently pigeonhole class of matroids and a sentence in counting monadic second-order logic it can efficiently be tested whether a given matroid from the class fulfills the conditions expressed in the logic.
The authors present full details on the tree automaton approach that is already used in the proof of Courcelle’s theorem. All major basic constructions are presented and proved anew in their special setting, which benefits readers that are unfamiliar with tree automata theory. However, the main notions from matroid theory are glossed over rather quickly and it is essentially assumed that the reader is familiar with matroid theory. The relevant references are provided in all cases. Additional examples would have been welcome.
Overall, the contribution is formally self-contained, but readers without a background in matroids will find it a difficult reading. Readers with some background in tree automata theory will be surprised to find many basic constructions (product, etc.) with full proof details.

MSC:

68Q45 Formal languages and automata
03D05 Automata and formal grammars in connection with logical questions
05B35 Combinatorial aspects of matroids and geometric lattices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bixby, R.E., Cunningham, W.H.: Matroid optimization and algorithms. In: Handbook of Combinatorics, vol. 1, 2, pp. 551-609. Elsevier, Amsterdam (1995) · Zbl 0848.05017
[2] Bonin, JE, Lattice path matroids: the excluded minors, J. Comb. Theory Ser. B, 100, 6, 585-599 (2010) · Zbl 1231.05054 · doi:10.1016/j.jctb.2010.05.001
[3] Bonin, JE; Kung, JPS; de Mier, A., Characterizations of transversal and fundamental transversal matroids, Electron. J. Comb., 18, 1, 106, 16 (2011) · Zbl 1233.05077
[4] Courcelle, B., The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inf. Comput., 85, 1, 12-75 (1990) · Zbl 0722.03008 · doi:10.1016/0890-5401(90)90043-H
[5] Cunningham, WH, Improved bounds for matroid partition and intersection algorithms, SIAM J. Comput., 15, 4, 948-957 (1986) · Zbl 0619.68040 · doi:10.1137/0215066
[6] DeVos, M.; Funk, D.; Pivotto, I., When does a biased graph come from a group labelling?, Adv. Appl. Math., 61, 1-18 (2014) · Zbl 1371.05113 · doi:10.1016/j.aam.2014.08.002
[7] Downey, RG; Fellows, MR, Parameterized Complexity. Monographs in Computer Science (1999), New York: Springer, New York · doi:10.1007/978-1-4612-0515-9
[8] Downey, RG; Fellows, MR, Fundamentals of Parameterized Complexity. Texts in Computer Science (2013), London: Springer, London · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1
[9] Engelfriet, J.: Tree automata and tree grammars. arXiv e-prints (2015). arXiv:1510.02036
[10] Funk, D., Mayhew, D., Newman, M.: Tree automata and pigeonhole classes of matroids—II. arXiv e-prints (2019). arXiv:1910.04361
[11] Funk, D.; Mayhew, D.; Newman, M., Defining bicircular matroids in monadic logic, Q. J. Math. (2021) · Zbl 07499694 · doi:10.1093/qmath/haab020
[12] Geelen, J.; Gerards, B.; Whittle, G., Solving Rota’s conjecture, Notices Am. Math. Soc., 61, 7, 736-743 (2014) · Zbl 1338.05039 · doi:10.1090/noti1139
[13] Geelen, JF; Gerards, AMH; Robertson, N.; Whittle, GP, On the excluded minors for the matroids of branch-width \(k\), J. Comb. Theory Ser. B, 88, 2, 261-265 (2003) · Zbl 1032.05027 · doi:10.1016/S0095-8956(02)00046-1
[14] Hliněný, 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-479. Springer, Berlin (2003) · Zbl 1124.68373
[15] Hliněný, P., Branch-width, parse trees, and monadic second-order logic for matroids, J. Comb. Theory Ser. B, 96, 3, 325-351 (2006) · Zbl 1088.05022 · doi:10.1016/j.jctb.2005.08.005
[16] Hliněný, P.; Seese, D., Trees, grids, and MSO decidability: from graphs to matroids, Theor. Comput. Sci., 351, 3, 372-393 (2006) · Zbl 1093.03006 · doi:10.1016/j.tcs.2005.10.006
[17] Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Automata Studies, Annals of Mathematics Studies, no 34, pp. 3-41. Princeton University Press, Princeton, NJ (1956) · Zbl 0074.11204
[18] Král, D., Decomposition width of matroids, Discrete Appl. Math., 160, 6, 913-923 (2012) · Zbl 1241.05013 · doi:10.1016/j.dam.2011.03.016
[19] Libkin, L.: Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2004) · Zbl 1060.03002
[20] Mayhew, D.; Newman, M.; Whittle, G., Yes, the missing axiom of matroid theory is lost forever, Trans. Am. Math. Soc., 370, 8, 5907-5929 (2018) · Zbl 1522.05028 · doi:10.1090/tran/7408
[21] Oum, S-I; Seymour, P., Approximating clique-width and branch-width, J. Comb. Theory Ser. B, 96, 4, 514-528 (2006) · Zbl 1114.05022 · doi:10.1016/j.jctb.2005.10.006
[22] Oxley, J., Matroid Theory (2011), New York: Oxford University Press, New York · Zbl 1254.05002 · doi:10.1093/acprof:oso/9780198566946.001.0001
[23] Rabin, MO; Scott, D., Finite automata and their decision problems, IBM J. Res. Dev., 3, 114-125 (1959) · Zbl 1461.68105 · doi:10.1147/rd.32.0114
[24] Seese, D., The structure of the models of decidable monadic theories of graphs, Ann. Pure Appl. Logic, 53, 2, 169-195 (1991) · Zbl 0733.03026 · doi:10.1016/0168-0072(91)90054-P
[25] Strozecki, Y.: Enumeration Complexity and Matroid Decomposition. Ph.D. thesis, Université Paris Diderot (2010) · Zbl 1287.68082
[26] Strozecki, Y., Monadic second-order model-checking on decomposable matroids, Discrete Appl. Math., 159, 10, 1022-1039 (2011) · Zbl 1225.05073 · doi:10.1016/j.dam.2011.02.005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.