tcb@breakable

# Computing the $D$-base and $D$-relation in finite closure systems

Kira Adaricheva  Department of Mathematics, Hofstra University, Hempstead, NY
11549, USA.  Lhouari Nourine  Université Clermont Auvergne, Clermont Auvergne
INP, CNRS, LIMOS, F-63000 Clermont–Ferrand, France.  Simon Vilmin  Aix-
Marseille Université, CNRS, LIS, Marseille, France.

###### Abstract

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 from logic and databases to Knowledge Space
Theory.

Different IBs can represent the same closure system. Therefore, several IBs
have been studied, such as the canonical and canonical direct bases. In this
paper, we investigate the $D$-base, a refinement of the canonical direct base.
It is connected with the $D$-relation, an essential tool in the study of free
lattices. The $D$-base demonstrates desirable algorithmic properties, and
together with the $D$-relation, it conveys essential properties of the
underlying closure system. Hence, computing the $D$-base and the $D$-relation
of a closure system from another representation is crucial to enjoy its
benefits. However, complexity results for this task are lacking.

In this paper, we give algorithms and hardness results for the computation of
the $D$-base and $D$-relation. Specifically, we establish the
$\mathbf{NP}$-completeness of finding the $D$-relation from an arbitrary IB;
we give an output-quasi-polynomial time algorithm to compute the $D$-base from
meet-irreducible elements; and we obtain a polynomial-delay algorithm
computing the $D$-base from an arbitrary IB. These results complete the
picture regarding the complexity of identifying the $D$-base and $D$-relation
of a closure system.

### Keywords:

closure systems, $D$-base, $D$-relation, minimal join covers, algorithmic
enumeration, distributive lattice dualization, solution-graph traversal

##  1 Introduction

A _closure system_ over a finite groundset $X$ is a set system containing $X$
and closed under taking intersections. The sets in a closure system are
_closed sets_ , and when ordered by inclusion they form a _lattice_. Lattices
and closure systems are used in a number of fields of mathematics and computer
science such as algebra [Gra11], databases [MR92], logic [HK95], or Knowledge
Space Theory [DF12] to mention just a few.

Often, a closure system is implicitly given by one of the following two
representations: _meet-irreducible elements_ or _implicational bases_ (IBs).
The family of meet-irreducible elements of a closure system is the unique
minimal subset of closed sets from which the whole system can be rebuilt using
intersections. An implication over groundset $X$ is a statement $A\rightarrow
c$ where $A$ is a subset of $X$ and $c$ and element of $X$. In $A\rightarrow
c$, $A$ is the _premise_ and $c$ the _conclusion_. The implication
$A\rightarrow c$ stands for “if a set includes $A$, it must also contain the
element $c$”. An implicational base (IB) over $X$ is a collection of
implications over $X$. An IB encodes a unique closure system. On the other
hand, a closure system can be represented by several equivalent IBs. IBs are
known as pure Horn CNFs in logic [BČKK09, HK95], covers of functional
dependencies in databases [MR92], association rules in data mining [AMS+96] or
entailments in Knowledge Space Theory [DF12].

This variety of applications brought a rich theory of implications still at
the core of several works, as witnessed by surveys [BDVG18, Wil17] and recent
contributions [BBM23a, BBM23b, Bic22, Bic23, NV23]. Specifically, since two
distinct IBs can represent the same closure system, several IBs have been
studied [ANR13, BM10, GD86, Wil94]. Within this galaxy, the _canonical base_
and the _canonical direct base_ are arguably the two most shining stars. They
are unique, and they reflect two complementary ways of understanding IBs:

  1. (1)

_the canonical base_ [GD86], also known as the _Duquenne-Guigues base_ , puts
emphasis on the premises of implications. Its implications are of the form
$A\rightarrow C$ (rather than $A\rightarrow c$) where $A$ must be _pseudo-
closed_ and $C$ is the _closure_ of $A$, i.e., the set of all elements derived
from $A$. The canonical base has a minimum number of implications, and can be
reached from any other IB in polynomial time [GD86, Day92b].

  2. (2)

_The canonical direct base_ is defined by its conclusions (see the survey
[BM10]). It describes, for each element $c$, the inclusion-wise minimal sets
$A$ such that $A\rightarrow c$ holds in the closure system. Such minimal sets
are the _minimal generators_ of $c$. The canonical direct base then gathers
all implications of the form $A\rightarrow c$ (known in logic as the prime
implicates in Horn CNFs). It enjoys the property of being _direct_ , meaning
that the closure of a set can be computed with a single pass over the
implications. Moreover, the canonical direct base naturally captures the
$\delta$-relation of lattice theory [MC97], where $c\delta a$ means that $a$
belongs to some minimal generator of $c$. This relation and its transitive
closure have been used implicitly in the context of pure Horn CNFs and
implication-graphs for minimization [BČK98] or to recognize and optimize
acyclic Horn functions and some of their generalizations [BČKK09, HK95].

In this paper, we study a subset of the canonical direct base: the $D$-base
[ANR13]. It relies on particular minimal generators called _$D$ -generators_.
A minimal generator $A$ of $c$ is a _$D$ -generator_ of $c$ if its closure
with respect to binary implications—implications of the form $a\rightarrow
c$—is minimal as compared to those of other minimal generators of $c$. The
$D$-generators also appear under the name _minimal pairs_ in the study of
semimodular closure operators [FH81]. The $D$-base then consists in all
implications of the form $A\rightarrow c$ where $A$ is a $D$-generator of $c$,
along with all valid (and non-trivial) binary implications. In general, the
$D$-base is much smaller than the canonical direct base. Yet, it still enjoys
directness as long as its implications are suitably ordered. This makes the
$D$-base appealing for computational purposes. Several application projects
were carried out recently that provide analysis of data by employing $D$-base
[NCMS+21, ABLS23].

Besides, the $D$-base embeds the $D$-relation of a closure system: $cDa$ holds
if $a$ belongs to a $D$-generator of $c$. The $D$-relation has played a major
role in lattice theory since the 1970s [JN75]. It is crucial in the study of
free lattices [FJN95] and for the doubling of convex sets [Day92a]. Also, the
$D$-relation compactly convey structural information of the underlying closure
system. The most striking examples are lower bounded closure systems that are
precisely characterized by an acyclic $D$-relation [FJN95]. Acyclic closure
systems (i.e., acyclic Horn functions) [Ada17, HK95, Wil94] and closure
systems generated by sub-semilattices of semilattices [Ada91] are well-known
examples of lower bounded closure systems.

Despite their importance, the algorithmic solutions for several questions
related to $D$-base and $D$-relation are still lacking. A first question is
about computing the $D$-relation from an IB.

######  Question 1.

Is it possible to compute in polynomial time the $D$-relation of a closure
system given by an IB?

The other two questions are two sides of the same coin for they ask to compute
the $D$-base of a closure system given by either of the two representations
previously mentioned, namely an IB or meet-irreducible elements. Algorithms
for such tasks are _enumeration algorithms_ for they aim at outputting,
without repetitions, all the implications of the $D$-base. However, the
$D$-base may contain a number of implications being exponential in the size of
the input IB or meet-irreducible elements. Hence, we need to express the
complexity of our algorithms in terms of the combined size of their input and
their output. This is _output sensitive complexity_ [JYP88, Str19]. More
precisely, an enumeration algorithm runs in _output-polynomial time_ (resp.
_output-quasi-polynomial time_) if its execution time is polynomially (resp.
quasi-polynomially) bounded by its input and output sizes. A more refined
description of an enumeration algorithm’s complexity can be conducted by
analyzing the regularity with which solutions are output. Specifically, if the
delay between two solutions output and after the last one is polynomial in the
size of the input, the algorithm runs with _polynomial-delay_. Note that if an
algorithm runs with polynomial-delay, it runs in output-polynomial time. We
can now formalize the questions regarding the computation of the $D$-base.

######  Question 2.

Can the $D$-base of a closure system given by its meet-irreducible elements be
computed in output-polynomial time?

######  Question 3.

Can the $D$-base of a closure system given by an IB be computed in output-
polynomial time?

### Contributions.

In this paper, we study the aforementioned questions. Without loss of
generality, our results are stated for _standard_ closure systems (see Section
2). To begin with, we answer Question 1 negatively under different
restrictions related to the acyclicity of $\delta$ or $D$. Our results are
summarized by the next two theorems.

######  Theorem 1 (restate=DACG, label=thm:D-relation-ACG).

The problem of identifying the $D$-relation given an IB is
$\mathbf{NP}$-complete even for acyclic (i.e., $\delta$-acyclic) closure
systems and IBs with premises of size at most $2$.

######  Theorem 2 (restate=DLB, label=thm:D-relation-LB).

The problem of identifying the $D$-relation given an IB is
$\mathbf{NP}$-complete even for lower-bounded (i.e., $D$-acyclic) closure
systems where $D$-paths have size at most $2$ and IBs with premises of size at
most $2$.

For Question 2, we prove that the problem is equivalent to _dualization in
distributive closure systems_. This task is a generalization of the famous
_hypergraph dualization_ problem (see e.g., [EG95, EMG08]), and has been shown
recently to admit an output-quasi-polynomial time algorithm [Elb22]. Our
results can thus be summarized as follows:

######  Theorem 3 (restate=DBDual, label=thm:D-base-dual).

There exists an output-polynomial time finding the $D$-base of a closure
system given by its meet-irreducible elements if and only if there exists an
output-polynomial time solving dualization in distributive closure systems.

######  Theorem 4 (restate=DBMi, label=thm:D-base-Mi).

There is an output-quasi-polynomial time algorithm that computes the $D$-base
of a closure system given its meet-irreducible elements.

Finally, we tackle Question 3 using the well-known _solution graph traversal_
method (see e.g., [Elb14, JYP88]) and results rooted in database theory
[EN16]. Specifically, we prove:

######  Theorem 5 (restate=DBIB, label=thm:D-base-IB).

There is a polynomial-delay algorithm that computes the $D$-base of a closure
system given by an arbitrary IB.

### Related work.

We begin with complexity results regarding the $D$-relation. In [ANR13], the
authors provide sub and supersets of the $D$-relation that can be obtained in
polynomial time from any IB. On the one hand, it is possible to refine any IB
to a subset of the $D$-base, which gives a subset of the $D$-relation. On the
other hand, the transitive closure of the $D$-relation can be recovered from
any IB. Similar results also exist for the $\delta$-relation [BČK98]. The
hardness of computing the $\delta$-relation can be obtained as a corollary of
the $\mathbf{NP}$-completeness of the prime attribute problem in databases
[LO78]. However, since $D\subset\delta$ in general, these results do not
straightforwardly apply to the $D$-relation, especially when the structure of
the closure system is to be studied. Let us mention that when one is given
meet-irreducible elements instead of an IB, both the $D$-relation and the
$\delta$-relation can be computed in polynomial time by means of lattice-
theoretic characterizations [MC97, FJN95]. Still, to our knowledge, none of
these results formally settles the complexity of computing the $D$-relation
from an IB, especially with regard to the structure of the underlying closure
system as we do in this paper.

We move to the tasks of computing the $D$-base from an IB or from meet-
irreducible elements. In [RLAC+15, RLAC+17], the authors use simplification
logic to come up with two algorithms computing the $D$-base from an arbitrary
IB. However, the complexity of these algorithms is not analyzed. As for meet-
irreducible elements as input, [AN17] give an algorithm based on hypergraph
dualization. Yet, their algorithm will produce in general a proper superset of
the $D$-base. Note that hypergraph dualization is a central open problem in
algorithmic enumeration [EG95, EMG08]. To date, the best algorithm for this
task is due to Fredman and Khachiyan [FK96] and runs in output-quasi-
polynomial time. We finally mention the algorithm of Freese et al. [FJN95,
Algorithm 11.12, p. 232] which computes the $D$-base from the whole closure
system (in fact, a meet-join table of the lattice) as input. As there is
usually an exponential gap between a closure and either of its representation,
IB or meet-irreducible elements, we cannot afford using this algorithm in our
context.

We also mention algorithms for finding the related canonical direct base. If
the input representation is meet-irreducible elements, it is well-known that
the problem is equivalent to hypergraph dualization (see e.g., [MR92, Wil17]).
When an IB is given, the algorithm of [LO78] (see also [BBM23a]) listing the
minimal keys of a closure system can be adapted to list the minimal generators
of a single element with polynomial-delay. Besides, the algorithm of [BCH90]
computes the whole canonical direct base with a total time linearly dependent
on the number of implications in the output. These techniques cannot be used
out of the box to find the $D$-base as there may be an exponential gap between
the two IBs. Instead, we adapt the procedure of [EN16] to list the so called
ideal-minimal keys—called $D$-minimal keys in our paper—of a closure system.
Nevertheless, our approach naturally extends results on minimal generators,
all the while taking care of the binary implications playing an important role
in the $D$-base.

### Paper Organization.

In Section 2 we give necessary definitions regarding closure systems and their
representations. We also formally define the problems we study in the paper.
In Section 3 we establish the complexity of computing the $D$-relation.
Section 4 is dedicated to the computation of the $D$-base of a closure system
given by its meet-irreducible elements. We investigate the dual problem of
finding the $D$-base from an IB in Section 5. We conclude the paper with some
remarks for future research in Section 6.

##  2 Preliminaries

All the objects considered in this paper are finite. For notions not defined
here, we redirect the reader to [Gra11]. If $X$ is a set, $\mathbf{2}^{X}$ is
its powerset.

### Closure operators, closure systems.

Let $X$ be a set. A _closure operator_ over $X$ is a map
$\phi\colon\mathbf{2}^{X}\to\mathbf{2}^{X}$ such that, for every $A,B\subseteq
X$:

  1. (1)

$A\subseteq\phi(A)$;

  2. (2)

$A\subseteq B$ implies $\phi(A)\subseteq\phi(B)$; and

  3. (3)

$\phi(\phi(A))=\phi(A)$.

The pair $(X,\phi)$ is a _closure space_. A subset $F$ of $X$ is _closed_ if
$\phi(F)=F$. For brevity, we write $\phi(a)$ instead of $\phi(\\{a\\})$ for
$a\in X$. The family of closed sets of $\phi$ is called $\mathcal{F}$. We have
$\mathcal{F}=\\{F\subseteq X:F=\phi(F)\\}=\\{\phi(A):A\subseteq X\\}$. We say
that $\phi$ is _standard_ if for every $a\in X$, $\phi(a)\setminus\\{a\\}$ is
closed. Consequently, $\emptyset$ is closed and $\phi(a)\neq\phi(b)$ unless
$a=b$. If $\phi(a)=\\{a\\}$ for each $a\in X$, $(X,\mathcal{F})$ is
_atomistic_. Let $(X,\phi)$ be a closure space and let $K\subseteq X$. We say
that $K$ is a _minimal spanning set_ of its closure if
$\phi(K^{\prime})\subset\phi(K)$ for every $K^{\prime}\subset K$. If moreover
$\phi(K)=X$, $K$ is a _minimal key_ of the closure space. For $c\in X$, a
subset $A\subseteq X$ is a _minimal generator_ of $c$ if $c\in\phi(A)$ but
$c\notin\phi(A^{\prime})$ for every $A^{\prime}\subset A$. Any minimal
generator of $c$ distinct from $c$ is called non-trivial. We define
$\operatorname{gen}(c)$ to be the non-trivial minimal generators of $c$.
Remark that minimal generators must be minimal spanning sets of their closure.

We move to closure systems. A set system $(X,\mathcal{F})$ is a _closure
system_ if $X\in\mathcal{F}$ and $F_{1}\cap F_{2}\in\mathcal{F}$ whenever
$F_{1},F_{2}\in\mathcal{F}$. There is a well-known correspondence between
closure operators and closure systems. More precisely, if $(X,\phi)$ is a
closure space, the set system $(X,\mathcal{F})$ is a closure system. Dually, a
closure system $(X,\mathcal{F})$ induces a closure operator
$\phi\colon\mathbf{2}^{X}\to\mathbf{2}^{X}$ given by
$\phi(A)=\bigcap\\{F\in\mathcal{F}:A\subseteq F\\}$. This correspondence is
one-to-one. The pair $(\mathcal{F},\subseteq)$ gives a _(closure) lattice_ ,
as closed sets ordered by inclusion.

######  Remark 1.

In this paper, we always assume without loss of generality that closure
systems are standard. If $(X,\mathcal{F})$ is a closure system, $\phi$ is its
closure operator.

Let $(X,\mathcal{F})$ be a closure system with closure operator $\phi$. We
introduce a closure system devised from $(X,\mathcal{F})$ that will be useful
all along the paper. Let $\phi^{b}$ be the closure operator defined by
$\phi^{b}(A)=\bigcup_{a\in A}\phi(a)$. It induces a closure system
$(X,\mathcal{F}^{b})$. We have $\mathcal{F}\subseteq\mathcal{F}^{b}$. Now let
$M\in\mathcal{F}$ such that $M\neq X$. The closed set $M$ is a _meet-
irreducible element_ of $\mathcal{F}$ if for every
$F_{1},F_{2}\in\mathcal{F}$, $F_{1}\cap F_{2}=M$ implies $F_{1}=M$ or
$F_{2}=M$. We denote by $\operatorname{Mi}(\mathcal{F})$ the meet-irreducible
elements of $\mathcal{F}$. Remark that, in fact,
$\operatorname{Mi}(\mathcal{F})$ is the set of meet-irreducible elements in
the lattice-theoretic sense of the closure lattice $(\mathcal{F},\subseteq)$.
For every closed set $F$, we have
$F=\bigcap\\{M\in\operatorname{Mi}(\mathcal{F}):F\subseteq M\\}$. Given $a\in
X$ and $M\in\operatorname{Mi}(\mathcal{F})$, we write
$a\,\scalebox{0.9}{$\nearrow$}\,M$ if $a\notin M$ but $a\in F$ for every
$F\in\mathcal{F}$ such that $M\subset F$. Equivalently
$a\,\scalebox{0.9}{$\nearrow$}\,M$ if
$M\in\max_{\subseteq}(\\{M\in\operatorname{Mi}(\mathcal{F}):a\notin M\\})$.
Dually, we write $M\,\scalebox{0.9}{$\searrow$}\,a$ if $a\notin M$ but
$\phi(a)\setminus\\{a\\}\subseteq M$.

######  Example 1.

Let $X=\\{1,2,3,4,5,6\\}$ and consider the closure system $(X,\mathcal{F})$
whose closure lattice $(\mathcal{F},\subseteq)$ is depicted in Figure 1. For
convenience we write a set as the concatenation of its elements, e.g., $1234$
stands for $\\{1,2,3,4\\}$. For instance, $\phi(25)=2456$. We have
$\operatorname{Mi}(\mathcal{F})=\\{356,13,15,1356,1456,124,2456,12456\\}$.

Figure 1: The closure lattice of Example 1. Meet-irreducible elements are
marked by black dots.

We conclude the paragraph with some classes of closure systems. Let
$(X,\mathcal{F})$ be a closure system. If for every closed set
$F\in\mathcal{F}$, $F\neq X$, there exists $a\notin F$ such that
$F\cup\\{a\\}\in\mathcal{F}$, then $(X,\mathcal{F})$ is a _convex geometry_
[EJ85]. Convex geometries are precisely the closure systems associated to
_anti-exchange_ closure operators. A closure operator $\phi$ is anti-exchange
if for every closed set $F$ and $a,b\notin F$, $b\in\phi(F\cup\\{a\\})$
entails $a\notin\phi(F\cup\\{b\\})$. Another useful characterizations of
convex geometries relies on minimal spanning sets and extreme points. Let
$F\in\mathcal{F}$. An element $a$ of $F$ is an _extreme point_ of $F$ if
$a\notin\phi(F\setminus\\{a\\})$. In particular,
$\phi(F\setminus\\{a\\})=F\setminus\\{a\\}$ must hold. Now a closure system is
a convex geometry if and only if each closed set has a unique minimal spanning
set which comprises precisely extreme points. For a given $A\subset X$, we
denote by $K_{A}$ the unique minimal spanning set of $\phi(A)$. If
$(X,\mathcal{F})$ is a closure system and $F_{1}\cup F_{2}\in\mathcal{F}$ for
every $F_{1},F_{2}\in\mathcal{F}$, then $(X,\mathcal{F})$ (or its lattice
$(\mathcal{F},\subseteq)$) is _distributive_. Every (standard) distributive
closure system is a convex geometry. In this case, we have
$\operatorname{Mi}(\mathcal{F})=\\{\\{c\in X:a\notin\phi(c)\\}:a\in X\\}$.
Hence, $|\operatorname{Mi}(\mathcal{F})|=|X|$ and
$\operatorname{Mi}(\mathcal{F})$ can be computed in polynomial time in the
size of an IB $(X,\Sigma)$. Observe that the closure system
$(X,\mathcal{F}^{b})$ defined previously is always distributive, regardless of
the underlying closure system $(X,\mathcal{F})$. In the particular case when
$(X,\mathcal{F})$ is already distributive, we have $\phi=\phi^{b}$ and
$\mathcal{F}=\mathcal{F}^{b}$.

### Implicational bases (IBs), $D$-generators, $D$-base.

We give some standard notations regarding implications and implicational bases
(see also [Wil17]). An _implication_ over $X$ is an expression $A\rightarrow
c$ where $A\cup\\{c\\}\subseteq X$, also called _unit implication_ in [BM10].

An implication is _binary_ if $A$ is a singleton. For simplicity, we write
them $a\rightarrow c$ instead of $\\{a\\}\rightarrow c$. An _implicational
base_ (IB) over $X$ is a pair $(X,\Sigma)$ where $\Sigma$ is a collection of
implications over $X$. The size of $\Sigma$ is its number of implications. An
IB induces a closure operator $\phi$ where a subset $F$ of $X$ is closed if
for every implication $A\rightarrow c\in\Sigma$, $A\subseteq F$ implies $c\in
F$. The closure of $C\subseteq X$ can be computed using the _forward chaining
procedure_. This routine starts from $C$ and builds a sequence
$C=C_{0}\subseteq C_{1}\subseteq\dots\subseteq C_{m}=\phi(C)$ of subsets of
$X$ such that, for every $1\leq i\leq m$, $C_{i}=C_{i-1}\cup\\{c\in
X:A\rightarrow c\in\Sigma,A\subseteq C_{i-1}\\}$. A closure system admits
several equivalent IBs. An implication $A\rightarrow c$ holds in a closure
system if and only if $c\in\phi(A)$.

######  Example 2.

An IB for the closure system of Example 1 is $(X,\Sigma)$ with:

$\Sigma=\\{2\rightarrow 4,6\rightarrow 5\\}\cup\\{245\rightarrow
6,34\rightarrow 1,34\rightarrow 2,34\rightarrow 5,35\rightarrow
6,45\rightarrow 6\\}$

If an IB $(X,\Sigma)$ consists only of binary implications, the corresponding
closure system is distributive. Dually, if a closure system $(X,\mathcal{F})$
is distributive, it can be represented by an IB with binary implications only.
Hence, its meet-irreducible elements or one if its IBs can be computed in
polynomial time from one another. For the distributive closure system
$(X,\mathcal{F}^{b})$ associated with a given $(X,\mathcal{F})$, we can thus
define the IB $(X,\Sigma^{b})$ with $\Sigma^{b}=\\{a\rightarrow
c:c\in\phi(a)\setminus\\{a\\},a,c\in X\\}$ to represent $(X,\mathcal{F}^{b})$.
It can be obtained in polynomial time from any IB $(X,\Sigma)$ of
$(X,\mathcal{F})$ or from $\operatorname{Mi}(\mathcal{F})$.

In this paper, we focus on the _$D$ -base_ of a closure system
$(X,\mathcal{F})$ [ANR13]. It is an IB which, among equivalent IBs of a
closure system, is uniquely defined. In order to introduce the $D$-base, it is
convenient to go through another unique IB: the _canonical direct base_ (see
[BM10] for a survey). It is the IB $(X,\Sigma_{\delta})$ devised from minimal
generators of elements of $X$, that is $\Sigma_{\delta}=\\{A\rightarrow
c:A\in\operatorname{gen}(c),c\in X\\}$.

######  Example 3.

The IB of Example 2 is not the canonical direct base $(X,\Sigma_{\delta})$ of
the closure system of Example 1. Indeed, $23$ is a minimal generator of $1$
but $23\rightarrow 1\notin\Sigma$. Also, $245\rightarrow 6$ is in $\Sigma$,
but $245$ is not a minimal generator of $6$. In fact, we have:

$\Sigma_{\delta}=\left\\{\begin{array}[]{l l l l}23\rightarrow
1,&34\rightarrow 1,&34\rightarrow 2,&2\rightarrow 4,\\\ 23\rightarrow
5,&34\rightarrow 5,&6\rightarrow 5,&23\rightarrow 6,\\\ 25\rightarrow
6,&34\rightarrow 6,&35\rightarrow 6,&45\rightarrow 6\end{array}\right\\}$

To obtain the $D$-base from the canonical direct base, we need to use minimal
generators and $\phi^{b}$. A minimal generator $A$ of $c$ is a _$D$
-generator_ of $c$ if $c\notin\phi^{b}(A)$ and for every minimal generator
$A^{\prime}$ of $c$, $A^{\prime}\subseteq\phi^{b}(A)$ implies $A^{\prime}=A$.
Remark that $c\notin\phi^{b}(A)$ means $|A|\geq 2$ as $A$ is supposed to be a
minimal generator of $c$. It will be convenient to call
$\operatorname{gen_{\mathit{D}}}(c)$ the family of $D$-generators of $c$
(w.r.t. $(X,\mathcal{F})$). The $D$-base of the closure system
$(X,\mathcal{F})$ is $(X,\Sigma_{D})$ where:

$\Sigma_{D}=\Sigma^{b}\cup\\{A\rightarrow
c:A\in\operatorname{gen_{\mathit{D}}}(c),c\in X\\}.$

######  Remark 2.

Observe that a given $c\in X$ does not need not admit $D$-generators, that is
$\operatorname{gen_{\mathit{D}}}(c)=\emptyset$ is possible. This happens if
and only if $c$ has only singleton non-trivial minimal generators. This is in
turn equivalent to $\\{a\in X:c\notin\phi(a)\\}$ being the unique meet-
irreducible element $M$ of $(X,\mathcal{F})$ satisfying
$c\,\scalebox{0.9}{$\nearrow$}\,M$. Therefore, whether
$\operatorname{gen_{\mathit{D}}}(c)=\emptyset$ can be tested in polynomial
time from both $\operatorname{Mi}(\mathcal{F})$ and an IB $(X,\Sigma)$.

######  Example 4.

Continuing Example 3, we can extract the IB $(X,\Sigma^{b})$ from
$(X,\Sigma)$: $\Sigma^{b}=\\{2\rightarrow 4,6\rightarrow 5\\}$. The IB
$(X,\Sigma)$ in Example 2 is not the $D$-base of $(X,\mathcal{F})$. Indeed,
$34\in\operatorname{gen_{\mathit{D}}}(6)$, yet $34\to 6$ is not in $\Sigma$.
Note that $25$ is a minimal generator of $6$ which does not belong to
$\operatorname{gen_{\mathit{D}}}(6)$ since $\phi^{b}(45)=45\subset
245=\phi^{b}(25)$. Finally:

$\Sigma_{D}=\Sigma^{b}\cup\\{34\rightarrow 1,34\rightarrow 2,34\rightarrow
5,\\\ 34\rightarrow 6,35\rightarrow 6,45\rightarrow 6\\}.$

In this paper we seek to solve the following two enumeration problems.

$D$-base computation with meet-irreducible elements
---
Input: |  The meet-irreducible elements $\operatorname{Mi}(\mathcal{F})$ of a closure system $(X,\mathcal{F})$
Output: |  The $D$-base $(X,\Sigma_{D})$ associated to $(X,\mathcal{F})$

$D$-base computation with implications
---
Input: |  An IB $(X,\Sigma)$ of a closure system $(X,\mathcal{F})$
Output: |  The $D$-base $(X,\Sigma_{D})$ associated to $(X,\mathcal{F})$

Observe that, by definition, the $D$-base is always a subset of the canonical
direct base. However, there may be an exponential gap between these two IBs in
the general case, even though they coincide in atomistic closure systems.

######  Example 5.

Let $X=\\{a_{1},\dots,a_{n},b_{1},\dots,b_{n},c\\}$ and let
$\Sigma=\\{a_{i}\rightarrow b_{i}:1\leq i\leq n\\}\cup\\{b_{1}\dots
b_{n}\rightarrow c\\}$. The IB $(X,\Sigma)$ is the $D$-base of its closure
system, while we have $\Sigma_{\delta}=\\{d_{1}\dots d_{n}\rightarrow
c:d_{i}\in\\{a_{i},b_{i}\\},1\leq i\leq n\\}\cup\\{a_{i}\rightarrow
b_{i}:1\leq i\leq n\\}$. Thus, $|\Sigma|=n+1$ and $|\Sigma_{\delta}|=2^{n}+1$.

As a consequence, one cannot straightforwardly apply the algorithms for
finding the canonical direct base to find the $D$-base.

### Relations $\delta$ and $D$.

Minimal and $D$-generators induce two binary relations over $X$. More
precisely, we put $c\delta a$ if $a$ belongs to a non-trivial minimal
generator of $c$. This is the $\delta$-relation. Similarly, $cDa$ means that
$a$ belongs to a $D$-generator of $c$.111the notations $\delta$ and $D$ are
standard terminology in lattice theory [ANR13, BM10, FJN95, MC97] The
resulting relation is the $D$-relation. By definition, $D\subseteq\delta$, and
the equality holds when $\Sigma^{b}=\emptyset$, i.e., when the underlying
closure system is atomistic. However, in general, $D\subset\delta$ as
illustrated in Figure 2. We note that both $\delta$ and $D$ admit
characterizations by means of $\operatorname{Mi}(\mathcal{F})$ [FJN95, MC97].
For $\delta$, $c\delta a$ holds if and only if there exists
$M\in\operatorname{Mi}(\mathcal{F})$ such that
$c\,\scalebox{0.9}{$\nearrow$}\,M$ and $a\notin M$ with $c\neq a$. For $D$,
$cDa$ holds if and only if there is $M\in\operatorname{Mi}(\mathcal{F})$ such
that $c\,\scalebox{0.9}{$\nearrow$}\,M\,\scalebox{0.9}{$\searrow$}\,a$, again
with $c\neq a$. It follows that both $\delta$ and $D$ can be recovered in
polynomial time from $\operatorname{Mi}(\mathcal{F})$.

There is a close connection between the relations $\delta$ and $D$ and
_implication-graphs_ [BCH90, HK95]. The _implication-graph_ of an IB
$(X,\Sigma)$ is the directed graph $G(\Sigma)=(X,E)$ where an arc $(a,c)$
belongs to $G(\Sigma)$ if there exists an implication $A\rightarrow c$ in
$\Sigma$ such that $a\in A$. Now, the $\delta$-relation precisely consists of
the reversed arcs of $G(\Sigma_{\delta})$. Similarly, the $D$-relation is
obtained from $G(\Sigma_{D})$ by removing the arcs coming from binary
implications and reversing the remaining ones.

######  Example 6.

Figure 2 illustrates the $\delta$\- and $D$-relations of the closure system of
Example 1. Note that $D$ is a proper subset of $\delta$.

Figure 2: The $\delta$-relation (left) and the $D$-relation (right) of Example
1 represented as directed graphs. An edge without arrow indicates arcs in both
directions (such as between 2 and 4 on the left).

When the $\delta$-relation of a closure system $(X,\Sigma)$ does not have
$\delta$-cycles, we say that $(X,\Sigma)$ is _acyclic_. For the closure system
associated to $(X,\Sigma)$ to be acyclic, it is sufficient that $G(\Sigma)$ is
acyclic [HK95]. Remark that a standard distributive closure system is acyclic.
Acyclic closure systems are particular convex geometries that have been
extensively studied as they correspond to acyclic Horn functions, poset type
convex geometries and $G$-geometries [BČKK09, HK95, Ada17, Wil94]. When the
$D$-relation is acyclic the closure system is _lower bounded_ , or simply
without $D$-cycles [FJN95, ANR13]. This class strictly generalizes acyclic
closure systems. The closure system of Example 1 is without $D$-cycles but it
contains $\delta$-cycles. Hence, it is lower bounded but not acyclic.

The third problem we study in this paper is the identification (or
computation) of the $D$-relation from an IB. Since the $D$-relation is a
binary relation over elements of $X$, this problem can be reduced to the
problem of checking whether $cDa$ holds for each pair $a,c$ of $X$:

$D$-relation identification
---
Input: |  An IB $(X,\Sigma)$ of a closure system $(X,\mathcal{F})$, and $a,c\in X$.
Question: |  Does $cDa$ hold?

##  3 Finding the $D$-relation from an implicational base

In this section we establish the hardness of computing the $D$-relation of a
closure system $(X,\mathcal{F})$ given by an arbitrary IB $(X,\Sigma)$. More
precisely, we show that given $(X,\Sigma)$ and $a,c\in X$, it is
$\mathbf{NP}$-complete to check whether $cDa$ holds, even in acyclic closure
systems or lower bounded closure systems with $D$-paths of constant size.
These are Theorems LABEL:thm:D-relation-ACG and LABEL:thm:D-relation-LB
respectively.

As a preliminary step, we show that the problem belongs to $\mathbf{NP}$. On
this purpose, we rephrase in our terms a characterization of $D$-generators
given in [FJN95, Algorithm 11.13, Equation 9, p. 230]. We could also use the
expression of $D$ based on meet-irreducible elements as mentioned in the
preliminaries, but the characterization of $D$-generators will be useful in
Section 5.

######  Lemma 6 ([FJN95]).

Let $(X,\mathcal{F})$ be a closure system, $A\subseteq X$ and $c\in X\setminus
A$. Then, $A$ is a $D$-generator of $c$ if and only if $c\in\phi(A)$ and for
every $a\in A$, $c\notin\phi(\phi^{b}(A)\setminus\\{a\\})$.

######  Corollary 1.

Whether $A$ is indeed a $D$-generator of $c$ can be tested with at most
$2\cdot|X|$ calls to $\phi$.

###### Proof.

We apply Lemma 6. First, we compute $\phi^{b}(A)=\bigcup_{a\in A}\phi(a)$ with
$|A|$ calls to $\phi$. Then, for each $a\in A$, we check whether
$c\in\phi(\phi^{b}(A)\setminus\\{a\\})$. In total, we needed at most
$2\cdot|X|$ calls to $\phi$, which concludes the proof. ∎

The closure operator $\phi$ can be simulated in polynomial time given
implications using forward chaining. Note that it can also be computed in
polynomial time from meet-irreducible elements using set intersections. We
deduce:

######  Corollary 2.

The problem of deciding, given an IB $(X,\Sigma)$ and $a,c\in X$, whether
$cDa$ holds belongs to $\mathbf{NP}$.

###### Proof.

A certificate is a $D$-generator $A$ of $c$ such that $a\in A$. Whether $A$ is
indeed a $D$-generator of $c$ can be checked in polynomial time due to
Corollary 1. ∎

We proceed to the hardness of identifying the $D$-relation in acyclic closure
systems. This is Theorem LABEL:thm:D-relation-ACG which we restate below. In
fact, the hardness result also holds under the assumption that the premises of
the input IB have constant size. We give here the reduction, but the complete
proof is delayed to Appendix A for clarity.

*

######  Proof sketch.

We showed in Corollary 2 that the problem belongs to $\mathbf{NP}$. To show
$\mathbf{NP}$-hardness, we use a reduction from the problem $1$-in-$3$-SAT:

1-in-3 SAT
---
Input: |  A positive $3$-CNF $\varphi=\\{C_{1},\dots,C_{m}\\}$ over variables $V=\\{v_{1},\dots,v_{n}\\}$
Question: |  Is there a truth assignment of the variables in $V$ which is a model of $\varphi$ and such that each clause of $\varphi$ has exactly one true literal?

Let $\varphi=\\{C_{1},\dots,C_{m}\\}$ be a non-trivial positive $3$-CNF over
$V=\\{v_{1},\dots,v_{n}\\}$. For simplicity, we view clauses as sets of
variables. Moreover, we identify an assignment of $V$ to the sets of its
variables assigned 1. Consequently, a 1-in-3 assignment of $V$ is a set of
variables $T\subset V$ such that $|C_{i}\cap T|=1$ for each clause $C_{i}$ of
$\varphi$. Two variables $v_{i},v_{j}$ are in conflict if there exists a
clause $C_{k}$ in $\varphi$ that contains both $v_{i}$ and $v_{j}$. For each
$1\leq i\leq m$, we define $\varphi_{i}=\\{C_{i},\dots,C_{m}\\}$. A subset $T$
of $V$ is $\varphi$-conflict-free (resp. $\varphi_{i}$-conflict-free) if it
does not contain variables in conflict among the clauses of $\varphi$ (resp.
$\varphi_{i}$).

We build an instance of the $D$-relation identification problem. Let
$C=\\{c_{1},\dots,c_{m},\allowbreak c_{m+1}\\}$ and let $X=C\cup V$. An
element $c_{i}$, $1\leq i\leq m$ represents the clause $C_{i}$. The element
$c_{m+1}$ is another gadget element. Now consider the set
$\Sigma=\Sigma_{mod}\cup\Sigma_{conf}$ of implications, where:

$\displaystyle\Sigma_{\mathit{mod}}$ $\displaystyle=\\{c_{i}v_{j}\rightarrow
c_{i+1}:1\leq i\leq m\text{ and }v_{j}\in C_{i}\\}$
$\displaystyle\Sigma_{\mathit{conf}}$ $\displaystyle=\\{v_{i}v_{j}\rightarrow
c_{m+1}:v_{i},v_{j}\in V\text{ and }v_{i},v_{j}\text{ are in conflict in
}\varphi\\}$

Informally, $\Sigma_{mod}$ models the fact that whenever the $i$-th clause is
satisfied, we can proceed to the $(i+1)$-th clause or $c_{m+1}$, and
$\Sigma_{conf}$ represents the conflicts induced by the variables appearing
together in a clause.

We consider $(X,\Sigma)$ and we seek to identify whether $c_{m+1}Dc_{1}$
holds. Note that $(X,\Sigma)$ can be constructed in polynomial time in the
size of $\varphi$ and $V$. The premises of $\Sigma$ have size $2$ and
$G(\Sigma)$ has no cycle. Hence, $(X,\mathcal{F})$ is an acyclic closure
system represented by an IB with premises of size at most $2$ as required.
Moreover $\Sigma$ has no binary implication to that minimal generators and
$D$-generators coincide. The proof in appendices relies on the
characterization of minimal generators of $c_{m+1}$. ∎

######  Example 7.

We illustrate the reduction of Theorem LABEL:thm:D-relation-ACG. Let
$V=\\{1,\dots,5\\}$ and let $\varphi=\\{C_{1},C_{2},C_{3}\\}$ with
$C_{1}=\\{2,3,4\\}$, $C_{2}=\\{1,2,3\\}$, $C_{3}=\\{1,3,5\\}$. According to
the reduction of Theorem LABEL:thm:D-relation-ACG, we have
$X=V\cup\\{c_{1},c_{2},c_{3},c_{4}\\}$ and
$\Sigma=\Sigma_{\mathit{mod}}\cup\Sigma_{\mathit{conf}}$ where:

$\Sigma_{\mathit{mod}}=\left\\{\begin{array}[]{l l l}4c_{1}\rightarrow
c_{2},&2c_{1}\rightarrow c_{2},&3c_{1}\rightarrow c_{2},\\\ 2c_{2}\rightarrow
c_{3},&3c_{2}\rightarrow c_{3},&1c_{2}\rightarrow c_{3},\\\ 3c_{3}\rightarrow
c_{4},&1c_{3}\rightarrow c_{4},&5c_{3}\rightarrow
c_{4}\end{array}\right\\}\text{ and
}\;\Sigma_{\mathit{conf}}=\left\\{\begin{array}[]{l l}12\rightarrow
c_{4},&13\rightarrow c_{4},\\\ 15\rightarrow c_{4},&23\rightarrow c_{4},\\\
24\rightarrow c_{4},&34\rightarrow c_{4},\\\ 35\rightarrow
c_{4}\end{array}\right\\}$

We have $\Sigma\subseteq\Sigma_{D}$, so the $D$-relation of the corresponding
closure system is a subset (once reversed) of $G(\Sigma)$. This subset is
sufficient to recover the transitive closure of $D$. We represent it in Figure
3.

Figure 3: The subset of the $D$-relation of $\Sigma$ in Example 7. This subset
is sufficient to recover the transitive closure of $D$. Whether $c_{4}Dc_{1}$
holds (highlighted in grey) depends on whether the associated formula
$\varphi$ has a $1$-in-$3$ assignment.

Deciding whether $c_{4}Dc_{1}$ holds amounts to decide whether $\varphi$ has a
1-in-3 valid assignment. Here, $14$ is such an assignment so that $14c_{1}$ is
a $D$-generator of $c_{4}$, and $c_{4}Dc_{1}$ holds true.

Remark that our reduction shows at the same time that testing $c\delta a$ is
hard in acyclic closure systems, which was also unknown to our knowledge.
Understanding what makes hard to decide whether $cDa$ holds is an intriguing
question. The reduction of Theorem LABEL:thm:D-relation-ACG and Example 7
suggest the difficulty comes from the fact that two elements can be separated
by an arbitrary long $D$-path. However, we prove in the next theorem that the
problem remains $\mathbf{NP}$-complete even when the length of a $D$-path is
constant. Interestingly though, this complexity comes at the cost of cycles in
the $\delta$-relation. Again, we give the reduction, but leave the complete
proof in Appendix B for readability.

*

######  Proof sketch.

To show $\mathbf{NP}$-hardness, we use another reduction from $1$-in-$3$ SAT.
Let $\varphi=\\{C_{1},\dots,C_{m}\\}$ be a positive $3$-CNF over variables
$V=\\{v_{1},\dots,v_{n}\\}$. Let $C=\\{c_{1},\dots,c_{m}\\}$. We use the same
terminology as in Theorem LABEL:thm:D-relation-ACG. Let $X=V\cup
C\cup\\{a,b\\}$ be a new groundset, and let
$\Sigma=\Sigma_{\mathit{mod}}\cup\Sigma_{\mathit{conf}}\cup\Sigma^{b}$ where:

$\displaystyle\Sigma_{\mathit{mod}}$ $\displaystyle=\\{av_{i}\rightarrow
c_{j}:v_{i}\in C_{j}\\}\cup\\{C\rightarrow b\\}$
$\displaystyle\Sigma_{\mathit{conf}}$ $\displaystyle=\\{v_{i}v_{j}\rightarrow
b:v_{i},v_{j}\in V\text{ and }v_{i},v_{j}\text{ are in conflict in
}\varphi\\}$ $\displaystyle\Sigma^{b}$ $\displaystyle=\\{c_{i}\rightarrow
a:c_{i}\in C\\}$

Informally, $\Sigma_{\mathit{conf}}$ models all the conflicts in between two
variables appearing in a clause and $\Sigma_{\mathit{mod}}$ models the fact
that taking one element in a clause together with $a$ for all the clauses
yields a $1$-in-$3$ assignment of $\varphi$. Finally, the binary implications
$\Sigma^{b}$ guarantee that $a$ will never appear in any minimal generator
together with one of the $c_{i}$’s. Finally, let $(X,\mathcal{F})$ be the
closure system associated to $(X,\Sigma)$. We call $\phi$ the corresponding
closure operator. The reduction can be conducted in polynomial time. The rest
of the proof shows that: (1) $(X,\Sigma)$ and $(X,\mathcal{F})$ meet the
requirements of the statement, and (2) $bDa$ holds if and only if $\varphi$
has a valid 1-in-3 assignment. ∎

######  Example 8.

We illustrate the reduction on the same formula as in Example 7. Here, we will
have $C=\\{c_{1},c_{2},c_{3}\\}$ and $X=V\cup C\cup\\{a,b\\}$ and
$\Sigma=\Sigma_{\mathit{mod}}\cup\Sigma_{\mathit{conf}}\cup\Sigma_{a}$ where
$\Sigma^{b}=\\{c_{1}\rightarrow a,c_{2}\rightarrow a,c_{3}\rightarrow a\\}$
and:

$\Sigma_{\mathit{mod}}=\left\\{\begin{array}[]{l l l}4a\rightarrow
c_{1},&2a\rightarrow c_{1},&3a\rightarrow c_{1},\\\ 2a\rightarrow
c_{2},&3a\rightarrow c_{2},&1a\rightarrow c_{2},\\\ 3a\rightarrow
c_{3},&1a\rightarrow c_{3},&5a\rightarrow c_{3},\\\ c_{1}c_{2}c_{3}\rightarrow
b\end{array}\right\\}\text{,
}\;\Sigma_{\mathit{conf}}=\left\\{\begin{array}[]{l l}12\rightarrow
b,&13\rightarrow b,\\\ 15\rightarrow b,&23\rightarrow b,\\\ 24\rightarrow
b,&34\rightarrow b,\\\ 35\rightarrow b\end{array}\right\\}.$

Again, $\Sigma\subseteq\Sigma_{D}$ so reversing the arcs of $G(\Sigma)$ and
dropping arcs of the binary implications in $\Sigma^{b}$ gives a subset of the
$D$-relation, see Figure 4.

Figure 4: The subset of the $D$-relation of $\Sigma$ in Example 8. The only
possible missing pair in the $D$-relation is $bDa$. Observe that the
$D$-relation is acyclic and that all paths have size at most $2$. Whether
$bDa$ holds (highlighted in grey) depends on whether the associated formula
$\varphi$ has a $1$-in-$3$ assignment.

Whether the $D$-relation can be computed in polynomial time when restricted to
acyclic closure systems with $D$-paths of constant size remains an open
question for future work.

##  4 Finding the $D$-base from meet-irreducible elements

We prove that there exists an output-polynomial time algorithm for computing
the $D$-base given meet-irreducible elements if and only if there is an
output-polynomial time algorithm for dualization in distributive lattices,
i.e., Theorem LABEL:thm:D-base-dual. Building on the algorithm of [Elb22]
solving this latter problem in output-quasi-polynomial time, we deduce that
the $D$-base of a closure system given by its meet-irreducible elements can be
computed in output-quasi-polynomial time too. This is Theorem
LABEL:thm:D-base-Mi.

We first give some definitions related to dualization. Let $(X,\mathcal{F})$
be a closure system. An _antichain_ of the lattice $(\mathcal{F},\subseteq)$
is a subset $\mathcal{B}$ of $\mathcal{F}$ consisting of pairwise incomparable
closed sets. We write $\downarrow\mathcal{B}$ the _ideal_ of $\mathcal{B}$ in
$(\mathcal{F},\subseteq)$, i.e.,
$\downarrow\mathcal{B}=\\{F\in\mathcal{F}:F\subseteq B\text{ for some
}B\in\mathcal{B}\\}$. The _filter_ of $\mathcal{B}$, denoted
$\uparrow\mathcal{B}$, is defined dually. Let $\mathcal{B}^{-}$,
$\mathcal{B}^{+}$ be two antichains of $(\mathcal{F},\subseteq)$. We say that
$\mathcal{B}^{-}$ and $\mathcal{B}^{+}$ are _dual_ in
$(\mathcal{F},\subseteq)$ if
$\uparrow\mathcal{B}^{-}\cup\downarrow\mathcal{B}^{+}=\mathcal{F}$ and
$\uparrow\mathcal{B}^{-}\cap\downarrow\mathcal{B}^{+}=\emptyset$. For each
antichain $\mathcal{B}^{+}$, there exists a unique dual antichain
$\mathcal{B}^{-}$ to $\mathcal{B}^{+}$. In particular, we have
$\mathcal{B}^{-}=\min_{\subseteq}(\\{F\in\mathcal{F}:F\nsubseteq B,\text{ for
all }B\in\mathcal{B}^{+}\\})$. Symmetrically, each antichain $\mathcal{B}^{-}$
has a unique dual antichain $\mathcal{B}^{+}$. The problem of dualizing
distributive lattices now reads as follows.

Distributive lattice dualization
---
Input: |  An IB $(X,\Sigma)$ of a distributive closure system $(X,\mathcal{F})$ and an antichain $\mathcal{B}^{+}$ of $(\mathcal{F},\subseteq)$.
Output: |  The antichain $\mathcal{B}^{-}$ dual to $\mathcal{B}^{+}$ in $(\mathcal{F},\subseteq)$.

This problem is a generalization of hypergraph dualization (see [EG95, EMG08]
for further details on this task). In hypergraph dualization, $\Sigma$ is
empty and the corresponding distributive lattice is in fact the powerset
(Boolean) lattice $(\mathbf{2}^{X},\subseteq)$. Since one can translate
between the meet-irreducible elements and an IB of a distributive closure
system in polynomial time, the input to dualization in distrbutive lattices
can be considered to be either of the two representations, or even both.

######  Example 9.

Let $X=\\{1,2,3,4,5\\}$ and consider the (distributive) closure system
$(X,\mathcal{F})$ given by the IB $(X,\Sigma)$ with $\Sigma$:

$\Sigma=\\{3\rightarrow 2,2\rightarrow 1,3\rightarrow 1,5\rightarrow 4\\}$

The corresponding closure lattice is depicted in Figure 5. Remark that
$\Sigma=\Sigma^{b}$. The antichains $\mathcal{B}^{-}=\\{123,\allowbreak
124,145\\}$ and $\mathcal{B}^{+}=\\{12,14,45\\}$ are dual in
$(\mathcal{F},\subseteq)$. They are highlighted in Figure 5.

Figure 5: The distributive lattice of Example 9 with two dual antichains
$\mathcal{B}^{+}$, $\mathcal{B}^{-}$.

In view of Theorem LABEL:thm:D-base-dual, we first reduce dualization of
distributive lattices to the problem of computing the $D$-base of a closure
system given its meet-irreducible elements. Let $(X,\Sigma)$ be a binary IB of
a distributive closure system $(X,\mathcal{F})$. Remind from Section 2 that
$\phi=\phi^{b}$ as $(X,\mathcal{F})$ is distributive. Moreover, recall that
distributive closure systems are acyclic convex geometries. Hence, each closed
set $F\in\mathcal{F}$ has a unique minimal spanning set $K_{F}$. Let
$\mathcal{B}^{+}$ be an (non-empty) antichain of $(\mathcal{F},\subseteq)$,
and let $\mathcal{B}^{-}$ be its dual antichain.

Let $X^{\prime}=X\cup\\{d\\}$ where $d$ is a new gadget element. We first
construct a closure system $(X^{\prime},\mathcal{F}^{\prime})$ by means of its
meet-irreducible elements which we define as follows:

$\operatorname{Mi}(\mathcal{F}^{\prime})=\mathcal{B}^{+}\cup\\{M\cup\\{d\\}:M\in\operatorname{Mi}(\mathcal{F})\\}$

Remark that $\operatorname{Mi}(\mathcal{F}^{\prime})$ can be constructed in
polynomial time from $(X,\Sigma)$, $\mathcal{B}^{+}$, and that is a well-
defined collection of meet-irreducible elements. Indeed, each
$B\in\mathcal{B}^{+}$ is incomparable to every other set of $\mathcal{B}^{+}$
and other sets in $\operatorname{Mi}(\mathcal{F}^{\prime})$ always contain
$d$. So $B$ cannot be obtained as the intersection of different sets in
$\operatorname{Mi}(\mathcal{F}^{\prime})$. The fact that $M\cup\\{d\\}$ is
meet-irreducible comes from the observations that $d\in M\cup\\{d\\}$ and
$M\in\operatorname{Mi}(\mathcal{F})$. We call $\phi^{\prime}$ the closure
operator associated to $(X^{\prime},\mathcal{F}^{\prime})$. We readily have
that
$\mathcal{F}^{\prime}=\\{F\in\mathcal{F}:F\in\downarrow\mathcal{B}^{+}\text{
in }(\mathcal{F},\subseteq)\\}\cup\\{F\cup\\{d\\}:F\in\mathcal{F}\\}$ and, for
each $A\subseteq X^{\prime}$,

$\phi^{\prime}(A)=\begin{cases}\phi(A)&\text{if }d\notin A\text{ and
}\phi(A)\in\downarrow\mathcal{B}^{+}\text{ in }(\mathcal{F},\subseteq)\\\
\phi(A\setminus\\{d\\})\cup\\{d\\}&\text{otherwise.}\end{cases}$

Remark that $(X^{\prime},\mathcal{F}^{\prime})$ is standard as long as
$(X,\mathcal{F})$ is. Moreover, for each $a\in X^{\prime}$,
$\phi^{b}(a)\subseteq\phi^{\prime b}(a)$ holds. Thus,
$\phi(A)=\phi^{b}(A)\subseteq\phi^{\prime b}(A)\subseteq\phi^{\prime}(A)$ for
all $A\subseteq X$. If $a\in X$ and $d\notin\phi^{\prime b}(a)$, then
$\phi^{b}(a)=\phi^{\prime b}(a)$. As a consequence, for every $A\subseteq
X^{\prime}$ such that $d\notin\phi^{\prime}(A)$,
$\phi(A)=\phi^{b}(A)=\phi^{\prime b}(A)$. We proceed to show that the
antichain $\mathcal{B}^{-}$ dual to $\mathcal{B}^{+}$ in
$(\mathcal{F},\subseteq)$ can be recovered in polynomial time from the
$D$-base $(X^{\prime},\Sigma^{\prime}_{D})$ of
$(X^{\prime},\mathcal{F}^{\prime})$. We begin with a useful claim regarding
the nature of $(X^{\prime},\mathcal{F}^{\prime})$.

######  Proposition 1.

The closure system $(X^{\prime},\mathcal{F}^{\prime})$ is a convex geometry.
Therefore, each closed set $F^{\prime}\in\mathcal{F}^{\prime}$ has a unique
minimal spanning set $K^{\prime}_{F}$.

###### Proof.

To show that $(X^{\prime},\mathcal{F}^{\prime})$ is a convex geometry, we
prove that for each closed set $F^{\prime}\neq X^{\prime}$, there is $a\in
X^{\prime}\setminus F^{\prime}$ such that $F^{\prime}\cup\\{a\\}$ is closed.
If $d\notin F^{\prime}$, then $d=a$ meets the requirement. Assume $d\in
F^{\prime}$. Then, $F^{\prime}$ lies in $\\{F\cup\\{d\\}:F\in\mathcal{F}\\}$.
Put $F^{\prime}=F\cup\\{d\\}$ with $F\in\mathcal{F}$. Since $(X,\mathcal{F})$
is distributive, it is a convex geometry and as $F^{\prime}\neq X^{\prime}$,
there exists $a\in X\setminus F$ such that $F\cup\\{a\\}\in\mathcal{F}$ so
that $F^{\prime}\cup\\{a\\}\in\mathcal{F}^{\prime}$ holds. We deduce that
$(X^{\prime},\mathcal{F}^{\prime})$ is a convex geometry, which concludes the
proof. ∎

Then, we characterize the $D$-base of $(X^{\prime},\mathcal{F}^{\prime})$.
Recall that since $(X,\mathcal{F})$ is distributive, $\Sigma=\Sigma^{b}$
faithfully represents $(X,\mathcal{F})$. Henceforth, every non-trivial minimal
generator in $(X,\mathcal{F})$ is a singleton, meaning that there is no
$D$-generator in $(X,\mathcal{F})$. In the next statement we characterize the
$D$-base of $(X^{\prime},\Sigma^{\prime}_{D})$. Again, the proof is given in
Appendix C for readability.

######  Proposition 2 (restate=PDB, label=prop:D-base-dual-DB).

The $D$-base $(X^{\prime},\Sigma^{\prime}_{D})$ of
$(X^{\prime},\mathcal{F}^{\prime})$ is defined by:

$\Sigma^{\prime}_{D}=\Sigma^{\prime b}\cup\\{K^{\prime}_{B}\rightarrow
d:B\in\mathcal{B}^{-},|K^{\prime}_{B}|\geq 2\\}$

where $\Sigma^{\prime b}=\Sigma^{b}\cup\\{a\rightarrow
d:B\subseteq\phi(a)\text{ for some }B\in\mathcal{B}^{-}\\}$.

######  Proposition 3.

The $D$-base $(X^{\prime},\Sigma^{\prime}_{D})$ has polynomial size with
respect to the sizes of $(X,\Sigma)$ and $\mathcal{B}^{-}$.

###### Proof.

This follows from the fact that for all $B\in\mathcal{B}^{-}$,
$\phi^{\prime}(B)$ has a unique minimal spanning set as
$(X^{\prime},\mathcal{F}^{\prime})$ is a convex geometry in virtue of
Proposition 1. ∎

We are in position to conclude the first side of the reduction.

######  Lemma 7.

There is an output-polynomial time algorithm for dualization in distributive
lattices if there is one for computing the $D$-base of a closure system given
its meet-irreducible elements.

###### Proof.

Let A be an output-polynomial time algorithm computing the $D$-base of a
closure system given its meet-irreducible elements. Given an instance
$(X,\Sigma)$, $\mathcal{B}^{+}$ of distributive lattice dualization, we show
how to compute $\mathcal{B}^{-}$ in output-polynomial time using A. First, we
build $X^{\prime}$ and $\operatorname{Mi}(\mathcal{F}^{\prime})$ in polynomial
time. Then, we use A to compute $(X^{\prime},\Sigma^{\prime}_{D})$ in time
polynomial with respect to $(X,\Sigma),\mathcal{B}^{+}$ and $\mathcal{B}^{-}$
according to Proposition 3. Based on Proposition LABEL:prop:D-base-dual-DB, we
can recover a subset of $\mathcal{B}^{-}$ in polynomial time by computing
$\phi(K^{\prime}_{B})$ in polynomial time for each $K^{\prime}_{B}\rightarrow
d$ in $\Sigma^{\prime}_{D}$. Again by Proposition LABEL:prop:D-base-dual-DB,
the only missing elements of $\mathcal{B}^{-}$ are of the form $\phi(a)$ for
some $a\in X$ if there is any. To identify such elements, we go through the
following operations:

  * •

find the elements $a\in X$ such that $d\in\phi^{\prime}(a)$ but
$K^{\prime}_{B}\nsubseteq\phi^{\prime}(a)$ for each $K^{\prime}_{B}$ appearing
in the non-binary part of $\Sigma^{\prime}_{D}$. This can be done in time
polynomial in the size of $\mathcal{B}^{-}$ and
$\operatorname{Mi}(\mathcal{F}^{\prime})$, hence in output-polynomial time.

  * •

among these elements, find those whose closure with respect to $\phi^{\prime
b}$ is inclusion-wise minimal. This can be done in polynomial time in the size
of $\operatorname{Mi}(\mathcal{F}^{\prime})$ and $X^{\prime}$.

Computing the closure in $\phi$ of the resulting elements will produce the
remaining parts of $\mathcal{B}^{-}$. As long as A output-polynomial time, the
whole procedure correctly output the antichain $\mathcal{B}^{-}$ dual to
$\mathcal{B}^{+}$ in $(\mathcal{F},\subseteq)$ in output-polynomial time. This
concludes the proof. ∎

We illustrate the reduction with the closure lattice of Example 9.

######  Example 10.

In Example 9 we have $\mathcal{B}^{+}=\\{12,14,5\\}$ and
$\mathcal{B}^{-}=\\{123,124,145\\}$ (see Figure 5). As in the reduction we
define $X^{\prime}=X\cup\\{d\\}$ and the meet-irreducible elements of the
closure system $(X^{\prime},\mathcal{F}^{\prime})$:

$\operatorname{Mi}(\mathcal{F}^{\prime})=\mathcal{B}^{+}\cup\\{M\cup\\{d\\}:M\in\operatorname{Mi}(\mathcal{F})\\}=\\{12,14,5,45d,123d,145d,1234d,1245d\\}$

Following Proposition LABEL:prop:D-base-dual-DB, the $D$-base of
$(X^{\prime},\Sigma^{\prime}_{D})$ of $(X^{\prime},\mathcal{F}^{\prime})$ is
given by:

$\Sigma^{\prime}_{D}=\\{3\rightarrow 2,3\rightarrow 1,3\rightarrow
d,5\rightarrow 4\\}\cup\\{24\rightarrow d,15\rightarrow d\\}$

We represent the closure lattice $(\mathcal{F}^{\prime},\subseteq)$ in Figure
6. Finding the $D$-base $(X^{\prime},\Sigma^{\prime}_{D})$ from
$\operatorname{Mi}(\mathcal{F}^{\prime})$ amounts to find (polynomially many)
binary implications plus the unique minimal spanning sets of each element of
$\mathcal{B}^{-}$ not covered by binary implications. Here, $124$ and $145$
are generated by non-binary implications of the $D$-base, namely
$24\rightarrow d$ and $15\rightarrow d$. The last element of
$\mathcal{B}^{-}$, $123$, is identified by $3\rightarrow d$.

Figure 6: The lattice $(\mathcal{F}^{\prime},\subseteq)$ resulting from the
reduction of Lemma 7 applied to Example 9. Observe that $\mathcal{B}^{+}$ is
now part of $\operatorname{Mi}(\mathcal{F}^{\prime})$.

We turn our attention to the other side of Theorem LABEL:thm:D-base-dual,
namely, that an output-polynomial time algorithm for solving distributive
lattice dualization yields an output-polynomial time algorithm for computing
the $D$-base of a closure system given its meet-irreducible elements. To do
so, we prove that finding the $D$-base of a closure system $(X,\mathcal{F})$
given by $\operatorname{Mi}(\mathcal{F})$ reduces to (at most) $|X|$ instances
of distributive lattice dualization. More precisely, we show that given $c\in
X$, we can recover $\operatorname{gen_{\mathit{D}}}(c)$ from the antichain
dual to
$\\{M\in\operatorname{Mi}(\mathcal{F}):c\,\scalebox{0.9}{$\nearrow$}\,M\\}$ in
the distributive lattice $(\mathcal{F}^{b},\subseteq)$. We formalize this idea
in Lemma 8, and we illustrate it via Example 11.

######  Lemma 8.

Let $(X,\mathcal{F})$ be a closure system. For $c\in X$, the two following
antichains are dual in $(\mathcal{F}^{b},\subseteq)$:

  * •

$\mathcal{B}^{+}=\\{M\in\operatorname{Mi}(\mathcal{F}):c\,\scalebox{0.9}{$\nearrow$}\,M\\}$

  * •

$\mathcal{B}^{-}=\\{\phi^{b}(A):A\in\operatorname{gen_{\mathit{D}}}(c)\\}\cup\\{\phi^{b}(c)\\}$

Moreover, $\phi^{b}$ is a one-to-one mapping between
$\operatorname{gen_{\mathit{D}}}(c)$ and
$\\{\phi^{b}(A):A\in\operatorname{gen_{\mathit{D}}}(c)\\}$.

###### Proof.

First, we prove that $\mathcal{B}^{-}$ and $\mathcal{B}^{+}$ are indeed
antichains of $(\mathcal{F}^{b},\subseteq)$. Since
$\mathcal{F}\subseteq\mathcal{F}^{b}$, each
$M\in\operatorname{Mi}(\mathcal{F})$ belongs to $\mathcal{F}^{b}$. Moreover,
by definition of  $\nearrow$ , all the meet-irreducible elements of
$\mathcal{B}^{+}$ must be incomparable. Thus, $\mathcal{B}^{+}$ is an
antichain of $(\mathcal{F}^{b},\subseteq)$. For $\mathcal{B}^{-}$,
$\mathcal{B}^{-}\subseteq\mathcal{F}^{b}$ holds by definition. The fact that
$\mathcal{B}^{-}$ is an antichain follows from the definition of
$D$-generators.

We proceed to show that $\mathcal{B}^{-}$ and $\mathcal{B}^{+}$ are dual.
First, we prove that
$\uparrow\mathcal{B}^{-}\cap\downarrow\mathcal{B}^{+}=\emptyset$. It is
sufficient to show that
$\mathcal{B}^{-}\cap\downarrow\mathcal{B}^{+}=\emptyset$, i.e., that for each
$B\in\mathcal{B}^{-}$, $B\nsubseteq M$ for every $M\in\mathcal{B}^{+}$. Since
$\mathcal{B}^{+}=\\{M\in\operatorname{Mi}(\mathcal{F}):c\,\scalebox{0.9}{$\nearrow$}\,M\\}$
and $\phi(c)=\phi^{b}(c)$, we readily have that $\phi^{b}(c)\nsubseteq M$ for
each $M\in\mathcal{B}^{+}$. We consider $\operatorname{gen_{\mathit{D}}}(c)$.
Note that if $\operatorname{gen_{\mathit{D}}}(c)=\emptyset$, then
$\uparrow\mathcal{B}^{-}\cap\downarrow\mathcal{B}^{+}=\emptyset$ is already
proved. Hence, assume $\operatorname{gen_{\mathit{D}}}(c)\neq\emptyset$ and
let $A\in\operatorname{gen_{\mathit{D}}}(c)$. We have
$A\in\operatorname{gen}(c)$. Thus, for every
$M\in\operatorname{Mi}(\mathcal{F})$ such that
$c\,\scalebox{0.9}{$\nearrow$}\,M$, there exists $a\in A\setminus M$.
Consequently, $\phi^{b}(A)\nsubseteq\phi^{b}(M)=M$. We derive that
$\uparrow\mathcal{B}^{-}\cap\downarrow\mathcal{B}^{+}=\emptyset$ as required.

It remains to show that
$\uparrow\mathcal{B}^{-}\cup\downarrow\mathcal{B}^{+}=\mathcal{F}^{b}$. It is
sufficient to show that for every $F\in\mathcal{F}^{b}$ such that
$F\notin\downarrow\mathcal{B}^{+}$, $F\in\uparrow\mathcal{B}^{-}$. If $c\in
F$, $F\in\uparrow\mathcal{B}^{-}$ holds as $\phi^{b}(c)\in\mathcal{B}^{-}$.
Hence, suppose that $c\notin F$. Let $K_{F}$ be the unique minimal spanning
set of $F$ in $(X,\mathcal{F}^{b})$. Note that $K_{F}$ is indeed unique since
$(\mathcal{F}^{b},\subseteq)$ is distributive. Now, for each
$M\in\mathcal{B}^{+}$, $\phi^{b}(K_{F})=F\nsubseteq M=\phi^{b}(M)$ holds if
and only if $K_{F}\nsubseteq M$ since $\phi^{b}$ is a closure operator. We
deduce that $\phi(K_{F})\nsubseteq M$ for each
$M\in\operatorname{Mi}(\mathcal{F})$ such that
$c\,\scalebox{0.9}{$\nearrow$}\,M$ by definition of $\mathcal{B}^{+}$. By
definition of  $\nearrow$ , every closed set $F$ of $\mathcal{F}$ either
contains $c$ or satisfies $F\subseteq M$ for some $M$ such that
$c\,\scalebox{0.9}{$\nearrow$}\,M$. It follows that $c\in\phi(K_{F})$. As
$c\notin K_{F}$, we obtain that $K_{F}$ contains a minimal generator of $c$.
Thus, $K_{F}$ can be modified to obtain a $D$-generator $A$ of $c$ and
$\phi^{b}(A)\subseteq F$ holds. We obtain $F\in\uparrow\mathcal{B}^{-}$ as
expected. Therefore,
$\uparrow\mathcal{B}^{-}\cup\downarrow\mathcal{B}^{+}=\mathcal{F}^{b}$ holds.

The two antichains $\mathcal{B}^{-}$ and $\mathcal{B}^{+}$ satisfy
$\uparrow\mathcal{B}^{-}\cap\downarrow\mathcal{B}^{+}=\emptyset$ and
$\uparrow\mathcal{B}^{-}\cup\downarrow\mathcal{B}^{+}=\mathcal{F}^{b}$. We
deduce that they are dual in $(\mathcal{F}^{b},\subseteq)$, which concludes
this part of the proof.

The fact that $\phi^{b}$ defines a one-to-one correspondence between
$D$-generators follows from the fact that each $A$ in
$\operatorname{gen_{\mathit{D}}}(c)$ is the unique minimal spanning set of
$\phi^{b}(A)$ in $(\mathcal{F}^{b},\subseteq)$. ∎

######  Example 11.

Let $X=\\{1,2,3,4,5\\}$ and consider the closure system $(X,\mathcal{F})$ with
$D$-base $(X,\Sigma_{D})$, where

$\Sigma_{D}=\\{3\rightarrow 2,4\rightarrow 2\\}\cup\left\\{\begin{array}[]{l l
l}25\rightarrow 1,&34\rightarrow 1,&15\rightarrow 2,\\\ 14\rightarrow
3,&15\rightarrow 3,&25\rightarrow 3,\\\ 13\rightarrow 4,&25\rightarrow
4,&15\rightarrow 4,\\\ 34\rightarrow 5,&13\rightarrow 5,&14\rightarrow
5\end{array}\right\\}$

We have $\Sigma^{b}=\\{3\rightarrow 2,4\rightarrow 2\\}$. The lattice
$(X,\mathcal{F})$ is given in Figure 7. The meet-irreducible elements are
$\operatorname{Mi}(\mathcal{F})=\\{1,12,23,24,5\\}$.

Figure 7: The closure lattice of Example 11. Black dots are meet-irreducible
elements.

For instance, we have $\operatorname{gen_{\mathit{D}}}(5)=\\{13,14,34\\}$. In
Figure 8 we show the distributive closure lattice
$(\mathcal{F}^{b},\subseteq)$ associated to $(X,\mathcal{F})$ and we highlight
the two dual antichains associated to $5$:

  * •

$\mathcal{B}^{+}=\\{M\in\operatorname{Mi}(\mathcal{F}):5\,\scalebox{0.9}{$\nearrow$}\,M\\}=\\{12,23,24\\}$

  * •

$\mathcal{B}^{-}=\phi^{b}(5)\cup\\{\phi^{b}(A):A\in\operatorname{gen_{\mathit{D}}}(5)\\}=\\{5,123,124,234\\}$

Since $(\mathcal{F}^{b},\subseteq)$ is distributive, each closed set has a
unique minimal spanning set. Moreover, $D$-generators are minimal spanning
sets of their closure. Hence, $\phi$ is a one-to-one correspondence between
$\operatorname{gen_{\mathit{D}}}(5)$ and
$\mathcal{B}^{-}\setminus\\{\phi^{b}(5)\\}=\\{123,124,234\\}$ as specified by
Lemma 8.

Figure 8: The distributive closure lattice $(\mathcal{F}^{b},\subseteq)$ of
Example 11. Two dual antichains are highlighted: the meet-irreducible elements
$M$ satisfying $5\,\scalebox{0.9}{$\nearrow$}\,M$ ($\mathcal{B}^{+}$) and the
closures of $D$-generators of $5$ along with the closure of $5$
($\mathcal{B}^{-}$).

Using Lemma 8, we demonstrate how dualization in distributive lattices can be
used to find the $D$-base from meet-irreducible elements.

######  Lemma 9.

There is an output-polynomial time algorithm for computing the $D$-base of a
closure system given by its meet-irreducible elements if there is one for
dualization in distributive lattices.

###### Proof.

As a preliminary step, we compute the binary part $\Sigma^{b}$ of $\Sigma_{D}$
using $\operatorname{Mi}(\mathcal{F})$. Since $\Sigma^{b}=\\{a\rightarrow
c:a,c\in X,c\in\phi(a),a\neq c\\}$ and $\phi(A)$ can be computed in polynomial
time from $\operatorname{Mi}(\mathcal{F})$ for every $A\subseteq X$,
determining $\Sigma^{b}$ from $\operatorname{Mi}(\mathcal{F})$ takes
polynomial time. The IB $(X,\Sigma^{b})$ is an IB for $(X,\mathcal{F}^{b})$.

Suppose there exists an output-polynomial time for dualization of distributive
lattices. Let $c\in X$ and let
$\mathcal{B}^{+}=\\{M\in\operatorname{Mi}(\mathcal{F}):c\,\scalebox{0.9}{$\nearrow$}\,M\\}$.
Observe that $\mathcal{B}^{+}$ can be identified in polynomial time from
$\operatorname{Mi}(\mathcal{F})$ as $c\,\scalebox{0.9}{$\nearrow$}\,M$ is
equivalent to
$M\in\max_{\subseteq}(\\{M\in\operatorname{Mi}(\mathcal{F}):c\notin M\\})$.
Now we use A to compute the antichain $\mathcal{B}^{-}$ dual to
$\mathcal{B}^{+}$ in $(\mathcal{F}^{b},\subseteq)$ in output-polynomial time.
By Lemma 8,
$\mathcal{B}^{-}=\phi^{b}(c)\cup\\{\phi^{b}(A):A\in\operatorname{gen_{\mathit{D}}}(c)\\}$.
Instead of outputting $\phi^{b}(A)$ for each
$A\in\operatorname{gen_{\mathit{D}}}(c)$, we output $A\rightarrow c$. Since
$(\mathcal{F}^{b},\subseteq)$ is a (standard) distributive closure lattice,
$A$ is the unique minimal spanning set of $\phi^{b}(A)$. Henceforth, $A$ can
be computed in polynomial time by greedily removing elements. By Lemma 8,
$\phi^{b}$ defines a bijection between $\operatorname{gen_{\mathit{D}}}(c)$
and $\mathcal{B}^{-}\setminus\\{\phi^{b}(c)\\}$ so that the size of
$\mathcal{B}^{-}$ is bounded by $|\operatorname{gen_{\mathit{D}}}(c)|+1$.
Consequently, the subset $\\{A\rightarrow
c:A\in\operatorname{gen_{\mathit{D}}}(c)\\}$ is obtained in output-polynomial
time using A.

Applying this algorithm to each element of $X$ yields the $D$-base of the
closure system. Note that since there are only $|X|$ calls to A, each
generator will be output at most $|X|$ times. Thus, the algorithm correctly
outputs the $D$-base associated to $\operatorname{Mi}(\mathcal{F})$ in output-
polynomial time as required. ∎

Combining Lemmas 7 and 9 we finally obtain Theorem LABEL:thm:D-base-dual which
we restate below. *

It is shown in [Elb22] that dualization in distributive lattices can be solved
in output-quasi-polynomial time. Therefore, we obtain Theorem
LABEL:thm:D-base-Mi

*

##  5 Finding the $D$-base from an implicational base

In this part, we give an algorithm which computes the $D$-base of a closure
system given by an IB with polynomial delay, i.e., Theorem LABEL:thm:D-base-
IB. On this purpose we use results of Ennaoui and Nourine [EN16] based on the
solution graph traversal method. Recall that the principle of this technique
is to traverse a (directed) graph, called the _solution graph_ , whose
vertices are the solutions to enumerate and whose arcs are devised from a
suitably chosen _transition function_. The next theorem restates the
conditions needed to obtain polynomial delay with solution graph traversal. We
note that to avoid repetitions during enumeration, the algorithm may require
exponential space. We redirect the reader to, e.g., [BEG04, Elb14, JYP88] for
further details on this folklore technique.

######  Theorem 10 (Folklore).

Let $\Pi$ be an enumeration problem which on input $x$ has solutions
$\mathcal{S}(x)$. We further assume that $\mathcal{S}(x)$ is a collection of
subsets of a groundset $X$ being part of the input $x$. Let
$\mathcal{N}:\mathcal{S}(x)\to\mathbf{2}^{\mathcal{S}(x)}$ be a transition
function and define $\mathcal{G}$ as the directed graph—the solution graph—on
$\mathcal{S}(x)$ where there is an arc from $S_{1}$ to $S_{2}$ if
$S_{2}\in\mathcal{N}(S_{1})$. Then, $\mathcal{S}(x)$ can be computed with
polynomial delay if the next three conditions hold:

  1. 1.

a first solution $S_{0}$ of $\mathcal{S}(x)$ can be computed in input
polynomial time (i.e., polynomial in the size of $x$);

  2. 2.

for each $S\in\mathcal{S}$, $\mathcal{N}(S)$ can be computed in input
polynomial time;

  3. 3.

$\mathcal{G}$ is strongly connected.

Let $(X,\Sigma)$ be an IB. Our aim is to find an appropriate transition
function to list all the $D$-generators of $(X,\Sigma)$ based on Theorem 10.
As an intermediate step, we will show how to list the $D$-generators of some
element $c$ with the same technique. For convenience, let us define
$X_{c}=\\{a\in X:c\notin\phi(a)\\}$. Observe that $c\notin X_{c}$ and that
$X_{c}$ contains at least all the elements of $X$ that appear in
$D$-generators of $c$.

######  Remark 3.

Recall from Section 2 that $X_{c}\in\mathcal{F}$ if and only if $c$ has no
$D$-generators. In this case, there is nothing to enumerate. Hence, In what
follows, we assume that $c$ has at least one $D$-generator to be found, hence
that $X_{c}\notin\mathcal{F}$.

We first relate the problem of finding $\operatorname{gen}_{D}(c)$ to the task
of finding the so called _$D$ -minimal keys_ of a (standard) closure system.
Similarly to $D$-generators, a minimal key $K$ of a closure system
$(X,\mathcal{F})$ is a _$D$ -minimal key_ if for every minimal key
$K^{\prime}$, $\phi^{b}(K^{\prime})\subseteq\phi^{b}(K)$ entails
$K=K^{\prime}$. Using $X_{c}$, we build an implicational base
$(X_{c},\Sigma_{c})$ where:

$\displaystyle\Sigma_{c}=$ $\displaystyle\\{A\rightarrow
b\in\Sigma:A\cup\\{b\\}\subseteq X_{c}\\}\ \cup$ $\displaystyle\\{A\rightarrow
b:A\rightarrow d\in\Sigma,A\subseteq X_{c},d\notin X_{c},b\in
X_{c}\setminus\phi^{b}(A)\\}$

Note that $(X_{c},\Sigma_{c})$ is standard. Indeed, $\emptyset$ remains closed
in $\mathcal{F}_{c}$ as long as it is already in $\mathcal{F}$, and
$\phi(a)=\phi_{c}(a)$ by definition of $\Sigma_{c}$ as long as $a\in X_{c}$.
In particular $\Sigma_{c}^{b}=\Sigma^{b}\setminus\\{a\rightarrow
d:c\in\phi(d)\\}$, so that for every $D$-generator $A$ of $c$,
$\phi_{c}^{b}(A)=\phi^{b}(A)$. Furthermore, $(X_{c},\Sigma_{c})$ can be
computed in polynomial time in the size of $(X,\Sigma)$. We argue that
$D$-generators of $c$ in $(X,\mathcal{F})$ are precisely the $D$-minimal keys
of $(X_{c},\mathcal{F}_{c})$.

######  Lemma 11.

The $D$-generators of $c$ in $(X,\Sigma)$ are precisely the $D$-minimal keys
of $(X_{c},\Sigma_{c})$.

###### Proof.

As a preliminary observation, remark that both $D$-minimal keys of
$(X_{c},\mathcal{F}_{c})$ and $D$-generators of $c$ lie in $X_{c}$ by
definition.

We prove that for every $S\subseteq X_{c}$, $\phi_{c}(S)=X_{c}$ if and only if
$c\in\phi(S)$. Suppose first that $c\in\phi(S)$ and let
$S=S_{0},\dots,S_{k}=\phi(S)$ be the sequence of sets obtained using forward
chaining on $S$ with $\Sigma$. Since $S\subseteq X_{c}$ and $c\in\phi(S)$,
there is some $1\leq i\leq k$ and some implication $A\rightarrow d\in\Sigma$
such that $A\subseteq X_{c}$, $A\subseteq S_{i-1}$, $d\notin X_{c}$ and
$d\notin S_{i-1}$. Consider the least such $i$. By assumption, all
implications used to build sets $S_{0},S_{1},\dots,S_{i-1}$ contained in
$X_{c}$ and hence belong to $\Sigma_{c}$. Thus, they will be used in the
forward chaining on $S$ with $\Sigma_{c}$ too so that $A\subseteq\phi_{c}(S)$
holds. Because $A\rightarrow b\in\Sigma_{c}$ for every $b\in X_{c}\setminus
A$, we deduce that $\phi_{c}(S)=X_{c}$ as expected.

Now assume that $\phi_{c}(S)=X_{c}$. Since $X_{c}$ is not closed by
assumption, $c\in\phi(X_{c})$ holds by definition of $X_{c}$. Again, consider
the forward chaining on $S$ with $\Sigma_{c}$. In order to obtain $X_{c}$, we
have two possibilities:

  1. (1)

an implication $A\rightarrow b$ such that $A\rightarrow d\in\Sigma$ for some
$d\notin X_{c}$ is used. Consider the first such implication encountered in
the forward chaining. Then, all implications used before $A\rightarrow b$
belongs to $\Sigma$. In particular, $A\rightarrow d$ will be used in when
applying forward chaining on $S$ with $\Sigma$, so that $d\in\phi(S)$. Since
$c\in\phi(d)$, we deduce $c\in\phi(S)$.

  2. (2)

every implication used in the forward chaining, if any, is an implication of
$\Sigma$. In this case, $X_{c}\subseteq\phi_{c}(S)$ implies
$X_{c}\subseteq\phi(S)$. This holds in particular if $S=X_{c}$, which covers
the case where $\Sigma_{c}=\emptyset$. Since $X_{c}$ is assumed not to be
closed in $\mathcal{F}$, it contains at least one $D$-generator of $c$. We
deduce $c\in\phi(S)$ as expected.

This concludes the proof that $c\in\phi(S)$ if and only if
$\phi_{c}(S)=X_{c}$. In particular, it holds that $S$ is a minimal generator
of $c$ included in $X_{c}$ if and only if $S$ is a minimal key of
$(X_{c},\mathcal{F}_{c})$. As the binary part of $\Sigma$ involved in
$D$-generators of $c$ is included in $\Sigma_{c}$, it further holds that $S$
is a $D$-generator of $c$ if and only if it is a $D$-minimal key of
$(X_{c},\mathcal{F}_{c})$. ∎

In [EN16], the authors show how to list the $D$-minimal keys of a standard
closure system using solution graph traversal. As a consequence of Lemma 11,
we can adapt their approach to the problem of finding
$\operatorname{gen_{\mathit{D}}}(c)$. In particular, we rephrase in our
framework a key statement that lays the ground for defining a suitable
transition function.

######  Lemma 12.

[EN16, Theorem 8] Let $(X,\Sigma)$ be a standard IB, let $c\in X$ and let
$\mathcal{S}$ be a non-empty subset of $\operatorname{gen_{\mathit{D}}}(c)$.
Then, $\mathcal{S}\neq\operatorname{gen_{\mathit{D}}}(c)$ if and only if there
exists some $A$ in $\mathcal{S}$ and an implication $B\rightarrow
d\in\Sigma_{c}$, $|B|\geq 2$, such that
$\phi_{c}^{b}((\phi_{c}^{b}(A)\setminus\phi_{c}^{b}(d))\cup B)$ does not
contain any set of $\mathcal{S}$.

In words, Lemma 12 states that the set $\mathcal{S}$ is incomplete if and only
if there is a closed set in $\mathcal{F}_{c}^{b}$ which includes an unseen
$D$-generator. Indeed, based on Lemma 8,
$\\{\phi_{c}^{b}(A):A\in\operatorname{gen_{\mathit{D}}}(c)\\}$ defines an
antichain of $(\mathcal{F}_{c}^{b},\subseteq)$. If the antichain
$\\{\phi_{c}^{b}(A):A\in\mathcal{S}\\}$ associated to $\mathcal{S}$ is
incomplete, then there is a closed set $F\in\mathcal{F}_{c}^{b}$ which is in
$\uparrow\\{\phi_{c}^{b}(A):A\in\operatorname{gen_{\mathit{D}}}(c)\\}$ but not
in $\uparrow\\{\phi_{c}^{b}(A):A\in\mathcal{S}\\}$. The lemma further shows
that such a closed set can be identified by substituting elements from the
$\phi_{c}^{b}$-closure of a solution in $\mathcal{S}$ for a premise in
$\Sigma_{c}$. Henceforth, in view of Theorem 10 and according to Lemma 12, we
define the solution graph $\mathcal{G}(c)$ with vertices
$\operatorname{gen_{\mathit{D}}}(c)$ and transition function $\mathcal{N}$
defined by:

$\mathcal{N}(A)=\left\\{\texttt{Min}(\phi_{c}^{b}((\phi_{c}^{b}(A)\setminus\phi_{c}^{b}(d))\cup
B)):B\rightarrow d\in\Sigma_{c},|B|\geq 2\right\\}.$

Here, Min is a greedy algorithm that computes a $D$-generator (of $c$) from
any $\phi_{c}^{b}$-closed generator of $c$. To do so, it greedily removes the
least available extreme point of the current closed set (recall that
$(X_{c},\mathcal{F}_{c}^{b})$ is a convex geometry) according to an ordering
of the vertices of $X_{c}$ such that $a<d$ provided
$\phi_{c}^{b}(a)\subset\phi_{c}^{b}(d)$. When the algorithm reaches a closed
set of $\mathcal{F}_{c}^{b}$ whose extreme points satisfy Lemma 6, it outputs
the corresponding $D$-generator. The whole procedure can be conducted in
polynomial time given $(X,\Sigma)$ and $(X_{c},\Sigma_{c})$.

######  Remark 4.

Since for every $c\in X$, $\Sigma_{c}^{b}\subseteq\Sigma^{b}$, we can use a
same ordering of $X$ which is then applied to each $X_{c}$.

Now, observe that $\mathcal{G}(c)$ is strongly connected. Let $\mathcal{S}$ be
a non-empty subset of $\operatorname{gen_{\mathit{D}}}(c)$. Based on the
definition of $\mathcal{N}$, Lemma 11 states that either
$\mathcal{S}=\operatorname{gen_{\mathit{D}}}(c)$ or $\mathcal{S}$ has an
unseen neighbor w.r.t. $\mathcal{N}$. Henceforth, the process of starting from
$\mathcal{S}=\\{A\\}$ for some $D$-generator $A$ of $c$ and repeatedly
applying Lemma 11 to obtain a new neighbor of $S$ will eventually reach each
generator in $\operatorname{gen_{\mathit{D}}}(c)$. As we can use this strategy
starting from any generator, we deduce that $\mathcal{G}(c)$ is strongly
connected. Moreover, a first $D$-generator can be computed in polynomial time
using Min on $X_{c}$. Finally $\mathcal{N}(A)$ can be generated in polynomial
time. Hence, all the requirements of Theorem 10 are satisfied. Computing
$(X_{c},\Sigma_{c})$ in polynomial time at pre-processing, we obtain:

######  Theorem 13.

Let $(X,\Sigma)$ be an implicational base of a closure system
$(X,\mathcal{F})$ and let $c\in X$. Then, there is a polynomial-delay
algorithm which computes $\operatorname{gen_{\mathit{D}}}(c)$ from
$(X,\Sigma)$.

######  Example 12.

Let $X=\\{1,2,3,4,5,6,7,8\\}$ and consider the IB $(X,\Sigma)$ defined by:

$\Sigma=\left\\{\begin{array}[]{l}4\rightarrow 3,\\\ 3\rightarrow 2,\\\
2\rightarrow 1\end{array}\right\\}\cup\left\\{\begin{array}[]{l
l}15\rightarrow 2,&16\rightarrow 2,\\\ 27\rightarrow 3,&28\rightarrow 3,\\\
36\rightarrow 4,&37\rightarrow 4\end{array}\right\\}$

The corresponding closure system $(X,\mathcal{F})$ is standard. The elements
of $X$ admitting $D$-generators are $2$, $3$ and $4$:

$\displaystyle\operatorname{gen_{\mathit{D}}}(2)=$
$\displaystyle\;\\{15,16\\},$
$\displaystyle\operatorname{gen_{\mathit{D}}}(3)=$
$\displaystyle\;\\{157,158,167,168,27,28\\},$
$\displaystyle\operatorname{gen_{\mathit{D}}}(4)=$
$\displaystyle\;\\{157,167,168,27,36\\}.$

We consider the element $4$. We have $X_{4}=X\setminus\\{4\\}$ and:

$\Sigma_{4}=\left\\{\begin{array}[]{l}3\rightarrow 2,\\\ 2\rightarrow
1\end{array}\right\\}\cup\left\\{\begin{array}[]{l l}15\rightarrow
2,&16\rightarrow 2,\\\ 27\rightarrow 3,&28\rightarrow 3\\\
\end{array}\right\\}\cup\left\\{\begin{array}[]{l l l}36\rightarrow
5,&36\rightarrow 7,&36\rightarrow 8,\\\ 37\rightarrow 5,&37\rightarrow
6,&37\rightarrow 8\end{array}\right\\}.$

The solution graph $\mathcal{G}(4)$ is given in Figure 9. We use the ordering
$1<2<\dots<8$ for the Min procedure. Remark that it complies with
$\phi_{4}^{b}$. For instance, there is a transition from $167$ to $168$, i.e.,
$168\in\mathcal{N}(167)$, given by the implication $28\to 3$ (highlighted in
the figure). We have that $167$ is a $D$-generator of $4$, so that
$\phi_{4}^{b}((\phi_{4}^{b}(167)\setminus\phi_{4}^{b}(3))\cup 28)=12678$ must
contain a $D$-generator of $4$ as $1\in\phi_{4}^{b}(3)$. The Min procedure
will remove $2$ and $7$ in that order. We obtain $168$ as a new $D$-generator
(since $168$ is at the same time a $D$-generator and a closed w.r.t.
$\phi_{4}^{b}$).

Figure 9: On the left, the solution graph $\mathcal{G}(4)$ of Example 12. An
edge without arrows indicate transitions in both directions. On the right, a
table that gives an example of implication that can be used for each
transition. For instance, the implication $28\to 3$ yields a transition from
$167$ to $168$ (highlighted in grey). A cross means that the transition is not
possible. There may be other possible choices of implications, and self-loops
are omitted for simplicity.

We represent the three solution graphs $\mathcal{G}(2),\mathcal{G}(3)$,
$\mathcal{G}(4)$ in Figure 10. We note that the ordering used for $X_{2}$,
$X_{3}$ is similar as the one used for $X_{4}$.

Figure 10: The three solution graphs of Example 12.

We build upon previous discussions to give an algorithm finding all the
$D$-generators of $(X,\Sigma)$ and outputting the corresponding implications
of the $D$-base. We cannot straightforwardly apply Theorem 13 as a same set
$A$ may be a $D$-generator of several distinct elements. This is the case in
Example 12 where we have
$\operatorname{gen_{\mathit{D}}}(3)\cap\operatorname{gen_{\mathit{D}}}(4)=\\{157,167,168,27\\}$.
To avoid repetitions, we consider the solution graph $\mathcal{G}(X)$ with
vertices $\bigcup_{c\in X}\operatorname{gen_{\mathit{D}}}(c)$ and whose
transition function is defined as:

$\mathcal{N}(A)=\bigcup_{\begin{subarray}{c}c\in X,\\\
A\in\operatorname{gen_{\mathit{D}}}(c)\end{subarray}}\left\\{\texttt{Min}(\phi_{c}^{b}((\phi_{c}^{b}(A)\setminus\phi_{c}^{b}(d))\cup
B)):B\rightarrow d\in\Sigma_{c},|B|\geq 2\right\\}$

In other words, $\mathcal{G}(X)=\bigcup_{c\in X}\mathcal{G}(c)$. In Figure 11,
we show the solution graph $\mathcal{G}(X)$ associated with Example 12.

Figure 11: The solution graph $\mathcal{G}(X)$ of Example 12. It the union of
two strongly connected components: one associated to $\mathcal{G}(2)$ (on the
left), and one associated to $\operatorname{gen_{\mathit{D}}}(3)$ and
$\operatorname{gen_{\mathit{D}}}(4)$ (on the right).

Even though $\mathcal{G}$ is not strongly connected, it is an union of
strongly connected components due to Lemma 12. Moreover, we can compute in
polynomial time a $D$-generator for each strongly connected component.
Finally, within each strongly connected component, the transition function can
be computed in polynomial time as it is the union of polynomial-time
computable transition functions. When obtaining a $D$-generator $A$, we output
the implication $A\rightarrow c$ for each $c$ such that
$A\in\operatorname{gen_{\mathit{D}}}(c)$. Using Theorem 10 on each strongly
connected component of $\mathcal{G}$ we finally obtain Theorem
LABEL:thm:D-base-IB:

*

###### Proof.

As a pre-processing step, we compute $(X,\Sigma^{b})$ and $(X_{c},\Sigma_{c})$
for each $c$ such that $\operatorname{gen_{\mathit{D}}}(c)\neq\emptyset$. This
can be done in polynomial time (see Section 2). Then, we apply Theorem 10 on
each strongly connected component of $\mathcal{G}$ one after the other. At the
end of the traversal of a strongly connected component, we have to detect that
there is no component left. On this purpose, it is sufficient to test whether
a $D$-generator have been output for each $c$ such that
$\operatorname{gen_{\mathit{D}}}(c)\neq\emptyset$. If this is the case, the
$D$-base has been found completely. Otherwise, we use $\texttt{Min}(X_{c})$ on
a $c$ whose $D$-generators have not been enumerated to start a new BFS in one
of the remaining components. ∎

We remark that, much as Theorem 13, the algorithm of Theorem LABEL:thm:D-base-
IB may require an exponential amount of space, notably to avoid repetitions.
The question of whether the same time complexity can be achieved with
polynomial space is intriguing. However, answering this question in the
affirmative would at the same time give an algorithm to list all the minimal
keys of a set of functional dependencies with polynomial delay and polynomial
space, a long-standing open question [EN16, LO78].

##  6 Conclusion

In this paper, we have investigated complexity aspects of the $D$-base and
$D$-relation of a closure system. We have shown that computing the
$D$-relation from an IB is $\mathbf{NP}$-complete even in the acyclic setup.
Besides, we gave output sensitive algorithms to compute the $D$-base from both
an IB and meet-irreducible elements. Namely, we gave a polynomial-delay
algorithm to find the $D$-base from an arbitrary IB, and an output-quasi-
polynomial time algorithm for recovering the $D$-base from meet-irreducible
elements. These results answer Questions 1, 2 and 3 and hence complete the
complexity landscape of the $D$-relation and $D$-base. However, the properties
of the $D$-relation could be further studied. Indeed, the fact that lower
bounded closure systems are characterized by an acyclic $D$-relation [FJN95]
suggests that other properties of closure systems may be embedded in the
structure of the $D$-relation. This leads to the following intriguing
question:

######  Question 4.

Is there any further properties of closure systems that can be derived
directly from the $D$-relation?

Another future research direction concerns the $E$-base and the $E$-relation
[AN14, Ada17]. The $E$-base is a further refinement of the $D$-base, and the
$E$-relation is defined in a similar way as the $D$-relation from
$D$-generators. More precisely, a $D$-generator of an element $c$ is an
$E$-generator of $c$ if its closure in the underlying closure system is
minimal among the closures of the other $D$-generators of $c$. This makes the
$E$-base connected with critical circuits of convex geometries [KLS12]. Unlike
the $D$-base though, the $E$-base does not always constitute a valid IB of its
associated closure system. Henceforth, the most intriguing question regarding
the $E$-base is:

######  Question 5.

Which closure systems have valid $E$-base?

Besides, the questions regarding the complexity of finding the $E$-base or the
$E$-relation given an IB or meet-irreducible elements, much as what has been
done for the $D$-base, are left to be answered.

## References

  * [ABLS23] Kira Adaricheva, Jase Bernhardt, Wenxin Liu, and Brianna Schmidt.  Importance of overnight parameters to predict sea breeze on long island, 2023.
  * [Ada91] Kira Adaricheva.  A characterisation of finite lattices of subsemilattices.  Algebra i Logika, 30:385–404, 1991.
  * [Ada17] Kira Adaricheva.  Optimum basis of finite convex geometry.  Discrete Applied Mathematics, 230:11–20, 2017.
  * [AMS+96] Rakesh Agrawal, Heikki Mannila, Ramakrishnan Srikant, Hannu Toivonen, A. Inkeri Verkamo, et al.  Fast discovery of association rules.  Advances in knowledge discovery and data mining, 12(1):307–328, 1996.
  * [AN14] Kira Adaricheva and J. B. Nation.  On implicational bases of closure systems with unique critical sets.  Discrete Applied Mathematics, 162:51–69, 2014.
  * [AN17] Kira Adaricheva and J. B. Nation.  Discovery of the D-basis in binary tables based on hypergraph dualization.  Theoretical Computer Science, 658:307–315, 2017.
  * [ANR13] Kira Adaricheva, J. B. Nation, and Robert Rand.  Ordered direct implicational basis of a finite closure system.  Discrete Applied Mathematics, 161(6):707–723, 2013.
  * [BBM23a] Kristóf Bérczi, Endre Boros, and Kazuhisa Makino.  Hypergraph Horn functions.  arXiv preprint arXiv:2301.05461, 2023.
  * [BBM23b] Kristóf Bérczi, Endre Boros, and Kazuhisa Makino.  Matroid Horn functions.  arXiv preprint arXiv:2301.06642, 2023.
  * [BCH90] Endre Boros, Yves Crama, and Peter L. Hammer.  Polynomial-time inference of all valid implications for Horn and related formulae.  Annals of Mathematics and Artificial Intelligence, 1:21–32, 1990.
  * [BČK98] Endre Boros, Ondřej Čepek, and Alexander Kogan.  Horn minimization by iterative decomposition.  Annals of Mathematics and Artificial Intelligence, 23:321–343, 1998.
  * [BČKK09] Endre Boros, Ondřej Čepek, Alexander Kogan, and Petr Kučera.  A subclass of Horn cnfs optimally compressible in polynomial time.  Annals of mathematics and artificial intelligence, 57:249–291, 2009.
  * [BDVG18] Karell Bertet, Christophe Demko, Jean-François Viaud, and Clément Guérin.  Lattices, closures systems and implication bases: A survey of structural aspects and algorithms.  Theoretical Computer Science, 743:93–109, 2018.
  * [BEG04] Endre Boros, Khaled Elbassioni, and Vladimir Gurvich.  Algorithms for generating minimal blockers of perfect matchings in bipartite graphs and related problems.  In European Symposium on Algorithms, pages 122–133. Springer, 2004.
  * [Bic22] Todd Bichoupan.  Complexity results for implication bases of convex geometries.  arXiv preprint arXiv:2211.08524, 2022.
  * [Bic23] Todd Bichoupan.  Independence of essential sets in finite implication bases.  arXiv preprint arXiv:2304.06837, 2023.
  * [BM10] Karell Bertet and Bernard Monjardet.  The multiple facets of the canonical direct unit implicational basis.  Theoretical Computer Science, 411(22-24):2155–2166, 2010.
  * [Day92a] Alan Day.  Doubling constructions in lattice theory.  Canadian J. of Mathematics, 44:252–269, 1992.
  * [Day92b] Alan Day.  The lattice theory of functional dependencies and normal decompositions.  Int. J. Algebra Comput., 2(4):409–432, 1992.
  * [DF12] Jean-Paul Doignon and Jean-Claude Falmagne.  Knowledge spaces.  Springer Science & Business Media, 2012.
  * [EG95] Thomas Eiter and Georg Gottlob.  Identifying the minimal transversals of a hypergraph and related problems.  SIAM Journal on Computing, 24(6):1278–1304, 1995.
  * [EJ85] Paul H. Edelman and Robert E. Jamison.  The theory of convex geometries.  Geometriae dedicata, 19(3):247–270, 1985.
  * [Elb14] Khaled Elbassioni.  A polynomial delay algorithm for generating connected induced subgraphs of a given cardinality.  arXiv preprint arXiv:1411.2262, 2014.
  * [Elb22] Khaled Elbassioni.  On dualization over distributive lattices.  Discrete Mathematics & Theoretical Computer Science, 24(Discrete Algorithms), 2022.
  * [EMG08] Thomas Eiter, Kazuhisa Makino, and Georg Gottlob.  Computational aspects of monotone dualization: A brief survey.  Discrete Applied Mathematics, 156(11):2035–2049, 2008.
  * [EN16] Karima Ennaoui and Lhouari Nourine.  Polynomial delay hybrid algorithms to enumerate candidate keys for a relation.  In BDA 2016, 2016.
  * [FH81] Ulrich Faigle and Christian Herrmann.  Projective geometry on partially ordered sets.  Transactions of the American Mathematical Society, 266(1):319–332, 1981.
  * [FJN95] Ralph Freese, Jaroslav Ježek, and J. B. Nation.  Free Lattices, volume 42.  American Mathematical Soc., 1995.
  * [FK96] Michael L Fredman and Leonid Khachiyan.  On the complexity of dualization of monotone disjunctive normal forms.  Journal of Algorithms, 21(3):618–628, 1996.
  * [GD86] Jean-Louis Guigues and Vincent Duquenne.  Familles minimales d’implications informatives résultant d’un tableau de données binaires.  Mathématiques et Sciences humaines, 95:5–18, 1986.
  * [Gra11] George. A. Gratzer.  Lattice theory: foundation.  Springer, 2011.
  * [HK95] Peter L. Hammer and Alexander Kogan.  Quasi-acyclic propositional Horn knowledge bases: Optimal compression.  IEEE Transactions on knowledge and data engineering, 7(5):751–762, 1995.
  * [JN75] Bjarni Jónsson and J. B. Nation.  A report on sublattices of a free lattice.  Colloq. Math. Soc. Janos Bolyai, 17:223–257, 1975.
  * [JYP88] David S Johnson, Mihalis Yannakakis, and Christos H Papadimitriou.  On generating all maximal independent sets.  Information Processing Letters, 27(3):119–123, 1988.
  * [KLS12] Bernhard Korte, László Lovász, and Rainer Schrader.  Greedoids, volume 4.  Springer Science & Business Media, 2012.
  * [LO78] Claudio. L. Lucchesi and Sylvia. L. Osborn.  Candidate keys for relations.  Journal of Computer and System Sciences, 17(2):270–279, 1978.
  * [MC97] Bernard Monjardet and Nathalie Caspard.  On a dependence relation in finite lattices.  Discrete Mathematics, 165:497–505, 1997.
  * [MR92] Heikki Mannila and Kari-Jouko Räihä.  The design of relational databases.  Addison-Wesley Longman Publishing Co., Inc., 1992.
  * [NCMS+21] J. B. Nation, Justin Cabot-Miller, Oren Segal, Robert Lucito, and Kira Adaricheva.  Combining algorithms to find signatures that predict risk in early stage stomach cancer.  Journal of Computational Biology, 28(310):985–1006, 2021.
  * [NV23] Lhouari Nourine and Simon Vilmin.  Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements.  Theoretical Computer Science, page 114030, 2023.
  * [RLAC+15] Estrella Rodrıguez-Lorenzo, Kira Adaricheva, Pablo Cordero, Manuel Enciso, and Angel Mora.  From an implicational system to its corresponding d-basis.  CLA 2015, page 217, 2015.
  * [RLAC+17] Estrella Rodríguez-Lorenzo, Kira Adaricheva, Pablo Cordero, Manuel Enciso, and Angel Mora.  Formation of the d-basis from implicational systems using simplification logic.  International Journal of General Systems, 46(5):547–568, 2017.
  * [Str19] Yann Strozecki.  Enumeration complexity.  Bulletin of EATCS, 3(129), 2019.
  * [Wil94] Marcel Wild.  A theory of finite closure spaces based on implications.  Advances in Mathematics, 108(1):118–139, 1994.
  * [Wil17] Marcel Wild.  The joy of implications, aka pure Horn formulas: mainly a survey.  Theoretical Computer Science, 658:264–292, 2017.

##  Appendix A Proof of Theorem LABEL:thm:D-relation-ACG

In this section, we give the complete proof of Theorem LABEL:thm:D-relation-
ACG which we first restate.

*

We showed in Corollary 2 that the problem belongs to $\mathbf{NP}$. To show
$\mathbf{NP}$-hardness, we use a reduction from the problem $1$-in-$3$-SAT:

1-in-3 SAT
---
Input: |  A positive $3$-CNF $\varphi=\\{C_{1},\dots,C_{m}\\}$ over variables $V=\\{v_{1},\dots,v_{n}\\}$.
Question: |  Is there a truth assignment of the variables in $V$ which is a model of $\varphi$ and such that each clause of $\varphi$ has exactly one true literal?

Let $\varphi=\\{C_{1},\dots,C_{m}\\}$ be a non-trivial positive $3$-CNF over
$V=\\{v_{1},\dots,v_{n}\\}$. For simplicity, we view clauses as sets of
variables. Moreover, we identify an assignment of $V$ to the sets of its
variables assigned 1. Consequently, a 1-in-3 assignment of $V$ is a set of
variables $T\subset V$ such that $|C_{i}\cap T|=1$ for each clause $C_{i}$ of
$\varphi$. Two variables $v_{i},v_{j}$ are in conflict if there exists a
clause $C_{k}$ in $\varphi$ that contains both $v_{i}$ and $v_{j}$. For each
$1\leq i\leq m$, we define $\varphi_{i}=\\{C_{i},\dots,C_{m}\\}$. A subset $T$
of $V$ is $\varphi$-conflict-free (resp. $\varphi_{i}$-conflict-free) if it
does not contain variables in conflict among the clauses of $\varphi$ (resp.
$\varphi_{i}$).

We build an instance of $D$-relation identification. Let
$C=\\{c_{1},\dots,c_{m},c_{m+1}\\}$ and let $X=C\cup V$. An element $c_{i}$,
$1\leq i\leq m$ represents the clause $C_{i}$. The element $c_{m+1}$ is
another gadget element. Now consider the set
$\Sigma=\Sigma_{mod}\cup\Sigma_{conf}$ of implications, where:

$\displaystyle\Sigma_{\mathit{mod}}$ $\displaystyle=\\{c_{i}v_{j}\rightarrow
c_{i+1}:1\leq i\leq m\text{ and }v_{j}\in C_{i}\\}$
$\displaystyle\Sigma_{\mathit{conf}}$ $\displaystyle=\\{v_{i}v_{j}\rightarrow
c_{m+1}:v_{i},v_{j}\in V\text{ and }v_{i},v_{j}\text{ are in conflict in
}\varphi\\}$

Informally, $\Sigma_{mod}$ models the fact that whenever the $i$-th clause is
satisfied, we can proceed to the $(i+1)$-th clause or $c_{m+1}$, and
$\Sigma_{conf}$ represents the conflicts induced by the variables appearing
together in a clause.

We take $(X,\Sigma)$ as input to our problem, together with $c_{1}$ and
$c_{m+1}$. Note that $(X,\Sigma)$ can be constructed in polynomial time in the
size of $\varphi$ and $V$. The premises of $\Sigma$ have size $2$ and
$G(\Sigma)$ has no cycle. Hence, $(X,\mathcal{F})$ is an acyclic closure
system represented by an IB with premises of size at most $2$ as required.

We argue that $c_{1}$ belongs to a $D$-generator of $c_{m+1}$ if and only if
there exists a 1-in-3 assignment $T$ of $\varphi$. As a preliminary
observation, note that $\Sigma$ has no binary implications. Hence,
$\operatorname{gen}(c_{m+1})=\operatorname{gen}_{D}(c_{m+1})$ and we can
restrict our analysis to minimal generators of $c_{m+1}$ only. Remark that by
definition of $\Sigma$, $\operatorname{gen}(c_{m+1})\neq\emptyset$ and for
every $A\in\operatorname{gen}(c_{m+1})$, $|A|\geq 2$. We start our analysis
with a useful proposition.

######  Proposition 4.

For any $A\subseteq X$ such that $A\setminus C$ is $\varphi$-conflict-free and
any $1<i\leq m+1$, $c_{i}\in\phi(A)$ if and only if $c_{i}\in A$ or
$c_{i-1}\in\phi(A)$ and $C_{i-1}\cap A\neq\emptyset$.

###### Proof.

The if part follows from the definition of $\Sigma$. We prove the only if
part. Assume that $c_{i}\in\phi(A)$ but $c_{i}\notin A$. Then, in the forward
chaining $A=A_{0},\dots,A_{k}=\phi(A)$ applied on $A$ with $\Sigma$, there
will be some $A_{j}$ and some implication $B\rightarrow c_{i}$ such that
$B\subseteq A_{j}$ and $c_{i}\notin A_{j}$, so that $c_{i}\in A_{j+1}$. Since
$A\setminus C$ is $\varphi$-conflict-free, $B\rightarrow c_{i}$ must be of the
form $c_{i-1}v_{j}\rightarrow c_{i}$ for some $v_{j}\in C_{i-1}$. As
$B\subseteq A_{j}\subseteq\phi(A)$, we obtain $c_{i-1},v_{j}\in\phi(A)$. It
remains to show that $v_{j}\in A$ so that $A\cap C_{i-1}\neq\emptyset$. But
this follows from the fact that no implication has $v_{j}$ as a conclusion.
Thus, $c_{i-1}\in\phi(A)$ and $C_{i-1}\cap A\neq\emptyset$. This concludes the
proof. ∎

Next, we characterize the minimal generators of $c_{m+1}$.

######  Proposition 5.

The following equality holds:

$\displaystyle\operatorname{gen}(c_{m+1})=$
$\displaystyle\\{\\{v_{i},v_{j}\\}:v_{i},v_{j}\in V\text{ are in conflict in
}\varphi\\}\cup$
$\displaystyle\min_{\subseteq}\\{T_{i}\cup\\{c_{i}\\}:T_{i}\subseteq V\text{
is a $\varphi$-conflict-free 1-in-3 assignment of }\varphi_{i}\\}$

###### Proof.

We show double-inclusion. We begin with the $\supseteq$ part. The fact that
each pair $\\{v_{i},v_{j}\\}$ of variables in conflict is a minimal generator
of $c_{m+1}$ follows from the definition of $\Sigma$. Let $T_{i}\subseteq V$
be a $\varphi$-conflict-free 1-in-3 assignment of $\varphi_{i}$, if it exists,
and put $A=T_{i}\cup\\{c_{i}\\}$. By assumption, $C_{j}\cap A\neq\emptyset$
for every $i\leq j\leq m$. Furthermore, $c_{i}\in A$. Hence using Proposition
4 inductively on $i<j\leq m+1$, we deduce that $c_{m+1}\in\phi(A)$ holds as
required. Now we show that no proper subset $A^{\prime}$ of $A$ satisfies
$c_{m+1}\in\phi(A^{\prime})$. Consider first
$A^{\prime}=A\setminus\\{c_{i}\\}=T_{i}$. By assumption, $T_{i}$ is
$\varphi$-conflict-free. Hence, $T_{i}$ contains no premise of $\Sigma$ so
that $\phi(T_{i})=T_{i}$ and $c_{m+1}\notin T_{i}=A^{\prime}$. Let
$A^{\prime}=A\setminus\\{v_{j}\\}$ for some $v_{j}\in T_{i}$. Since $T_{i}$ is
an inclusion-wise minimal 1-in-3 assignment of $\varphi_{i}$, there exists a
clause $C_{k}$ such that $C_{k}\cap A=\\{v_{j}\\}$ so that $C_{k}\cap
A^{\prime}=\emptyset$, with $k\geq i$. Again using Proposition 4 inductively
on $k<\ell\leq m+1$, we deduce that $c_{m+1}\notin\phi(A^{\prime})$. This
concludes the proof that $A\in\operatorname{gen}(c_{m+1})$.

We proceed to the $\subseteq$ part. Let $A$ be a minimal generator of
$c_{m+1}$. We have two cases: $A\cap C=\emptyset$ and $A\cap C\neq\emptyset$.
In the first case, $c_{m+1}\in\phi(A)$ implies that $A$ is not closed. Hence,
there exists an implication $B\rightarrow d\in\Sigma$ such that $B\subseteq
A\subseteq V$. As $A$ is a minimal generator of $c_{m+1}$ by assumption, we
deduce $A=\\{v_{i},v_{j}\\}$ as expected.

Now we consider the case $A\cap C\neq\emptyset$. Since $A$ is a minimal
generator of $c_{m+1}$, $A\setminus C$ is $\varphi$-conflict-free. Let $i$ be
the maximal index in $1\leq i\leq m$ such that $c_{i}\in A$. Since $A\setminus
C$ is $\varphi$-conflict-free, $c_{m+1}\in\phi(A)$ implies $c_{m}\in\phi(A)$
and $C_{m}\cap A\neq\emptyset$ by definition of $\Sigma$ and Proposition 4.
Using Proposition 4 inductively for $j$ ranging from $m+1$ to $i+1$, we deduce
that $A\cap C_{k}\neq\emptyset$ for every $i\leq k\leq m$, so that $A\setminus
C$ is a $\varphi$-conflict-free 1-in-3 assignment of $\varphi_{i}$. Using
$\subseteq$ part, we further deduce that $T_{i}=A\setminus C$ is inclusion-
wise minimal for this property. Hence, $A$ is of the form
$T_{i}\cup\\{c_{i}\\}$ as required, which concludes the proof. ∎

We are in position to conclude that $\varphi$ has a valid $1$-in-$3$
assignment if and only if there exists a minimal generator of $c_{m+1}$
containing $c_{1}$. Assume that $\varphi$ has a valid $1$-in-$3$ assignment
$T$. Then, by Proposition 5, $T\cup\\{c_{1}\\}$ belongs to
$\operatorname{gen}(c_{m+1})$ and $c_{m+1}\delta c_{1}$ holds. Conversely, if
there exists a minimal generator $A$ of $c_{m+1}$ containing $c_{1}$, then by
Proposition 5, $A\setminus\\{c_{1}\\}$ is a $1$-in-$3$ assignment of
$\\{C_{1},\dots,C_{m}\\}=\varphi$. This concludes the proof of the theorem.

##  Appendix B Proof of Theorem LABEL:thm:D-relation-LB

We proceed to the proof of Theorem LABEL:thm:D-relation-LB which we first
recall.

*

We showed in Corollary 2 that $D$-relation identification belongs to
$\mathbf{NP}$. To show $\mathbf{NP}$-hardness, we use another reduction from
$1$-in-$3$ SAT. Let $\varphi=\\{C_{1},\dots,C_{m}\\}$ be a positive $3$-CNF
over variables $V=\\{v_{1},\dots,v_{n}\\}$. Let $C=\\{c_{1},\dots,c_{m}\\}$.
We use the same terminology as in Theorem LABEL:thm:D-relation-ACG. Let
$X=V\cup C\cup\\{a,b\\}$ be a new groundset, and let
$\Sigma=\Sigma_{\mathit{mod}}\cup\Sigma_{\mathit{conf}}\cup\Sigma^{b}$ where:

$\displaystyle\Sigma_{\mathit{mod}}$ $\displaystyle=\\{av_{i}\rightarrow
c_{j}:v_{i}\in C_{j}\\}\cup\\{C\rightarrow b\\}$
$\displaystyle\Sigma_{\mathit{conf}}$ $\displaystyle=\\{v_{i}v_{j}\rightarrow
b:v_{i},v_{j}\in V\text{ and }v_{i},v_{j}\text{ are in conflict in
}\varphi\\}$ $\displaystyle\Sigma^{b}$ $\displaystyle=\\{c_{i}\rightarrow
a:c_{i}\in C\\}$

Informally, $\Sigma_{\mathit{conf}}$ models all the conflicts in between two
variables appearing in a clause and $\Sigma_{\mathit{mod}}$ models the fact
that taking one element in a clause together with $a$ for all the clauses
yields a $1$-in-$3$ assignment of $\varphi$. The binary implications
$\Sigma^{b}$ guarantee that $a$ will never appear in any minimal generator
together with one of the $c_{i}$’s. Finally, let $(X,\mathcal{F})$ be the
closure system associated to $\Sigma$. We call $\phi$ the corresponding
closure operator. The reduction can be conducted in polynomial time.

First, we show in the subsequent statement that the closure system
$(X,\mathcal{F})$ associated to $(X,\Sigma)$ is standard and without
$D$-cycles.

######  Proposition 6.

The closure system $(X,\mathcal{F})$ is standard and without $D$-cycles.

###### Proof.

Recall that a closure system $(X,\mathcal{F})$ over is standard if and only if
$\phi(e)\setminus\\{e\\}\in\mathcal{F}$ for each $e\in X$. For each $e\in
X\setminus C$, we have $\phi(e)=\\{e\\}$ and
$\phi(e)\setminus\\{e\\}=\emptyset\in\mathcal{F}$ by definition of $\Sigma$.
For each $c_{i}\in C$, $\phi(c_{i})=\\{c_{i},a\\}$. Since $\phi(a)=\\{a\\}$,
$\phi(c_{i})\setminus\\{c_{i}\\}\in\mathcal{F}$ follows. We conclude that
$\mathcal{F}$ is standard.

We demonstrate that the $D$-relation has no cycles. For $e\in X$, we denote by
$D(e)$ the elements $f$ of $X$ such that $eDf$. These elements are the
$D$-neighbors of $e$. We have the following properties:

  1. 1.

For every $e\in X\setminus\\{b\\}$, $b\notin D(e)$. Let $A\subseteq X$ and
assume that $b\in A$, $e\notin A$ and $e\in\phi(A)$. Then, there is a sequence
of implications in $\Sigma$ used in the forward chaining applied to $A$ in
$\Sigma$ that allows to derive $e$. However, $b$ belongs to no premise of
$\Sigma$. Hence $e\in\phi(A\setminus\\{b\\})$. We deduce that $b$ belongs to
no minimal generator of $e$, and that $b\notin D(e)$.

  2. 2.

$D(a)=\emptyset$ and $D(v_{j})=\emptyset$ for every $v_{j}\in V$. Let
$v_{j}\in V$. By definition of $\Sigma$, no implication has $v_{j}$ has a
conclusion. Hence $X\setminus\\{v_{j}\\}$ is closed, so that
$\operatorname{gen}(v_{j})=\emptyset$ and $D(v_{j})=\emptyset$. Now consider
$a$. Again by definition of $\Sigma$, $X\setminus(C\cup\\{a\\})$ is closed.
Hence, any minimal generator of $a$ must intersect $C$. However, for every
$c_{j}\in C$, we have $c_{j}\rightarrow a\in\Sigma$ due to $\Sigma^{b}$. We
conclude that $\operatorname{gen}(a)=C$ and hence $D(a)=\emptyset$.

  3. 3.

For every $c_{j}\in C$, $D(c_{j})\subseteq X\setminus C$. Assume for
contradiction there exists $c_{j}\in C$ such that $D(c_{j})\cap
C\neq\emptyset$. In order to derive $c_{j}$ from $A$ in $\Sigma$, the forward
chaining procedure must use an implication of the form $av_{i}\rightarrow
c_{j}$ where $v_{i}\in C_{j}$, that is $a,v_{i}\in\phi(A)$. Since no
implication of $\Sigma$ has $v_{i}$ as a conclusion, we also have $v_{i}\in
A$. Now, let $c_{k}\in A\cap C$. Such a $c_{k}$ exists by assumption. We have
$\\{a\\}=\phi^{b}(a)\subset\phi^{b}(c_{k})\subseteq\phi^{b}(A)$. Since
$\phi^{b}(v_{i})=\\{v_{i}\\}$, we obtain
$\phi^{b}(\\{a,v_{i}\\})\subset\phi^{b}(A)$. However,
$c_{j}\in\phi^{b}(\\{a,v_{i}\\})$. This contradicts $A$ being a $D$-generator
of $c_{j}$. We deduce that $D(c_{j})\subseteq X\setminus C$ for all $c_{j}\in
C$.

Using items 1. and 2., we deduce that no cycle in the $D$-relation can pass
through any elements of $V\cup\\{a,b\\}$. In other words, any $D$-cycle, if
any, must be included in $C$. However, by item 3., for every $c_{j}\in C$,
$D(C_{j})\cap C=\emptyset$ so that no $D$-cycle can contain $2$ adjacent
elements of $C$. We must conclude that the $D$-relation has no cycle as
required. ∎

It remains to show that $bDa$ holds if and only if $\varphi$ admits a valid
1-in-3 assignment. Recall that $bDa$ holds exactly if there exists a
$D$-generator $A$ of $b$ such that $a\in A$. Since $c_{j}\rightarrow
a\in\Sigma$ for each $c_{j}\in C$, it follows that if such a $A$ exists, it
satisfies $A\subseteq V\cup\\{a\\}$. Moreover, $\phi(d)=\phi^{b}(d)=\\{d\\}$
for each $d\in V\cup\\{a\\}$. Henceforth, any minimal generator of $b$
included in $V\cup\\{a\\}$ is already $\phi^{b}$-minimal and hence a
$D$-generator of $b$. Thus, $bDa$ is equivalent to $a$ belonging to a minimal
generator of $b$.

We prove the if part of the statement. Assume that $bDa$ holds. We show that
$\varphi$ has a valid 1-in-3 assignment $T$. Following previous discussion,
let $A$ be a minimal generator of $b$ with $a\in A$ and let $T=A\cap V$.
Because $A$ contains $a$ and $A$ is a minimal generator of $a$,
$b\notin\phi(A\setminus\\{a\\})$. By construction of $\Sigma_{\mathit{conf}}$
we deduce that $T$ is $\varphi$-conflict-free. Thus, for every
$C_{i}\in\varphi$, $|T\cap C_{i}|\leq 1$. On the other hand, $b\in\phi(A)$.
Since $\phi(A)\cap V=A\cap V=T$, we deduce that in $\Sigma$, $b$ is derived
from $A$ with the implication $C\rightarrow b$. Again using $\Sigma$ and the
fact that $A\subseteq V\cup\\{a\\}$, we deduce that $T$ must contain at least
one variable for each clause $C_{i}$ of $\varphi$. Consequently, $|T\cap
C_{i}|=1$ holds for each $C_{i}\in\varphi$, and $T$ is a valid 1-in-3
assignment of $\varphi$.

We move to the only if part. Let $T$ be an inclusion-wise minimal valid 1-in-3
assignment of $\varphi$. We show that $T\cup\\{a\\}$ is a minimal generator of
$b$. Since $T$ contains one variable for each clause $C_{j}$ in $\varphi$,
$c_{j}\in\phi(T\cup\\{a\\})$ holds for every $c_{j}\in C$ by definition of
$\Sigma$. Since $C\rightarrow b\in\Sigma$, we have $b\in\phi(T\cup\\{a\\})$.
We show that no proper subset $T^{\prime}$ of $T\cup\\{a\\}$ implies $b$. If
$T^{\prime}=T\setminus\\{a\\}$, then $\phi(T^{\prime})=T^{\prime}=T$ as $T$ is
$\varphi$-conflict-free. Let $T^{\prime}=T\cup\\{a\\}\setminus\\{v_{i}\\}$ for
some $v_{i}\in T$. Since $T$ is inclusion-wise minimal, there exists
$C_{j}\in\varphi$ such that $T\cap C_{j}=\\{v_{j}\\}$. Thus, $T^{\prime}\cap
C_{j}=\emptyset$. It follows that $c_{i}\notin\phi(T^{\prime})$. As $T$ is
$\varphi$-conflict-free, it contains no premise of $\Sigma_{\mathit{conf}}$.
We deduce that $b\notin\phi(T^{\prime})$. Applying this reasoning to each
$v_{j}\in T\cap V$, we conclude that that $T\cup\\{a\\}$ is a minimal
generator of $b$. By previous discussion, we obtain $bDa$. This concludes the
proof of the theorem.

##  Appendix C Proof of Proposition LABEL:prop:D-base-dual-DB

In this section we prove Proposition LABEL:prop:D-base-dual-DB which we first
restate.

*

###### Proof.

We first show that $\Sigma^{\prime b}=\Sigma^{b}\cup\\{a\rightarrow
d:B\subseteq\phi(a)\text{ for some }B\in\mathcal{B}^{-}\\}$ holds. We begin
with the $\supseteq$ part. Let $a\rightarrow b$ be an implication of
$\Sigma^{b}$. By definition of $\Sigma^{b}$, we have $a\neq b$ and
$b\in\phi(a)$. According to the construction of $\phi^{\prime}$, we deduce
$b\in\phi^{\prime}(a)$ so $\Sigma^{b}\subseteq\Sigma^{\prime b}$. Let $a\in X$
such that $B\subseteq\phi(a)$ for some $B\in\mathcal{B}^{-}$. By definition,
$\phi(a)\subseteq\phi^{\prime}(a)\nsubseteq B$ for every
$B\in\mathcal{B}^{+}$. Hence, by construction of $\mathcal{F}^{\prime}$, we
deduce that $d\in\phi^{\prime}(a)$ and $a\rightarrow d\in\Sigma^{\prime b}$
which proves the $\supseteq$ part of the equality. We turn to the $\subseteq$
part. Let $a\rightarrow b$ be an implication of $\Sigma^{\prime b}$, i.e., an
implication derived from $b\in\phi^{\prime}(a)$ and $a\neq b$. We have two
possible cases, $b=d$ or $b\neq d$. Assume first that $b=d$. By definition of
$\phi^{\prime}$, and since $\mathcal{B}^{-}$, $\mathcal{B}^{+}$ are dual in
$(\mathcal{F},\subseteq)$, $d\in\phi^{\prime}(a)$ implies that
$B\subseteq\phi(a)$ for some $B\in\mathcal{B}^{-}$. Thus, $a\rightarrow
b\in\\{a\rightarrow d:B\subseteq\phi(a)\text{ for some
}B\in\mathcal{B}^{-}\\}$. Remark that this holds in particular for the
elements $a$ such that $\phi(a)\in\mathcal{B}^{-}$. Now, suppose that $b\neq
d$. We show that $a\rightarrow b\in\Sigma^{b}$. We have $b\in\phi^{\prime}(a)$
by assumption. By definition of $\phi^{\prime}$, we also have
$\phi(a)=\phi^{\prime}(a)\setminus\\{d\\}$ and $b\in\phi(a)$ holds as $b\neq
d$. Hence, $a\rightarrow b\in\Sigma^{b}$. We deduce that $\Sigma^{\prime
b}=\Sigma^{b}\cup\\{a\rightarrow d:B\subseteq\phi(a)\text{ for some
}B\in\mathcal{B}^{-}\\}$ is true as required.

It remains to prove that the non-binary part of $\Sigma^{\prime}_{D}$ is
$\\{K^{\prime}_{B}\rightarrow d:B\in\mathcal{B}^{-},|K^{\prime}_{B}|\geq
2\\}$. We first show that $d$ is the unique element of $X^{\prime}$ having
$D$-generators. Let $c\in X$ (so that $c\neq d$) and let $A$ be a non-trivial
minimal generator of $c$ in $(X^{\prime},\mathcal{F}^{\prime})$. Again using
the construction of $\phi^{\prime}$, we have
$\phi^{b}(A)=\phi(A)=\phi^{\prime}(A)\setminus\\{d\\}$ so that $A$ is a non-
trivial minimal generator of $c$ in $(X,\mathcal{F})$. Since $(X,\mathcal{F})$
is distributive, we deduce that $A$ must be a singleton. In particular, $c$
cannot have $D$-generators in $(X^{\prime},\mathcal{F}^{\prime})$ unless
$c=d$.

We proceed to the analysis of $D$-generators of $d$. We prove that for every
$B\in\mathcal{B}^{-}$, the unique minimal minimal spanning set
$K^{\prime}_{B}$ of $\phi^{\prime}(B)$ obtained from Proposition 1 is a
$D$-generator of $d$ provided $|K^{\prime}_{B}|\geq 2$. Note that if
$|K^{\prime}_{B}|<2$, then $K^{\prime}_{B}$ is a singleton since
$(X^{\prime},\mathcal{F}^{\prime})$ is standard, and hence there is an
implication of the form $K^{\prime}_{B}\rightarrow d$ in $\Sigma^{\prime
b}\subseteq\Sigma^{\prime}_{D}$. Let us assume $|K^{\prime}_{B}|\geq 2$.
First, we show that $K^{\prime}_{B}$ is a minimal generator of $d$. We have
$\phi^{\prime}(K^{\prime}_{B})=B\cup\\{d\\}$ where $B\in\mathcal{B}^{-}$.
Hence, for every $K\subset K^{\prime}_{B}$, $d\notin\phi^{\prime}(K)=\phi(K)$
by construction of $\phi^{\prime}$. Thus, $K^{\prime}_{B}$ is a minimal
generator of $d$. We prove that it is now a $D$-generator, i.e., that for
every $K\subseteq X$ such that $\phi^{\prime b}(K)\subset\phi^{\prime
b}(K^{\prime}_{B})$, $d\notin\phi^{\prime}(K)$. Hence, let $K\subseteq X$ be
such that $\phi^{\prime b}(K)\subset\phi^{\prime b}(K^{\prime}_{B})$. We have
$\phi^{\prime b}(K)=\phi(K)\subset\phi^{\prime
b}(K^{\prime}_{B})=\phi(K^{\prime}_{B})=B$. In particular, $\phi^{\prime
b}(K)\in\downarrow\mathcal{B}^{+}$ in $(\mathcal{F},\subseteq)$. Hence,
$\phi^{\prime}(K)=\phi(K)$ so that $d\notin\phi^{\prime}(K)$. We deduce that
$K^{\prime}_{B}$ is a $D$-generator of $d$ in
$(X^{\prime},\mathcal{F}^{\prime})$ as expected. Consequently,
$\\{K^{\prime}_{B}\rightarrow d:B\in\mathcal{B}^{-},|K^{\prime}_{B}|\geq
2\\}\subseteq\Sigma^{\prime}_{D}$ holds.

It remains to show that each $D$-generator of $A$ is the minimal spanning set
$K^{\prime}_{B}$ of some $B\in\mathcal{B}^{-}$, with $|K^{\prime}_{B}|\geq 2$.
The fact that $|A|\geq 2$ follows from the definition of $D$-generators. Since
$d\in\phi^{\prime}(A)$ and $d\notin A$, we deduce by construction of
$\phi^{\prime}$ that there exists $B\in\mathcal{B}^{+}$ such that
$B\subseteq\phi(A)\subseteq\phi^{\prime b}(A)\subseteq\phi^{\prime}(A)$. In
particular, $K^{\prime}_{B}\subseteq\phi^{\prime b}(A)$ so that $\phi^{\prime
b}(K^{\prime}_{B})\subseteq\phi^{\prime b}(A)$. Since both $A$ and
$K^{\prime}_{B}$ are $D$-generators of $d$ by assumption and previous
discussion, we deduce that $A=K^{\prime}_{B}$ must hold. As a consequence,
$\\{K^{\prime}_{B}\rightarrow d:B\in\mathcal{B}^{-},|K^{\prime}_{B}|\geq 2\\}$
precisely captures the $D$-generators of $d$ in
$(X^{\prime},\mathcal{F}^{\prime})$. This shows that the $D$-base is complete,
and concludes the proof. ∎