6 papers
Characterizing the optimum bases of a convex geometry using quasi-closed hypergraphs
Anthony Meunier, Lhouari Nourine, Simon Vilmin
Optimizing an implicational base of a closure system consists in turning this implicational base into an equivalent one with premises and conclusions as small as possible. This tas…
Generating minimal redundant and maximal irredundant sets in incidence graphs
Emanuel Castelo, Jérémie Chalopin, Oscar Defrain +1
It has been proved by Boros and Makino that there is no output-polynomial-time algorithm enumerating the minimal redundant sets or the maximal irredundant sets of a hypergraph, unl…
Translating between the representations of an acyclic convex geometry of bounded degree
Oscar Defrain, Arthur Ohana, Simon Vilmin
We consider the problem of translating between irreducible closed sets and implicational bases in closure systems. To date, the complexity status of this problem is widely open, an…
Computing the -base and -relation in finite closure systems
Kira Adaricheva, Lhouari Nourine, Simon Vilmin
Implicational bases (IBs) are a common representation of finite closure systems and lattices, along with meet-irreducible elements. They appear in a wide variety of fields ranging…
On the -base of Finite Lattices: Semidistributive, Modular, and Geometric Lattices
Kira Adaricheva, Simon Vilmin
Implicational bases are a well-known representation of closure spaces and their closure lattices. This representation is not unique, though, and a closure space usually admits mult…
On the enumeration of signatures of XOR-CNF's
Nadia Creignou, Oscar Defrain, Frédéric Olive +1
Given a CNF formula with clauses over a set of variables , a truth assignment generates a binary sequence $Ï_Ï(\mathbf{a})…