Isolated suborders and their application to counting closure operators. (English) Zbl 07906373
Summary: In this paper we investigate the interplay between isolated suborders and closures. Isolated suborders are a special kind of suborders and can be used to diminish the number of elements of an ordered set by means of a quotient construction. The decisive point is that there are simple formulae establishing relationships between the number of closures in the original ordered set and the quotient thereof induced by isolated suborders. We show how these connections can be used to derive a recursive algorithm for counting closures, provided the ordered set under consideration contains suitable isolated suborders.
References:
| [1] | R. Glück Vol. 20:3 11:12 R. Glück Vol. 20:3 |
| [2] | N. Alpay, P. Jipsen, and M. Sugimoto. Unary-determined distributive ℓ-magmas and bunched implication algebras. In U. Fahrenberg, M. Gehrke, L. Santocanale, and M. Winter, editors, Relational and Algebraic Methods in Computer Science -19th International Conference, RAMiCS 11:20 R. Glück Vol. 20:3 |
| [3] | 2021, Marseille, France, November 2-5, 2021, Proceedings, volume 13027 of Lecture Notes in Computer Science, pages 19-36. Springer, 2021. doi:10.1007/978-3-030-88701-8_2. · doi:10.1007/978-3-030-88701-8_2 |
| [4] | J. Alman and V. V. Williams. A refined laser method and faster matrix multiplication. In D. Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 -13, 2021, pages 522-539. SIAM, 2021. doi:10.1137/1. 9781611976465.32. · doi:10.1137/1.9781611976465.32 |
| [5] | R. Berghammer, S. Börm, and M. Winter. Algorithmic counting of zero-dimensional finite topological spaces with respect to the covering dimension. Appl. Math. Comput., 389:125523, 2021. · Zbl 1508.54015 |
| [6] | G. Brinkmann and R. Deklerck. Generation of union-closed sets and moore families. Journal of Integer Sequences, 21(1):18.1.7, 2018. URL: https://cs.uwaterloo.ca/journals/JIS/VOL21/ Brinkmann/brink6.html. · Zbl 1384.05015 |
| [7] | G. Birkhoff. Lattice Theory. Amer. Math. Soc., 3rd edition, 1967. · Zbl 0505.06001 |
| [8] | C. Baier and J-P. Katoen. Principles of Model Checking. MIT Press, 2008. · Zbl 1179.68076 |
| [9] | G. Bordalo and B. Monjardet. Reducible classes of finite lattices. Order, 13(4):379-390, 1996. · Zbl 0891.06001 |
| [10] | H. Bodlaender. Dynamic programming on graphs with bounded treewidth. In T. Lepistö and A. Salomaa, editors, Automata, Languages and Programming, 15th International Colloquium, ICALP88, Tampere, Finland, July 11-15, 1988, Proceedings, volume 317 of Lecture Notes in Computer Science, pages 105-118. Springer, 1988. doi:10.1007/3-540-19488-6_110. · Zbl 0649.68039 · doi:10.1007/3-540-19488-6_110 |
| [11] | S. Bonzio, M. Pra Baldi, and D. Valota. Counting finite linearly ordered involutive bisemilattices. In J. Desharnais, W. Guttmann, and S. Joosten, editors, Relational and Algebraic Methods in Computer Science -17th International Conference, RAMiCS 2018, Groningen, The Netherlands, October 29 -November 1, 2018, Proceedings, volume 11194 of Lecture Notes in Computer Science, pages 166-183. Springer, 2018. · Zbl 1522.06003 |
| [12] | A. Conte, P. Crescenzi, A. Marino, and G. Punzi. Enumeration of s-d separators in dags with application to reliability analysis in temporal graphs. In J. Esparza and D. Král’, editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 25:1-25:14. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.MFCS.2020.25. · Zbl 07559396 · doi:10.4230/LIPIcs.MFCS.2020.25 |
| [13] | P. Colomb, A. Irlande, and O. Raynaud. Counting of moore families for n=7. In L. Kwuida and B. Sertkaya, editors, Formal Concept Analysis, 8th International Conference, ICFCA 2010, Agadir, Morocco, March 15-18, 2010. Proceedings, volume 5986 of Lecture Notes in Computer Science, pages 72-87. Springer, 2010. · Zbl 1274.05013 |
| [14] | N. Caspard and B. Monjardet. The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey. Discrete Applied Mathematics, 127(2):241-269, 2003. · Zbl 1026.06008 |
| [15] | J. Demetrovics, G. Hencsey, L. Libkin, and I. B. Muchnik. On the interaction between closure oper-ations and choice functions with applications to relational database. Acta Cybern., 10(3):129-139, 1992. URL: https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3401. · Zbl 0787.68032 |
| [16] | B. A. Davey and H. A. Priestley. Introduction to Lattices and Order, Second Edition. Cambridge University Press, 2002. · Zbl 1002.06001 |
| [17] | EBJ + 14] S. Elloumi, B. Boulifa, A. Jaoua, M. Saleh, J. Al Otaibi, and M. F. Frias. Inference engine based on closure and join operators over truth table binary relations. J. Log. Algebraic Methods Program., 83(2):180-193, 2014. · Zbl 1371.68268 |
| [18] | U. Fahrenberg, C. Johansen, G. Struth, and R.B. Thapa. Generating posets beyond N. In U. Fahrenberg, P. Jipsen, and M. Winter, editors, Relational and Algebraic Methods in Computer Science -18th International Conference, RAMiCS 2020, Palaiseau, France, April 8-11, 2020, Proceedings [postponed], volume 12062 of Lecture Notes in Computer Science, pages 82-99. |
| [19] | Springer, 2020. doi:10.1007/978-3-030-43520-2_6. · Zbl 07578336 · doi:10.1007/978-3-030-43520-2_6 |
| [20] | R. Glück. Algebraic investigation of connected components. In P. Höfner, D. Pous, and G. Struth, editors, Relational and Algebraic Methods in Computer Science -16th International Conference, RAMiCS 2017, Lyon, France, May 15-18, 2017, Proceedings, volume 10226 of Lecture Notes in Computer Science, pages 109-126, 2017. · Zbl 1486.68100 |
| [21] | R. Glück. Isolated sublattices and their application to counting closure operators. In U. Fahrenberg, M. Gehrke, L. Santocanale, and M. Winter, editors, Relational and Algebraic Methods in Computer Science -19th International Conference, RAMiCS 2021, Marseille, France, November 2-5, 2021, Vol. 20:3 ISOLATED SUBORDERS AND COUNTING CLOSURE OPERATORS 11:21 · Zbl 07906373 |
| [22] | Proceedings, volume 13027 of Lecture Notes in Computer Science, pages 192-208. Springer, 2021. doi:10.1007/978-3-030-88701-8_12. · Zbl 07670519 · doi:10.1007/978-3-030-88701-8_12 |
| [23] | R. Glück, B. Möller, and M. Sintzoff. Model refinement using bisimulation quotients. In M. Johnson and D. Pavlovic, editors, Algebraic Methodology and Software Technology -13th International Conference, AMAST 2010, Lac-Beauport, QC, Canada, June 23-25, 2010. · Zbl 1308.68040 |
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.
