11 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…
Half-space separation in monophonic convexity
Mohammed Elaroussi, Lhouari Nourine, Simon Vilmin
We study half-space separation in the convexity of chordless paths of a graph, i.e., monophonic convexity. In this problem, one is given a graph and two (disjoint) subsets of verti…
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…
Complexity of conjunctive regular path query homomorphisms
Laurent Beaudou, Florent Foucaud, Florent R. Madelaine +2
A graph database is a digraph whose arcs are labeled with symbols from a fixed alphabet. A regular graph pattern (RGP) is a digraph whose edges are labeled with regular expressions…
Enumerating maximal consistent closed sets in closure systems
Lhouari Nourine, Simon Vilmin
Given an implicational base, a well-known representation for a closure system, an inconsistency binary relation over a finite set, we are interested in the problem of enumerating a…
Hierarchical Decompositions of dihypergraphs
Lhouari Nourine, Simon Vilmin
In this paper we are interested in decomposing a dihypergraph into simpler dihypergraphs, that can be handled more efficiently. We study the proper…