Wyniki wyszukiwania - BazTech

1

A New Description of Transversal Matroids Through Rough Set Approach

Wang Zhaohao

Fundamenta Informaticae

|

2021

|

Vol. 179, nr 4

399-416

EN

Matroid theory is a useful tool for the combinatorial optimization issue in data mining, machine learning and knowledge discovery. Recently, combining matroid theory with rough sets is becoming interesting. In this paper, rough set approaches are used to investigate an important class of matroids, transversal matroids. We first extend the concept of upper approximation number functions in rough set theory and propose the notion of generalized upper approximation number functions on a set system. By means of the new notion, we give some necessary and sufficient conditions for a subset to be a partial transversal of a set system. Furthermore, we obtain a new description of a transversal matroid by the generalized upper approximation number function. We show that a transversal matroid can be induced by the generalized upper approximation number function which can be decomposed into the sum of some elementary generalized upper approximation number functions. Conversely, we also prove that a generalized upper approximation number function can induce a transversal matroid. Finally, we apply the generalized upper approximation number function to study the relationship among transversal matroids.

2

A new ω-stable plane

Paolini Gianluca

Reports on Mathematical Logic

|

2020

|

Vol. 55

87--111

EN

We use a variation on Mason’s α-function as a pre-dimension function to construct a not one-based ω-stable plane P (i.e. a simple rank 3 matroid) which does not admit an algebraic representation (in the sense of matroid theory) over any field. Furthermore, we characterize forking in T h(P), we prove that algebraic closure and intrinsic closure coincide in T h(P), and we show that T h(P) fails weak elimination of imaginaries, and has Morley rank ω.

3

Rough Set Characterization for 2-circuit Matroid

Wang S., Zhu Q., Zhu W., Min F.

Fundamenta Informaticae

|

2014

|

Vol. 129, nr 4

377--393

EN

Rough sets are efficient to extract rules from information systems. Matroids generalize the linear independency in vector spaces and the cycle in graphs. Specifically, matroids provide well-established platforms for greedy algorithms, while most existing algorithms for many rough set problems including attribute reduction are greedy ones. Therefore, the combination between rough sets and matroids may bring new efficient solutions to those important and difficult problems. In this paper, 2-circuit matroids, abstracted from matroidal characteristics of rough sets, are studied and axiomatized. A matroid is induced by an equivalence relation, and its characteristics including the independent set and duality are represented with rough sets. Based on these rough set representations, this special type of matroid is defined as 2-circuit matroids. Conversely, an equivalence relation is induced by a matroid, and its relationship with the above induction is further investigated. Finally, a number of axioms of the 2-circuit matroid are obtained through rough sets. These interesting and diverse axioms demonstrate the potential for the connection between rough sets and matroids.

4

A remark on hierarchical threshold secret sharing

Kawa R., Kula M.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2012

|

Vol. 12, no. 3

55--64

EN

The main results of this paper are theorems which provide a solution to the open problem posed by Tassa [1]. He considers a specific family Γv of hierarchical threshold access structures and shows that two extreme members Γ∧ and Γv of Γv are realized by secret sharing schemes which are ideal and perfect. The question posed by Tassa is whether the other members of Γv can be realized by ideal and perfect schemes as well. We show that the answer in general is negative. A precise definition of secret sharing scheme introduced by Brickell and Davenport in [2] combined with a connection between schemes and matroids are crucial tools used in this paper. Brickell and Davenport describe secret sharing scheme as a matrix M with n+1 columns, where n denotes the number of participants, and define ideality and perfectness as properties of the matrix M. The auxiliary theorems presented in this paper are interesting not only because of providing the solution of the problem. For example, they provide an upper bound on the number of rows of M if the scheme is perfect and ideal.

5

Analysis of Markov Boundary Induction in Bayesian Networks: A New View From Matroid Theory

Feng D., Chen F., Xu W.

Fundamenta Informaticae

|

2011

|

Vol. 107, nr 4

415-434

EN

Learning Markov boundaries from data without having to learn a Bayesian network first can be viewed as a feature subset selection problem and has received much attention due to its significance in the wide applications of AI techniques. Popular constraint based methods suffer from high computational complexity and are usually unstable in spaces of high dimensionality. We propose a new perspective from matroid theory towards the discovery of Markov boundaries of random variable in the domain, and develop a learning algorithm which guarantees to recover the true Markov boundaries by a greedy learning algorithm. Then we use the precision matrix of the original distribution as a measure of independence to make our algorithm feasible in large scale problems, which is essentially an approximation of the probabilistic relations with Gaussians and can find possible variables in Markov boundaries with low computational complexity. Experimental results on standard Bayesian networks show that our analysis and approximation can efficiently and accurately identify Markov boundaries in complex networks from data.

6

Pojęcia niezależności w ujęciu algebraicznym - ogólny schemat Marczewskiego

Głazek K.

Roczniki Polskiego Towarzystwa Matematycznego. Seria 2: Wiadomości Matematyczne

|

1998

|

[Z] 34

31-48