Mathematics
Permanent URI for this community
Browse
Browsing Mathematics by Author "Adaricheva, Kira"
Now showing 1 - 20 of 21
Results Per Page
Sort Options
Item Open Access A class of infinite convex geometries(2015) Adaricheva, Kira; Nation, J.B.Various characterizations of finite convex geometries are well known. This note provides similar characterizations for possibly infinite convex geometries whose lattice of closed sets is strongly coatomic and lower continuous. Some classes of examples of such convex geometries are givenItem Open Access Algebraic convex geometries revisited(2014) Adaricheva, KiraRepresentation of convex geometry as an appropriate join of compatible orderings of the base set can be achieved, when closure operator of convex geometry is algebraic, or finitary. This bears to the finite case proved by P. Edelman and R. Jamison to the greater extent than was thought earlierItem Open Access Discovery of the D-basis in binary tables based on hypergraph dualization(2016) Adaricheva, Kira; Nation, J.B.Discovery of (strong) association rules, or implications, is an important task in data management, and it nds application in arti cial intelligence, data mining and the semantic web. We introduce a novel approach for the discovery of a speci c set of implications, called the D-basis, that provides a representation for a reduced binary table, based on the structure of its Galois lattice. At the core of the method are the D-relation de ned in the lattice theory framework, and the hypergraph dualization algorithm that allows us to e ectively produce the set of transversals for a given Sperner hypergraph. The latter algorithm, rst developed by specialists from Rutgers Center for Operations Research, has already found numerous applications in solving optimization problems in data base theory, arti cial intelligence and game theory. One application of the method is for analysis of gene expression data related to a particular phenotypic variable, and some initial testing is done for the data provided by the University of Hawaii Cancer CenterItem Open Access Efficient bases of finite closure systems(2014-05-13) Adaricheva, KiraItem Open Access Embedding finite lattices into finite biatomic lattices(2005) Adaricheva, Kira; Wehrung, FreidrichFor a class C of finite lattices, the question arises whether any lattice in C can be embedded into some atomistic, biatomic lattice in C. We provide answers to the question above for C being, respectively, — The class of all finite lattices; — The class of all finite lower bounded lattices (solved by the first author’s earlier work). — The class of all finite join-semidistributive lattices (this problem was, until now, open). We solve the latter problem by finding a quasi-identity valid in all finite, atomistic, biatomic, join-semidistributive lattices but not in all finite join-semidistributive latticesItem Open Access Increasing the role of the D-basis in applications(2015-06-06) Adaricheva, KiraItem Open Access Join-semidistributive lattices of relatively convex sets(2004) Adaricheva, KiraWe give two sufficient conditions for the lattice Co(Rn,X) of rel- atively convex sets of Rn to be join-semidistributive, where X is a finite union of segments. We also prove that every finite lower bounded lattice can be embedded into Co(Rn,X), for a suitable finite subset X of RnItem Open Access Lattices of quasi-equational theories as congruence lattices of semilattices with operators, part I(2012) Adaricheva, Kira; Nation, J. B.We show that for every quasivariety K of structures (where both functions and relations are allowed) there is a semilattice S with operators such that the lattice of quasi-equational theories of K (the dual of the lattice of sub-quasivarieties of K) is isomorphic to Con(S;+; 0; F). As a consequence, new restrictions on the natural quasi-interior operator on lattices of quasi-equational theories are found.Item Open Access Lattices of quasi-equational theories as congruence lattices of semilattices with operators, part II(2012) Adaricheva, Kira; Nation, J.B.Part I proved that for every quasivariety K of structures (which may have both operations and relations) there is a semilattice S with operators such that the lattice of quasi-equational theories of K (the dual of the lattice of sub-quasivarieties of K) is isomorphic to Con(S;+; 0; F). It is known that if S is a join semilattice with 0 (and no operators), then there is a quasivariety Q such that the lattice of theories of Q is isomorphic to Con(S;+; 0). We prove that if S is a semilattice having both 0 and 1 with a group G of operators acting on S, and each operator in G xes both 0 and 1, then there is a quasivariety W such that the lattice of theories of W is isomorphic to Con(S;+; 0; G).Item Open Access Measuring implications of the D-basis in biomedical applications(2015-06-26) Adaricheva, KiraItem Open Access Notes on the description of join-distributive lattices by permutations(2012) Adaricheva, Kira; Cz´edli, G´aborLet L be a join-distributive lattice with length n and width (Ji L) k. There are two ways to describe L by k − 1 permutations acting on an n-element set: a combinatorial way given by P.H. Edelman and R. E. Jamison in 1985 and a recent lattice theoretical way of the second author. We prove that these two approaches are equivalent. Also, we characterize join-distributive lattices by trajectoriesItem Open Access On complex algebras of subalgebras(2006) Adaricheva, Kira; Pilitowska, Agata; Stanovsky, DavidLet V be a variety of algebras. We establish a condition (so called generalized entropic property), equivalent to the fact that for every algebra A 2 V, the set of all subalgebras of A is a subuniverse of the complex algebra of A. We investigate the relationship between the generalized entropic property and the entropic law. Further, provided the generalized entropic property is satisfied in V, we study the identities satisfied by the complex algebras of subalgebras of algebras from VItem Open Access On implicational bases of closure system with unique critical sets(2013) Adaricheva, Kira; Nation, J.B.We show that every optimum basis of a nite closure system, in D. Maier's sense, is also right-side optimum, which is a parameter of a minimum CNF representation of a Horn Boolean function. New parameters for the size of the binary part are also established. We introduce the K-basis of a general closure system, which is a re nement of the canonical basis of V. Duquenne and J.L. Guigues, and discuss a polynomial algorithm to obtain it. We study closure systems with unique critical sets, and some subclasses of these where the K-basis is unique. A further re nement in the form of the E-basis is possible for closure systems without D-cycles. There is a polynomial algorithm to recognize the D-relation from a K-basis. Thus, closure systems without D-cycles can be e ectively recognized. While the E-basis achieves an optimum in one of its parts, the optimization of the others is an NP-complete problemItem Open Access On scattered convex geometries(2015) Adaricheva, Kira; Pouzet, MauriceA convex geometry is a closure space satisfying the anti-exchange axiom. For several types of algebraic convex geometries we describe when the collection of closed sets is order scattered, in terms of obstructions to the semilattice of compact elements. In particular, a semilattice ( ), that does not appear among minimal obstructions to order-scattered algebraic modular lattices, plays a prominent role in convex geometries case. The connection to topological scatteredness is established in convex geometries of relatively convex setsItem Open Access Optimum basis of finite convex geometry(2016) Adaricheva, KiraConvex geometries form a subclass of closure systems with unique criticals, or UC-systems. We show that the F-basis introduced in [6] for UC- systems, becomes optimum in convex geometries, in two essential parts of the basis: right sides (conclusions) of binary implications and left sides (premises) of non-binary ones. The right sides of non-binary implications can also be optimized, when the convex geometry either satis es the Carousel property, or does not have D-cycles. The latter generalizes a result of P.L. Hammer and A. Kogan for acyclic Horn Boolean functions. Convex geometries of order convex subsets in a poset also have tractable optimum basis. The problem of tractability of optimum basis in convex geometries in general remains to be openItem Open Access Ordered direct implication basis of a finite closure system(2012) Adaricheva, Kira; Nation, J.B.; Rand, R.Closure system on a nite set is a unifying concept in logic programming, relational data bases and knowledge systems. It can also be presented in the terms of nite lattices, and the tools of economic description of a nite lattice have long existed in lattice theory. We present this approach by describing the so-called D-basis and introducing the concept of ordered direct basis of an implicational system. A direct basis of a closure operator, or an implicational system, is a set of implications that allows one to compute the closure of an arbitrary set by a single iteration. This property is preserved by the D-basis at the cost of following a prescribed order in which implications will be attended. In particular, using an ordered direct basis allows to optimize the forward chaining procedure in logic programming that uses the Horn fragment of propositional logic. One can extract the D-basis from any direct unit basis in time polynomial in the size s( ), and it takes only linear time of the cardinality of the D-basis to put it into a proper order. We produce examples of closure systems on a 6-element set, for which the canonical basis of Duquenne and Guigues is not ordered directItem Open Access Realization of abstract convex geometries by point configurations. Part I(2007) Adaricheva, Kira; Wild, MarcelThe Edelman-Jamison problem is to characterize those abstract convex geometries that are representable by a set of points in the plane. We show that some natural modification of the Edelman-Jamison problem is equivalent to the well known NP-hard order type problemItem Open Access Representations of Convex Geometries(2015-06) Adaricheva, KiraItem Open Access Representing finite convex geometries by relatively convex sets(2011) Adaricheva, KiraA closure system with the anti-exchange axiom is called a convex geometry. One geometry is called a sub-geometry of the other if its closed sets form a sublattice in the lattice of closed sets of the other. We prove that convex geometries of relatively convex sets in n-dimensional vector space and their nite sub-geometries satisfy the n-Carousel Rule, which is the strengthening of the n-Carath eodory property. We also nd another property, that is similar to the simplex partition property and does not follow from 2-Carusel Rule, which holds in sub-geometries of 2-dimensional geometries of relatively convex sets.Item Open Access Stasheff polytope as a sublattice of permutohedron(2011) Adaricheva, KiraAn assosiahedron Kn, known also as Stasheff polytope, is a multifaceted combinatorial object, which, in particular, can be realized as a convex hull of certain points in Rn, forming (n − 1)-dimensional polytope1. A permutahedron Pn is a polytope of dimension (n−1) in Rn with vertices forming various permutations of n-element set. There exists well-known orderings of vertices of Pn and Kn that make these objects into lattices: the first known as permutation lattices, and the latter as Tamari lattices. We provide a new proof to the statement that the vertices of Kn can be naturally associated with particular vertices of Pn in such a way that the corresponding lattice operations are preserved. In lattices terms, Tamari lattices are sublattices of permutation lattices. The fact was established in 1997 in paper by Bjorner and Wachs, but escaped the attention of lattice theorists. Our approach to the proof is based on presentation of points of an associahedron Kn via so-called bracketing functions. The new fact that we establish is that the embedding preserves the height of elements