×

Indiscernibility structures induced from function sets: graph and digraph case. (English) Zbl 1481.06030

Summary: A very general structure in mathematics is a function system, that is a structure \(\mathcal{J} = \langle U_\mathcal{J}, \Omega_\mathcal{J}, \Lambda_\mathcal{J} \rangle \), where \(U_\mathcal{J}\) is a finite universe set and \(\boldsymbol{\Omega}_\mathcal{J}\) is a finite set of functions \(a_i: U \rightarrow \Lambda_\mathcal{J} \). In this paper we use a function system to develop a mathematical theory of the indiscernibility. More in detail, we first use a natural equivalence relation induced by any function subset \(A \subseteq \boldsymbol{\Omega}_\mathcal{J}\) to introduce a complete lattice of set partitions of \(U_\mathcal{J} \). We prove several properties of this order structure and we develop two specific cases of study concerning directed and undirected graphs. Next, for finite function systems we introduce two approximation measures that have a deep similarity with the Lebesgue measure and with the conditional probability. Also in this case we provide two specific cases of study on directed and undirected graphs.

MSC:

06D72 Fuzzy lattices (soft algebras) and related topics
06A06 Partial orders, general
05C20 Directed graphs (digraphs), tournaments
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrews, G. E., Euler’s “De Partitio numerorum’’, Bull. Amer. Math. Soc., 44, 4, 561-573 (2007) · Zbl 1172.11031 · doi:10.1090/S0273-0979-07-01180-9
[2] Apollonio, N.; Caramia, M.; Franciosa, P. G., On the Galois lattice of bipartite distance hereditary graphs, Discrete Applied Mathematics, 190, 13-23 (2015) · Zbl 1316.05033 · doi:10.1016/j.dam.2015.03.014
[3] Apollonio, N.; Simeone, B., Improved Approximation of Maximum Vertex Coverage Problem on Bipartite Graphs, Siam Journal Discrete Mathematics, 28, 3, 1137-1151 (2014) · Zbl 1310.90095 · doi:10.1137/130931059
[4] Apollonio, N.; Simeone, B., The maximum vertex coverage problem on bipartite graphs, Discrete Applied Mathematics, 165, 37-48 (2014) · Zbl 1288.05201 · doi:10.1016/j.dam.2013.05.015
[5] Apollonio, N.; Caramia, M., Recognizing Helly Edge Path Tree Graphs and their Clique Graphs, Discrete Applied Mathematics, 159, 1166-1175 (2011) · Zbl 1223.05293 · doi:10.1016/j.dam.2011.02.008
[6] Bak, P.; Tang, C.; Wiesenfeld, K., Self organized criticality, Phys, Rev. A., 38, 364-374 (1988) · Zbl 1230.37103 · doi:10.1103/PhysRevA.38.364
[7] Bang-Jensen, J., Gutin, G., Digraphs. Theory, algorithms and applications. Second edition. Springer Monographs in Mathematics. Springer-Verlag London, Ltd., London, 2009. xxii+795 pp. · Zbl 1170.05002
[8] Barret, C. L.; Reidys, C. M., Elements of a theory of computer simulation. I. Sequential CA over random graphs, Appllied Mathematics and Computation, 98, 2-3, 241-259 (1999) · Zbl 0927.68114 · doi:10.1016/S0096-3003(97)10166-7
[9] Barret, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of computer simulation. II. Sequential dynamical systems, Appllied Mathematics and Computation, 107, 2-3, 121-136 (2000) · Zbl 1049.68149 · doi:10.1016/S0096-3003(98)10114-5
[10] Barret, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of computer simulation. III. Equivalence of SDS, Appllied Mathematics and Computation, 122, 3, 325-340 (2001) · Zbl 1050.68161 · doi:10.1016/S0096-3003(00)00042-4
[11] Barret, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of computer simulation. IV. Sequential dynamical systems: fixed points, invertibility and equivalence, Appllied Mathematics and Computation, 134, 1, 153-171 (2003) · Zbl 1028.37010 · doi:10.1016/S0096-3003(01)00277-6
[12] Berge, C., Hypergraphs: Combinatorics of Finite Sets (1984), Elsevier: Elsevier, Amsterdam
[13] Birkhoff, G., Lattice Theory, American Mathematical Society, Providence, Rhode Island, Third Edition, 1967. · Zbl 0153.02501
[14] Bisi, C.; Chiaselotti, G., A class of lattices and boolean functions related to the Manickam-Miklös-Singhi conjecture, Advances in Geometry, 13, 1, 1-27 (2013) · Zbl 1259.05178 · doi:10.1515/advgeom-2012-0027
[15] Bisi, C.; Chiaselotti, G.; Marino, G.; Oliverio, P. A., A natural extension of the Young partition lattice, Advances in Geometry, 15, 3, 263-280 (2015) · Zbl 1317.05018 · doi:10.1515/advgeom-2015-0017
[16] Bisi, C.; Chiaselotti, G.; Gentile, T.; Oliverio, P. A., Dominance Order on Signed Partitions, Advances in Geometry, 17, 1, 5-29 (2017) · Zbl 1383.05020 · doi:10.1515/advgeom-2016-0033
[17] Bisi, C.; Chiaselotti, G.; Ciucci, D.; Gentile, T.; Infusino, F., Micro and Macro Models of Granular Computing induced by the Indiscernibility Relation, Information Sciences, 388-389, 247-273 (2017) · doi:10.1016/j.ins.2017.01.023
[18] Bonacini, P.; Gionfriddo, M.; Marino, L., Nesting House-designs, Applied Mathematical Sciences, 9, 126, 6273-6282 (2015) · doi:10.12988/ams.2015.55397
[19] Bonacini, P.; Gionfriddo, M.; Marino, L., Nesting House-designs, Discrete Mathematcis, 339, 4, 1291-1299 (2016) · Zbl 1329.05241 · doi:10.1016/j.disc.2015.11.014
[20] Cattaneo, G.; Chiaselotti, G.; Gentile, T.; Oliverio, P. A., The lattice structure of equally extended signed partitions. A generalization of the Brylawski approach to integer partitions with two possible models: ice piles and semiconductors, Fundamenta Informaticae, 141, 1-36 (2015) · Zbl 1344.37015 · doi:10.3233/FI-2015-1261
[21] Cattaneo, G.; Chiaselotti, G.; Ciucci, D.; Gentile, T., On the connection of Hypergraph Theory with Formal Concept Analysis and Rough Set Theory, Information Sciences, 330, 342-357 (2016) · Zbl 1390.68618 · doi:10.1016/j.ins.2015.09.054
[22] Cattaneo, G.; Chiaselotti, G.; Oliverio, P. A.; Stumbo, F., A New Discrete Dynamical System of Signed Integer Partitions, European Journal of Combinatorics, 55, 119-143 (2016) · Zbl 1333.05026 · doi:10.1016/j.ejc.2016.02.003
[23] Chen, G., Zhong, N., Yao, Y., A Hypergraph Model of Granular Computing, The 2008 IEEE, Int. Conf. Gran. Comput., GrC2008, pp. 26-28.
[24] Chen, J.; Li, J., An application of rough sets to graph theory, Information Sciences, 201, 114-127 (2012) · Zbl 1251.05165 · doi:10.1016/j.ins.2012.03.009
[25] Chiaselotti, G.; Gentile, T.; Oliverio, P. A., Parallel and sequential dynamics of two discrete models of signed integer partitions, Applied Mathematics and Computation, 232, 1249-1261 (2014) · Zbl 1410.37015 · doi:10.1016/j.amc.2014.01.118
[26] Chiaselotti, G.; Keith, W.; Oliverio, P. A., Two Self-Dual Lattices of Signed Integer Partitions, Applied Mathematics and Information Sciences, 8, 3191-3199 (2014) · doi:10.12785/amis/080661
[27] Chiaselotti, G., Ciucci, D., Gentile, T., Simple Undirected Graphs as Formal Contexts. ICFCA 2015, Lecture Notes in Computer Science, LNAI 9113, pp. 287-302, Springer 2015. · Zbl 1312.68184
[28] Chiaselotti, G., Ciucci, D., Gentile, T., Simple Graphs in Granular Computing. Information Sciences, Volumes 340-341, 1 May 2016, 279-304. · Zbl 1395.68260
[29] Chiaselotti, G., Ciucci, D., Gentile, T., Infusino, F., Rough Set Theory Applied to Simple Undirected Graphs. Proc. RSKT 2015, Lecture Notes in Computer Science, Vol. 9436, pp. 423-434, Springer 2015. · Zbl 1444.68219
[30] Chiaselotti, G., Ciucci, D., Gentile, T., Infusino, F., Preclusivity and Simple Graphs. Proc. RSFDGrC 2015, Lecture Notes in Computer Science, Vol. 9437, 127-137, Springer 2015. · Zbl 1444.68199
[31] Chiaselotti, G., Ciucci, D., Gentile, T., Infusino, F., Preclusivity and Simple Graphs: the n-cycle and n-path Cases. Proc. RSFDGrC 2015, Lecture Notes in Computer Science, Vol. 9437, 138-148, Springer 2015. · Zbl 1444.68200
[32] Chiaselotti, G.; Gentile, T., Intersection Properties of Maximal Directed Cuts in Digraphs, Discrete Mathematics, 340, 3171-3175 (2017) · Zbl 1347.05083 · doi:10.1016/j.disc.2016.07.003
[33] Chiaselotti, G.; Gentile, T.; Infusino, F., P.A.: Oliverio, Rough Sets for n-Cycles and n-Paths, Applied Mathematics and Information Sciences, 10, 1, 117-124 (2016) · doi:10.18576/amis/100111
[34] Chiaselotti, G.; Ciucci, D.; Gentile, T.; Infusino, F., The Granular Partition Lattice of an Information Table, Information Sciences, 373, 57-78 (2016) · Zbl 1429.68270 · doi:10.1016/j.ins.2016.08.037
[35] Chiaselotti, G.; Gentile, T.; Infusino, F.; Oliverio, P. A.; Chiaselotti, G.; Gentile, T.; Infusino, F.; Oliverio, P. A., The Adjacency Matrix of a Graph as a Data Table, A Geometric Perspective. Annali di Matematica Pura e Applicata, 196, 3, 1073-1112 (2017) · Zbl 1366.05029 · doi:10.1007/s10231-016-0608-1
[36] Chiaselotti, G.; Ciucci, D.; Gentile, T.; Infusino, F., Generalizations of Rough Set Tools inspired by Graph Theory, Fundamenta Informaticae, 148, 207-227 (2016) · Zbl 1388.03045 · doi:10.3233/FI-2016-1431
[37] Chiaselotti, G.; Ciucci, D.; Gentile, T.; Infusino, F., Rough Set Theory and Digraphs, Fundamenta Informaticae, 153, 291-325 (2017) · Zbl 1400.05193 · doi:10.3233/FI-2017-1542
[38] Chiaselotti, G.; Gentile, T.; Infusino, F., Knowledge Pairing Systems in Granular Computing, Knowledge Based Systems, 124, 144-163 (2017) · doi:10.1016/j.knosys.2017.03.008
[39] Chiaselotti, G.; Gentile, T.; Infusino, F., Dependency Structures for Decision Tables, International Journal of Approximate Reasoning, 88, 333-370 (2017) · Zbl 1418.68187 · doi:10.1016/j.ijar.2017.06.007
[40] Chiaselotti, G., Gentile, T., Infusino, F., Pairings and Related Symmetry Notions, Annali dell’Universitá di Ferrara Jan. 2018, doi:10.1007/s11565-018-0297-3. · Zbl 1436.08001
[41] Ciucci, D. E., Classification of Dynamics in Rough Sets, RSCTC 2010, Lecture Notes in Computer Science, vol. 6086, pp. 257-266, SpringerVerlag 2010.
[42] Ciucci, D. E., Temporal Dynamics in finite function systems, Fundamenta informaticae, 115, 1, 57-74 (2012) · Zbl 1237.68212
[43] Diestel, R., Graph Theory (4th edition), Graduate Text in Mathematics, Springer 2010. · Zbl 1204.05001
[44] Eiter, T.; Gottlob, G., Identifying the Minimal Transversals of a Hypergraph and Related Problems, Siam Journal on Computing, 24, 1278-1304 (1995) · Zbl 0842.05070 · doi:10.1137/S0097539793250299
[45] Elbassioni, K., On the complexity of monotone dualization and generating minimal hypergraph transversals, Discrete Applied Mathematics, 32, 2, 171-187 (2008)
[46] Fagin, R., Degrees of Acyclicity for Hypergraphs and Relational Database Schemes, Journal of the Association for Computing Machinery, 30, 3, 514-550 (1983) · Zbl 0624.68088 · doi:10.1145/2402.322390
[47] Ganter, B.; Wille, R., Formal Concept Analysis. Mathematical Foundations (1999), Springer-Verlag · Zbl 0909.06001
[48] Gionfriddo, M.; Guardo, E.; Milazzo, L., Extending bicolorings for Steiner triple systems, Applicable Analysis and Discrete Mathematics, 225-234 (2013) · Zbl 1408.05096 · doi:10.2298/AADM130827019G
[49] Gottlob, G.; Schrefl, M.; Stumptner, M., Selective inheritance of attribute values in relational databases, Discrete Applied Mathematics, 40, 187-216 (1992) · Zbl 0767.68031 · doi:10.1016/0166-218X(92)90029-A
[50] Guo, L.; Huang, F.; Lia, Q.; Zhang, G., Power contexts and their concept lattices, Discrete Mathematics, 311, 2049-2063 (2011) · Zbl 1233.68207 · doi:10.1016/j.disc.2011.04.033
[51] Gyárfás, A.; Lehel, J.; Hypergraph families with bounded edge cover or transversal number; Combinatorica, Vol. 3, Issue 3-4, pp. 351-358, 1983. · Zbl 0534.05052
[52] Hagen, M., Lower bounds for three algorithms for transversal hypergraph generation, Discrete Applied Mathematics, 157, 1460-1469 (2009) · Zbl 1177.05116 · doi:10.1016/j.dam.2008.10.004
[53] Huang, A.; Zhao, H.; Zhu, W., Nullity-based matroid of rough sets and its application to function reduction, Information Sciences, 263, 153-165 (2014) · Zbl 1328.68228 · doi:10.1016/j.ins.2013.11.014
[54] Lee, T. T., An Information-Theoretic Analysis of Relational Databases part I: Data Dependencies and Metric, IEEE Transactions on Software Engineering SE-13, 1049-1061 (1987) · doi:10.1109/TSE.1987.232847
[55] Nambiar, K. K.; Radhakrishnan, T.; Tikekar, V. G., Representation of Functional Dependencies in Relational Databases Using Linear Graphs, Theoretical Computer Science, 24, 143-159 (1983) · Zbl 0542.68083 · doi:10.1016/0304-3975(83)90046-4
[56] Pawlak, Z.
[57] Pedrycz, W., Granular Computing: An Emerging Paradigm (2001), Springer-Verlag: Springer-Verlag, Berlin · Zbl 0966.00017
[58] Pedrycz, W.; Skowron, A.; Kreinovich, V., Handbook of Granular Computing (2008), Wiley · doi:10.1002/9780470724163
[59] Poonen, B., Union-Closed Families, Journal of Combinatorial Theory Ser. A, 59, 253-268 (1992) · Zbl 0758.05096 · doi:10.1016/0097-3165(92)90068-6
[60] Reidys, C. M., Combinatorics of sequential dynamical systems, Discrete Mathematics, 308, 4, 514-528 (2008) · Zbl 1128.37006 · doi:10.1016/j.disc.2007.03.033
[61] Sanahuja, S. M., New rough approximations for n-cycles and n-paths, Applied Mathematics and Computation, 276, 96-108 (2016) · Zbl 1410.68355 · doi:10.1016/j.amc.2015.11.052
[62] Simovici, D. A.; Djeraba, C., Mathematical Tools for Data Mining (2014), Springer-Verlag: Springer-Verlag, London · Zbl 1303.68006
[63] Stell, J. G., Granulation for Graphs, Sp. Inf. Th., Lecture Notes in Computer Science, Volume 1661, 1999, 417-432.
[64] Stell, J. G., Relational Granularity for Hypergraphs, RSCTC, Lecture Notes in Computer Science, 6086, 267-276 (2010) · doi:10.1007/978-3-642-13529-3_29
[65] Stell, J. G., Relational on Hypergraphs, RAMiCS, Lecture Notes in Computer Science, 7560, 326-341 (2012) · Zbl 1330.03093 · doi:10.1007/978-3-642-33314-9_22
[66] Stell, J. G., Formal concept analysis over graphs and hypergraphs, GKR2013, Lecture Notes in Computer Science, 8323, 165-179 (2014) · doi:10.1007/978-3-319-04534-4_11
[67] Tanga, J.; Shea, K.; Min, F.; Zhu, W., A matroidal approach to rough set theory, Theoretical Computer Science, 471, 1-11 (32013) · Zbl 1258.05022 · doi:10.1016/j.tcs.2012.10.060
[68] Wang, S.; Zhu, Q.; Zhu, W.; Min, F., Rough Set Characterization for 2-circuit Matroid, Fundamenta Informaticae, 129, 4, 377-393 (2014) · Zbl 1285.68186
[69] Wang, S.; Zhu, Q.; Zhu, W.; Min, F., Graph and matrix approaches to rough sets through matroids, Information Sciences, 288, 1-11 (2014) · Zbl 1355.68265 · doi:10.1016/j.ins.2014.07.023
[70] Wille, R., Subdirect product construction of concept lattices, Discrete Mathematics, 63, 2-3, 305-313 (1987) · Zbl 0621.06004 · doi:10.1016/0012-365X(87)90019-7
[71] Wille, R., Concept lattices and conceptual knowledge systems, Computers and Mathematics with Applications, 23, 6-9, 493-515 (1992) · Zbl 0766.68129 · doi:10.1016/0898-1221(92)90120-7
[72] Wille, R., The Basic Theorem of triadic concept analysis, Order, Volume 12, Issues 2, 1995, 149-158. · Zbl 0835.06005
[73] Yannakakis, M.; Papadimitriou, C. H., Algebraic Dependencies, Journal of Computer and System Sciences, 25, 2-41 (1982) · Zbl 0493.68095 · doi:10.1016/0022-0000(82)90008-3
[74] Yao, Y. Y., Information granulation and rough set approximation, International Journal of Intelligent Systems, 16, 1, 87-104 (2001) · Zbl 0969.68079 · doi:10.1002/1098-111X(200101)16:1<87::AID-INT7>3.0.CO;2-S
[75] Yao, Y. Y., Zhong, N., Granular Computing using finite function systems, in Data Mining, Rough Sets and Granular Computing, Physica-Verlag, 2002, pp. 102-124. · Zbl 1017.68053
[76] Yao, Y., A Partition Model of Granular Computing, in: Transactions on Rough Sets I, Lecture Notes in Computer Science, vol. 3100, Springer-Verlag, 2004, pp. 232-253. · Zbl 1104.68776
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.