=Paper=
{{Paper
|id=None
|storemode=property
|title=Depth-first Search for Pseudo-intents through Minimal Transversals
|pdfUrl=https://ceur-ws.org/Vol-1434/paper1.pdf
|volume=Vol-1434
|dblpUrl=https://dblp.org/rec/conf/icfca/Bazin15
}}
==Depth-first Search for Pseudo-intents through Minimal Transversals ==
https://ceur-ws.org/Vol-1434/paper1.pdf
Depth-first Search for Pseudo-intents through
Minimal Transversals
Alexandre Bazin
contact@alexandrebazin.com
Abstract. The enumeration of pseudo-intents is a long-standing prob-
lem in which the order plays a major role. In this paper, we present new
algorithms that enumerate pseudo-intents in orders that do not necessar-
ily respect the inclusion relation. We show that, confirming established
results, this enumeration is equivalent to computing minimal transversals
in hypergraphs a bounded number of times.
1 Introduction
Formal concept analysis, as a field of applied mathematics, is interested in the
patterns that can be found in data taking the form of a set of objects described
by attributes. Among these patterns are the implications, relations between at-
tribute sets A and B representing the fact that every object described by A is
also described by B. As often with this type of relation, interest revolves around
a small, non redundant set of implications. Such a set, the Duquenne-Guigues
basis, is constructed using the notion of pseudo-intent. Indeed, computing the
Duquenne-Guigues basis, and thus all the implications in a data set, is equiva-
lent to enumerating all the pseudo-intents. In [15], it is shown that the number
of pseudo-intents can be exponential in the number of attributes. It has been
proven in [6, 2] that pseudo-intents cannot be enumerated with a polynomial
delay in lectic or reverse lectic order. However, to the best of our knowledge,
no such result exists for other orders. The best-known algorithm, Next Closure
[11], enumerates only in the lectic order. In a previous work [4], we proposed an
exponential delay algorithm to enumerate in any order that extends the inclu-
sion order. In order to continue the study of the influence of the order on the
complexity of this enumeration problem, we propose here two new algorithms
that, together, can enumerate pseudo-intents without respecting the inclusion.
Our algorithms enumerate pseudo-intents incrementally, i.e. given a formal
context and a set of previously found implications, they return a new pseudo-
intent. In order to do this, we define new conditions under which a pseudo-intent
P can be recognized using the lower covers of P in the lattice of attribute sets
closed under the implications already found. This allows us to build algorithms
that, instead of starting from ∅ and adding attributes to construct sets, start
from > and remove attributes, resulting in a depth-first search in the lattice.
We show that both constructing and recognizing a pseudo-intent can be done
c 2015 for the individual papers by the papers’ authors. Copying permitted for private
and academic purposes. This volume is published and copyrighted by its editors.
Local Proceedings also appeared in ISBN 978-84-606-7410-8, Universidad de Málaga
(Dept. Matemática Aplicada), Spain.
2 Alexandre Bazin
by computing a bounded number of times the minimal transversals of some
hypergraph, which makes it easy to bound the delay and isolate special, easier
cases. This result establishes a link with the proof in [6] that enumerating pseudo-
intents without order is at least as hard as computing minimal transversals.
We start by recalling in Section 2 the basic definitions of FCA and results
on the enumeration of pseudo-intents and minimal transversals. In Section 3, we
present the definition of a recognizable pseudo-intent that we use along with the
properties needed for our algorithms. Finally, Sections 4 and 5 are dedicated to
the two algorithms, an example and a brief study of their delay.
2 Preliminaries
2.1 Basics
In formal concept analysis, data takes the form of a formal context. A formal
context is a triple C = (O, A, R) in which O is a set of objects, A is a set of
attributes and R ⊆ O × A a relation that maps attributes to objects. An object
o ∈ O is said to be described by an attribute a ∈ A if (o, a) ∈ R. Together with
the context, there are two ·0 operators defined as
·0 : 2O 7→ 2A
O0 = {a ∈ A | ∀o ∈ O, (o, a) ∈ R}
·0 : 2A 7→ 2O
A0 = {o ∈ O | ∀a ∈ A, (o, a) ∈ R}
Their composition ·00 is a closure operator. A set of attributes A = A00 closed
under ·00 is called an intent.
2.2 Implications
An implication is a relation between two attribute sets A and B, noted A → B.
It is said to hold in the context if and only if A0 ⊆ B 0 or, in other words, if and
only if every object described by A is also described by B. A set I of implications
is a basis if and only if every implication that holds in the context can be derived
from I using Armstrong’s rules :
B⊆A A→B A → B, B → C
, ,
A→B A∪C →B∪C A→C
A pseudo-intent (or pseudo-closed set) P is a set of attributes that contains
the closure of all its subsets and is not an intent. The set B = {P → P 00 | P
Depth-first Search for Pseudo-intents through Minimal Transversals 3
Fig. 1. A formal context
is a pseudo-intent} is the implication basis with the minimum cardinality and
is called the Duquenne-Guigues basis [12]. As such, computing the Duquenne-
Guigues basis, and thus all the implications, is enumerating all the pseudo-
intents. As one of the great problems in FCA, it has been abundantly studied
[12, 15, 6, 17, 4, 3, 16, 1, 19]. As the number of pseudo-intents can be exponential
in the size of the context, preventing a polynomial algorithm, the attention is
instead focused on the delay, i.e. the time between two pseudo-intents and the
last pseudo-intent and the end of the algorithm. It has been shown that pseudo-
intents cannot be enumerated with a polynomial delay in lectic [6] or reverse
lectic order [2]. For the enumeration without order, it is shown in [6] that it is at
least as hard as computing the minimal transversals of a hypergraph. However,
the upper bound is not yet known. The problem of recognizing a pseudo-intent
has been studied in [1] and found to be coNP-complete.
2.3 Logical Closures
A set of implications I gives rises to a logical closure operator I(·) defined as
A+ = A ∪ {C | B → C ∈ I and B ⊆ A}
I(A) = A++...+ (up to saturation)
Similarly, we have the logical pseudo-closure operator I − (·) defined as
A◦ = A ∪ {C | B → C ∈ I and B ⊂ A}
I − (A) = A◦◦...◦ (up to saturation)
It is known that intents are closed under both B − (·) and B(·), whereas a
pseudo-intent P is closed under B − (·) and I(·) for I ⊆ B \ {P → P 00 }.
An attribute set Y is said to be a generator of an attribute set X under
I(·) (resp. I − (·)) if I(Y ) = X (resp. I − (Y ) = X). It is a minimal generator
4 Alexandre Bazin
Fig. 2. ΦI with I = {de → bde, be → bde}
if there is no generator Z of X such that Z ⊂ Y . We will use GenI (X) to
denote the set of all minimal generators of a set X under I(·). The complexity
of computing the minimal generators of a set has been studied in [14]. The
number of minimal generators can be exponential in the number of attributes
and they can be enumerated with an incremental polynomial delay.
We shall use ΦI to denote the lattice of attribute sets closed under I(·)
ordered by the inclusion relation. For an attribute set A, the set of pseudo-
intents P in I such that P ⊆ A and P 00 6⊆ A will be denoted by PI (A).
2.4 Minimal Transversals
The problem of computing minimal transversals in hypergraphs or, equivalently,
the prime conjunctive normal form of the dual of a Boolean function (otherwise
called monotone dualization), have been largely studied in the literature [13, 10,
8, 9, 7].
Given a hypergraph H = (E, V) where E is a set of edges and V ⊆ 2E is a set
of vertices, a transversal T ⊆ E is a set of edges such that ∀V ∈ V, T ∩ V 6= ∅. A
transversal is minimal if none of its subsets is a transversal. We shall use T r(V )
to denote the set of minimal transversals of a set of vertices V . For example,
T r({ace, bce, cde}) = {c, e, abd}.
The problem of computing all the minimal transversals of a hypergraph can
be solved in quasi-polynomial total time [9, 10, 13]. It is currently not known
Depth-first Search for Pseudo-intents through Minimal Transversals 5
whether it is possible to enumerate the transversals with a polynomial delay in
the general case. However, many special cases are known to have an output-
polynomial delay. Their references can be found in [9].
In this work, we cannot presuppose the nature of the hypergraph and so we
are interested in the general case. The problem still being actively studied, we
will suppose that we have a blackbox algorithm nextTrans that enumerates
the minimal transversals of a set of vertices X. We suppose, for ease of writing,
that the transversals Ti this algorithm enumerates in some arbitrary order T1 <
T2 < ... < Tn with nextTrans(Ti , X) = Ti+1 and nextTrans(Tn , X) = ∅.
For example, Berge Multiplication [5] can be adapted to take the role of
nextTrans. It is important to note that a first transversal can be computed
in polynomial time by simply removing attributes until the set stops being a
transversal.
3 Recognizing a Pseudo-Intent
We know that an attribute set is a pseudo-intent if and only if it contains the
closure of all its subsets that are pseudo-intents. As for the problem of recognizing
pseudo-intents, two cases have been studied. When only a context and a set A
are provided, checking whether A is a pseudo-intent is coNP-complete [1]. An
algorithm has been proposed in [19] that runs in O(2|A| ). When the context and
A are provided alongside all the pseudo-intents (and thus implications) contained
in A, checking whether A is a pseudo-intent is easier as we only have to verify the
closedness of A for the logical closure and ·00 , which implies a runtime polynomial
in the size of the implication set. It is this method that is used in algorithms
such as Next Closure or the one we proposed in [4] and its drawback is that it
forces an enumeration in an order that extends the inclusion order.
In this paper, we are interested in enumerating pseudo-intents in orders that
do not extend the inclusion and, as such, we cannot suppose that we know the
closure of all the subsets of a set before attempting to recognize its pseudo-
closedness. Hence, we propose to consider the problem of recognizing a pseudo-
intent A given a context and a set of subsets of A that is not necessarily complete.
Proposition 1. An attribute set A ∈ ΦI is a pseudo-intent if A 6= A00 and all
its lower covers in ΦI are closed.
Proof. Let us suppose that A is not closed and that all its lower covers are
closed. Let B be a lower cover of A and X be a subset of A. If B ⊂ X, then
I(X) = A and X 00 = A00 . If X ⊆ B and X 00 6⊆ B, then B cannot be closed and
we have a contradiction. Therefore, X 00 ⊆ B. Since the closure of every subset
of A is either A00 or contained in A, the set A is a pseudo-intent.
This proposition states that some pseudo-intents can be recognized in ΦI only
by looking at their lower covers. As such, when I is a subset of the Duquenne-
Guigues basis, a new pseudo-intent can be found by looking in ΦI for sets that
only have intents as lower covers.
6 Alexandre Bazin
Definition 1. A pseudo-intent that can be recognized using Proposition 1 with
a set of implication I is said to be recognizable. The set of all the implications
that are recognizable with I is denoted by Rec(I).
Proposition 2. ∀I ⊂ B, Rec(I) 6= ∅
Proof. Let P be minimal among pseudo-intents that are not premises of impli-
cations in I. If there is a lower cover X of P in ΦI that is not closed, then there
is a set A ⊂ X in ΦI such that A → A00 holds in the context. If A00 ⊆ P , then
P is not minimal. If A00 6⊆ P , then P is not a pseudo-intent. Both cases lead to
contradictions so all the lower covers of P are closed and P is recognizable from
I. Since we have I ⊂ B, the set of pseudo-intents that are not a premise of I is
not empty, so it has minimal elements. Hence, the set of pseudo-intents that are
recognizable from I is not empty if I ⊂ B.
We have that, even though some unknown pseudo-intents may not be recog-
nizable, there are always additional recognizable pseudo-intents for any subset
of the Duquenne-Guigues basis. This ensures that we are able to enumerate all
the pseudo-intents with an algorithm that finds recognizable ones.
Proposition 3. Let A and B be two elements of ΦI . The set B is a lower cover
of A if and only if B = A \ C with C a minimal transversal of GenI (A).
Proof. Let C be minimal such that ∀G ∈ GenI (A), G∩C 6= ∅. For any attribute
i ∈ A \ C, the set (A \ C) ∪ {i} = A \ (C \ {i}) contains a minimal generator
of A because of the minimality of C. Therefore, any B between A \ C and A is
such that I(B) = A and cannot be in ΦI . Hence, A \ C is a lower cover of A.
Let B be a lower cover of A in ΦI . By definition, I(B ∪ {i}) = A for any
attribute i ∈ A \ B so there is a subset C of A such that i ∈ C and (C \ {i}) ⊆ B
that is a minimal generator of A.
This proposition states that the lower covers of a set can be computed from
and depend on its minimal generators. As such, the number of lower covers can be
exponential in the number of minimal generators which can itself be exponential
in the size of the attribute set [14].
Definition 2. For any two attribute sets A and B, we say that B is reachable
from A if and only if B ⊂ A and there is an ordering x1 < x2 < ... < xn of the
elements of A \ B such that, for every m < n, A \ {x1 , x2 , ..., xm } is not closed
under I.
In other words, B is reachable from A if you can obtain B by removing at-
tributes from A and only go through sets that are not closed under I. Evidently,
minimal reachable sets are elements of ΦI .
Proposition 4. An attribute set A ∈ ΦI is a minimal recognizable pseudo-
intent if and only if A is not an intent and all the minimal attributes sets reach-
able from A are intents.
Depth-first Search for Pseudo-intents through Minimal Transversals 7
Algorithm 1 reachableSets(A)
Require: An attribute set A, an implication set I
1: R = ∅
S i ∈ A do
2: for every
3: G = P ∈PI (A\{i}) GenI (P )
4: C = The first transversal of G
5: while C 6= ∅ do
6: B = A \ ({i} ∪ C)
7: if PI (B) 6= ∅ then
8: R = R ∪ reachableSets(B)
9: else
10: R = R ∪ {B}
11: end if
12: C = nextT rans(C, G)
13: end while
14: end for
15: Return R
Proof. If A is a minimal recognizable pseudo-intent, then every subset of A in
ΦI is an intent. Thus every minimal reachable set is an intent.
Let us suppose that every minimal reachable subset of A is an intent and
A 6= A00 . For any set X reachable from A and any attribute set P ⊆ X, if
P 00 6⊂ A, then X cannot be an intent. Every minimal reachable subset of A
being an intent, A contains the closure of all its subsets so it is a pseudo-intent.
If P is a pseudo-intent that is not in I, subsets of A \ {i} with i ∈ P 00 \ P cannot
be intents so either P or a superset of P in ΦI that is not an intent is reachable
from A. Hence, A is a minimal recognizable pseudo-intent.
A minimal recognizable pseudo-intent can therefore be recognized by com-
puting the sets of its minimal reachable subsets. These minimal reachable sets
can be computed using Algorithm 1. By definition, reachable sets can be com-
puted by removing from A attributes that play a role in the logical closure, i.e.
attributes in minimal generators of pseudo-intents P ⊂ A such that P 00 6⊆ A \ X
for some A \ X reachable from A. The minimal transversals T make up all the
possible ways to remove minimal generators of pseudo-intents and, thus, all the
sets T such that for every Y ⊂ T , A \ Y cannot be logically closed. As such,
removing minimal transversals of the generators of pseudo-intents used in the
logical closure of a set produces a reachable set. The set A \ T is not always
logically closed so the algorithm is recursively applied until an element of ΦI is
reached.
The algorithm is not optimal as some reachable sets can be computed mul-
tiple times and the sets reachable from a set A that is not an element of ΦI
could be computed directly from PI (A) instead of its direct subsets. However,
it is sufficient to give us an upper bound of the runtime. For each recursive call,
the algorithm computes PI (A \ {i}) for every attribute i ∈ A. For each of these
8 Alexandre Bazin
S
attributes, it then computes the minimal transversals of P ∈PI (A\{i}) GenI (P ).
There is another recursive call for each pseudo-intent found missing so the run-
time is bounded by O(|A| × |I| × T ) where T is the complexity of computing
the transversals.
In the rest of this paper, we will suppose that we have an algorithm nex-
tReach that enumerates minimal reachable sets in the same fashion as next-
Trans.
4 Computing a Recognizable Pseudo-Intent
4.1 Algorithm
We want to incrementally compute the pseudo-intents in a formal context. In
the beginning, we only have the formal context (O, A, R) and an empty set of
implications I. The corresponding ΦI is the boolean lattice of subsets of A. In
order to find a first pseudo-intent, we can look for a recognizable set (Proposition
1) in ΦI . We know that a non-closed set contains a pseudo-intent. Thus, we can
start with A and recursively remove attributes as long as we obtain non-closed
sets. When we cannot remove attributes without obtaining an intent, the set is
a recognizable pseudo-intent and we have a first implication. This corresponds
to the algorithm presented in [6] that computes a first pseudo-intent. We can
then generalize the algorithm for other pseudo-intents. As I contains a new
implication, sets disappear from ΦI and we now have to look in the new lattice
for a second pseudo-intent. As it is not a Boolean lattice anymore, we cannot
simply remove attributes to obtain lower covers so we have to use Proposition
3 to compute them. By going through the lattice using non-closed lower covers
of sets until we find a set respecting Proposition 1, we can compute a second
pseudo-intent. Pseudo-intents can thus be computed incrementally until A no
longer has any non-closed lower cover. Algorithm 2, given a context, a subset I
of the Duquenne-Guigue Basis and an attribute set A ∈ ΦI , uses this method
to compute a new pseudo-intent P ⊆ A.
Proposition 5. nextP I(A, I) returns either A or a pseudo-intent that is not
in I.
Proof. Let X be a set in ΦI . If X 00 6= X, then there is a pseudo-intent P ⊆ X.
If a lower cover of X is not closed, then there is a pseudo-intent X ⊂ S. The
algorithm returns the first set it finds that has all its lower covers closed. If this
set is not A, then it is not closed and is thus a pseudo-intent.
Algorithm 3 uses Algorithm 2 to enumerate pseudo-intents iteratively until
it returns A. It is sound but not complete, as exemplified below.
Depth-first Search for Pseudo-intents through Minimal Transversals 9
Algorithm 2 nextP I(A, I)
Require: Attribute set A, Implication set I
1: P = A
2: G = GenI (A)
3: C = The first transversal of G
4: while C 6= ∅ do
5: S =A\C
6: if S 00 6= S then
7: P = nextP I(S)
8: C=∅
9: else
10: C = nextT rans(C, G)
11: end if
12: end while
13: RETURN P
Algorithm 3 allP I
1: I = ∅
2: A = nextP I(A, I)
3: while A 6= A do
4: I = I ∪ {A → A00 }
5: A = nextP I(A, I)
6: end while
7: Return I
4.2 Example
Let us consider an arbitrary context for which the Duquenne-Guigues basis is
{de → bde, bc → bcd, ac → abcd, be → bde, bcde → abcde}. We want to find its
pseudo-intents using Algorithm 3 :
The set of implications is initially empty. We start with abcde.
It has a single minimal generator, itself. The first minimal transversal of
Gen(abcde) is a. The set abcde \ a = bcde is not an intent so we continue recur-
sively with it.
The set bcde has a single minimal generator, itself. The first minimal transver-
sal of Gen(bcde) is b. The set bcde \ b = cde is not an intent so we continue
recursively with it.
The set cde has a single minimal generator, itself. The first minimal transver-
sal of Gen(cde) is c. The set cde\c = de is not an intent so we continue recursively
with it.
The set de has a single minimal generator, itself. The first minimal transversal
of Gen(de) is d. The set de \ d = e is an intent. The second and last minimal
transversal is e. The set de \ e = d is an intent. The algorithm returns de as the
first pseudo-intent which gives us I = {de → bde}.
10 Alexandre Bazin
Fig. 3. The five steps of the algorithm. In red the sets considered by the recursive calls,
in black the lower covers of those sets in ΦI .
We start again with abcde. It has a single minimal generator, acde. The first
minimal transversal of Gen(abcde) is a. The set abcde \ a = bcde is not an intent
so we continue recursively with it.
The set bcde has a single minimal generator, cde. The first minimal transver-
sal of Gen(cde) is c. The set bcde \ c = bde is an intent. The second minimal
transversal is d. The set bcde \ d = bce is not an intent so we continue recursively
with it.
The set bce has a single minimal generator, itself. The first minimal transver-
sal of Gen(bce) is b. The set bce \ b = ce is an intent. The second minimal
transversal is c. The set bce \ c = be is not an intent so we continue recursively
with it.
The set be has a single minimal generator, itself. The first minimal transversal
of Gen(be) is b. The set be \ b = e is an intent. The second and last minimal
transversal is e. The set be \ e = b is an intent. The algorithm returns be as the
second pseudo-intent which gives us I = {de → bde, be → bde}.
We start again with abcde. It has two minimal generators, acde and abce.
The first minimal transversal of Gen(abcde) is a. The set abcde \ a = bcde is not
an intent so we continue recursively with it.
The set bcde has two minimal generators, bce and cde. The first minimal
transversal of Gen(cde) is c. The set bcde \ c = bde is an intent. The second
Depth-first Search for Pseudo-intents through Minimal Transversals 11
minimal transversal is bd. The set bcde \ bd = ce is an intent. The third and
last minimal transversal is e. The set bcde \ e = bcd is an intent. The algorithm
returns bcde as the third pseudo-intent which gives us I = {de → bde, be →
bde, bcde → abcde}.
We start again with abcde. It has two minimal generators, cde and bce. The
first minimal transversal of Gen(abcde) is bd. The set abcde \ bd = ace is not an
intent so we continue recursively with it.
The set ace has a single minimal generator, itself. The first minimal transver-
sal of Gen(ace) is a. The set ace \ a = ce is an intent. The second minimal
transversal is c. The set ace \ c = ae is an intent. The third minimal transversal
is e. The set ace \ e = ac is not an intent so we continue recursively with it.
The set ac has a single minimal generator, itself. The first minimal transversal
of Gen(ace) is a. The set ac \ a = c is an intent. The second and last minimal
transversal is c. The set ac\c = a is intent. The algorithm returns ac as the fourth
pseudo-intent which gives us I = {de → bde, be → bde, bcde → abcde, ac →
abcd}.
We start again with abcde. It has three minimal generators, ace, cde and bce.
The first minimal transversal of Gen(abcde) is c. The set abcde \ c = abde is
an intent. The second minimal transversal is e. The set abcde \ e = abcd is an
intent. The third and last minimal transversal is abd. The set abcde \ abd = ce
is an intent. The algorithm ends.
The algorithm has found four pseudo-intents but is unable to find the set bc
when considering the minimal transversals, and thus the sets, in that partic-
ular order. Indeed, knowing be → bde and de → bde makes bcde recognizable
and blocks every path from abcde to bc in ΦI . Finding bc before either de or be
solves the problem.
4.3 Complexity
The nature of Algorithm 2 makes it easy to bound the delay between finding
two pseudo-intents. As the algorithm starts from A and removes attributes until
it ends, it performs a maximum of |A| recursive calls before finding a pseudo-
intent. In a call, three different tasks are performed : computing the closure
of a set, computing the set of minimal generators and computing the set of all
lower covers. The closure of a set is known to be computable in polynomial time.
Computing GenI (A) is done in time polynomial in the size of the output. The
computation of all the lower covers of A, as we have seen in Section 2.4, can be
performed in quasi-polynomial total time, i.e. in time quasi-polynomial in the
size of n = |Gen
I (A)|
and m = |T r(GenI (A))| (note that the size of m itself is
n
bounded by n [18]). Hence, the delay is in O(|A| × (C + G + T )) with C
2
the complexity of computing a closure, G the complexity of computing minimal
generators and T the complexity of computing the lower covers.
12 Alexandre Bazin
Algorithm 4 nextM inP I(A, I)
Require: Attribute set A, Implication set I
1: P = A
2: C =The first minimal set reachable from A
3: while C 6= ∅ do
4: if C 00 6= C then
5: P = nextM inP I(C)
6: C=∅
7: else
8: C = nextReach(C, A)
9: end if
10: end while
11: RETURN P
An interesting point of detail is that the algorithm does not necessarily enu-
merate all the intents. When all the upper covers of an intent A in ΦI are
intents themselves, A cannot be reached by the algorithm anymore. In particu-
lar, if A ∪ {i} = (A ∪ {i})00 for every i ∈ A \ A, we are sure that A will never be
considered. In the previous example (see Figure 3), we see that the intents abd,
ab, ad, bd, de and ∅ are never considered because they do not appear as lower
covers of sets. We suppose that this property helps reduce the runtime on dense
contexts with a high number of intents.
5 Computing a Minimal Recognizable Pseudo-Intent
5.1 Algorithm
The problem with Algorithm 3 is that there are some pseudo-intents it cannot
compute. Among those leftover pseudo-intents, there is necessarily at least one
that is minimal. We have shown in Proposition 4 that a minimal recognizable
pseudo-intent P can be recognized through the minimal sets reachable from P .
Those reachable sets can themselves be obtained by computing the transversals
of the sets of minimal generators of the pseudo-intents involved in the logical
closure of the different P \ {i} (Algorithm 1). Algorithm 4 uses these properties
to compute a minimal recognizable pseudo-intent. In a manner similar to that of
Algorithm 2, the algorithm starts with A and enumerates the minimal reachable
sets. Once one that is not an intent is found, the algorithm is recursively applied.
The algorithm ends when it finds a set with only intents as minimal reachable
sets. The main difference between Algorithm 2 and Algorithm 4 is that the
former performs a depth-first search in the lattice ΦI while the latter performs
it in the directed graph in which the nodes are the elements of ΦI and the edges
are the pairs in the “reachable” relation.
Proposition 6. Algorithm 4 returns either A or a minimal pseudo-intent that
is not in I.
Depth-first Search for Pseudo-intents through Minimal Transversals 13
Algorithm 5 allP I2
1: I = ∅
2: A = nextminP I(A, I)
3: while A 6= A do
4: I = I ∪ {A → A00 }
5: A = nextM inP I(A, I)
6: end while
7: Return I
Proof. From Proposition 4 we know that if every minimal set T ∈ ΦI reachable
from A ∈ ΦI is closed and A is not, then A is a minimal recognizable pseudo-
intent. If T ∈ ΦI is not closed, then T contains a minimal recognizable pseudo-
intent so the algorithm can be recursively called on T . The algorithm stops
when it encounters a set A with only intents as minimal reachable sets. The set
A being the only intent on which the algorithm is called, it returns either A or
a minimal recognizable pseudo-intent.
We can enumerate all the pseudo-intents with Algorithm 5 using Algorithm
4 in the same fashion as Algorithm 3.
Proposition 7. Algorithm 5 is sound and complete.
Proof. Soundness follows from Proposition 6. For any implication set I ⊂ B,
pseudo-intent P not used in I and attribute set A ∈ ΦI such that P ⊂ A, no
set X such that P ⊂ X and P 00 6⊆ X can be an intent so either P or one of its
non-closed supersets is reachable from A. Hence, the algorithm does not stop
until every pseudo-intent has been found.
5.2 Example
Contrary to Algorithm 3, Algorithm 5 is complete. We can either use it to
compute all the pseudo-intents or combine it with Algorithm 3. Let us suppose
we have used Algorithm 3, as exemplified in Section 4, and that we know the
set of implications I = {de → bde, be → bde, bcde → abcde, ac → abcd}. Using
Algorithm 5 from there gives us the following :
We start with abcde. The first minimal reachable set abcde\(a∪bd) = ce is an
intent. The second minimal reachable set abcde \ (a ∪ bc) = de is an intent. The
third minimal reachable set abcde\(a∪e) = bcd is an intent. The fourth minimal
reachable set abcde \ (b ∪ cd) = ae is an intent. The fifth minimal reachable set
abcde\(b∪e) = cd is an intent. The sixth minimal reachable set abcde\(b∪ce) =
ad is an intent. The seventh minimal reachable set abcde \ c = abde is an intent.
The eighth minimal reachable set abcde \ (d ∪ ab) = ce is an intent. The ninth
minimal reachable set abcde \ (d ∪ ae) = bc is not an intent so we continue
recursively with it.
14 Alexandre Bazin
The set bc contains no pseudo-intents so its minimal reachable sets are bc\b =
c and bc \ c = b. They are both intents so the algorithm returns bc as a new
pseudo-intent which gives us I = {de → bde, be → bde, bcde → abcde, ac →
abcd, bc → bcd}.
We start again with abcde. The eight first minimal reachable sets computed
are the same as in the previous step. The ninth reachable set abcde \ cde = ab
is an intent. The tenth and last reachable set abcde \ e = abcd is an intent. The
algorithm ends.
In this example, the pseudo-intent bc has been found after bcde. Using both
Algorithm 3 and Algorithm 5, it is thus possible to enumerate pseudo-intents in
orders that do not extend the inclusion.
5.3 Complexity
Once again, the delay between two pseudo-intents with Algorithm 5 is easy
to bound. Algorithm 4 performs at most |A| recursive calls before returning
a pseudo-intent or A. Each call requires the computation of, at most, all the
reachable sets in ΦI . We have shown that this can be done in O(|A| × |I| × T )
with T the complexity of computing minimal transversals of minimal generators
of pseudo-intents. Thus, the worst case delay of Algorithm 5 is |I| times that of
Algorithm 3.
A first minimal transversal can be computed in polynomial time. As such,
for any attribute set A, we can compute its first reachable set in ΦI in time
polynomial in |A| and |I|. Hence, if, for every A ∈ ΦI that is not a pseudo-intent,
the reachable sets in ΦI are ordered in such a way that the first one is not closed,
Algorithm 5 can compute (but not necessarily recognize) a pseudo-intent in time
polynomial in the size of the implication set. A minimal pseudo-intent P , by
definition, does not contain any other pseudo-intent so the set of its reachable
set is {P \ {p} | p ∈ P } which can be computed in polynomial time. Thus,
there are always orderings of reachable sets such that Algorithm 5 can compute
minimal pseudo-intents with an incremental polynomial time between two of
them. However, as shown in [6], minimal pseudo-intents cannot be enumerated
in output polynomial time. Indeed, even though it is possible to compute a
minimal pseudo-intent in time polynomial in the size of the implication set,
confirming that they have all been found is exponential because non-minimal
pseudo-intents and A have a potentially exponential number of reachable sets.
6 Conclusion
We have proposed two algorithms for computing pseudo-intents using the com-
putation of minimal transversals as their main operation. The first can find
pseudo-intents before some of their subsets that are themselves pseudo-intents
but it is not complete for some enumeration orders. The second is complete but
can only enumerate in orders that respect the inclusion relation. They can be
Depth-first Search for Pseudo-intents through Minimal Transversals 15
combined to obtain the enumeration order of the first with the completeness of
the second. We expressed their delay as a function of the complexity of com-
puting minimal transversals. We showed that, for some orderings of attribute
sets, pseudo-intents can be reached, but not recognized, in incremental polyno-
mial time. As both reaching and recognizing pseudo-intents, in our context, are
related to the problem of computing minimal transversals in hypergraphs for
which many special cases are known, we believe that this work may be useful in
isolating more cases for which the enumeration of pseudo-intents is easier.
On the practical side, the fact that the algorithms do not necessarily enu-
merate the entirety of the set of intents should significantly reduce the runtime
on dense contexts. Furthermore, the depth-first strategy used in the algorithms
allows for some computations to be saved and reused. Further algorithmic opti-
mizations and empirical comparisons with other algorithms for the same problem
will be the subject of future investigations.
References
1. Mikhail A. Babin and Sergei O. Kuznetsov. Recognizing Pseudo-intents is coNP-
complete. In Proceedings of the 7th International Conference on Concept Lattices
and Their Applications, Sevilla, Spain, October 19-21, 2010, pages 294–301, 2010.
2. Mikhail A. Babin and Sergei O. Kuznetsov. Computing Premises of a Minimal
Cover of Functional Dependencies is Intractable. Discrete Applied Mathematics,
161(6):742–749, 2013.
3. Konstantin Bazhanov and Sergei A. Obiedkov. Comparing Performance of Algo-
rithms for Generating the Duquenne-Guigues Basis. In Proceedings of The Eighth
International Conference on Concept Lattices and Their Applications, Nancy,
France, October 17-20, 2011, pages 43–57, 2011.
4. Alexandre Bazin and Jean-Gabriel Ganascia. Enumerating Pseudo-Intents in a
Partial Order. In Proceedings of the Tenth International Conference on Concept
Lattices and Their Applications, La Rochelle, France, October 15-18, 2013., pages
45–56, 2013.
5. Claude Berge. Hypergraphs: Combinatorics of Finite Sets, volume 45. Elsevier,
1984.
6. Felix Distel and Baris Sertkaya. On the Complexity of Enumerating Pseudo-intents.
Discrete Applied Mathematics, 159(6):450–466, 2011.
7. Thomas Eiter and Georg Gottlob. Identifying the Minimal Transversals of a Hy-
pergraph and Related Problems. SIAM J. Comput., 24(6):1278–1304, 1995.
8. Thomas Eiter, Georg Gottlob, and Kazuhisa Makino. New Results on Mono-
tone Dualization and Generating Hypergraph Transversals. SIAM J. Comput.,
32(2):514–537, 2003.
9. Thomas Eiter, Kazuhisa Makino, and Georg Gottlob. Computational As-
pects of Monotone Dualization: A Brief Survey. Discrete Applied Mathematics,
156(11):2035–2049, 2008.
10. Michael L. Fredman and Leonid Khachiyan. On the Complexity of Dualization of
Monotone Disjunctive Normal Forms. J. Algorithms, 21(3):618–628, 1996.
11. Bernhard Ganter. Two Basic Algorithms in Concept Analysis. In Preprint Tech-
nische Hochschule Darmstadt, 1984.
16 Alexandre Bazin
12. Jean-Louis Guigues and Vincent Duquenne. Familles Minimales d’Implications
Informatives Résultant d’un Tableau de Données Binaires. Mathématiques et Sci-
ences humaines, 95:5–18, 1986.
13. Vladimir Gurvich and Leonid Khachiyan. On Generating the Irredundant Con-
junctive and Disjunctive Normal Forms of Monotone Boolean Functions. Discrete
Applied Mathematics, 96-97:363–373, 1999.
14. Miki Hermann and Baris Sertkaya. On the Complexity of Computing Generators
of Closed Sets. In Formal Concept Analysis, 6th International Conference, ICFCA
2008, Montreal, Canada, February 25-28, 2008, Proceedings, pages 158–168, 2008.
15. Sergei O. Kuznetsov. On the Intractability of Computing the Duquenne-Guigues
Bas. J. UCS, 10(8):927–933, 2004.
16. Sergei O. Kuznetsov and Sergei A. Obiedkov. Counting Pseudo-intents and #P-
completeness. In Formal Concept Analysis, 4th International Conference, ICFCA
2006, Dresden, Germany, February 13-17, 2006, Proceedings, pages 306–308, 2006.
17. Sergei O. Kuznetsov and Sergei A. Obiedkov. Some Decision and Counting Prob-
lems of the Duquenne-Guigues Basis of Implications. Discrete Applied Mathemat-
ics, 156(11):1994–2003, 2008.
18. Zbigniew Lonc and Miroslaw Truszczynski. On the Number of Minimal Transver-
sals in 3-uniform Hypergraphs. Discrete Mathematics, 308(16):3668–3687, 2008.
19. Sebastian Rudolph. Some Notes on Pseudo-closed Sets. In Formal Concept Analy-
sis, 5th International Conference, ICFCA 2007, Clermont-Ferrand, France, Febru-
ary 12-16, 2007, Proceedings, pages 151–165, 2007.