Theory and Applications of Categories, Vol. 17, No. 5, 2006, pp. 80–102.

APPROXIMABLE CONCEPTS, CHU SPACES, AND INFORMATION SYSTEMS

GUO-QIANG ZHANG AND GONGQIN SHEN

Abstract. This paper serves to bring three independent but important areas of computer science to a common meeting point: Formal Concept Analysis (FCA), Chu Spaces, and Domain Theory (DT). Each area is given a perspective or reformulation that is conducive to the flow of ideas and to the exploration of cross-disciplinary connections. Among other results, we show that the notion of state in Scott’s information system corresponds precisely to that of formal concepts in FCA with respect to all finite Chu spaces, and the entailment relation corresponds to “association rules”. We introduce, moreover, the notion of approximable concept and show that approximable concepts represent algebraic lattices which are identical to Scott domains except the inclusion of a top element. This notion serves as a stepping stone in the recent work [Hitzler and Zhang, 2004] in which a new notion of morphism on formal contexts results in a category equivalent to (a) the category of complete algebraic lattices and Scott continuous functions, and (b) a category of information systems and approximable mappings.

1. Introduction

This paper serves as the meeting point of three “parallel worlds”: Chu spaces, Domain Theory, and Formal Concept Analysis. It brings the three independent areas together and reviews some basic connections among them, leaving open opportunities for the exploration of cross-disciplinary influences. To serve this goal, we try to make the material easily accessible to a wider audience.

We begin with an overview of each of the three areas, followed by an account of the background of each area from a unified perspective. We then move to basic connections among them and point to topics of immediate interest and opportunities for further development, including applications in data-mining and knowledge discovery. Due to its interdisciplinary nature, the paper is written in a way that does not assume specific background knowledge for each area.

1.1. Domain theory. Domain theory (DT) was introduced by Scott in the late 60s for the denotational semantics of programming languages. It provides a mathematical foundation for the design, definition, and implementation of programming languages, and for systems for the specification and verification of programs.

Received by the editors 2003-09-24 and, in revised form, 2006-11-13. Published on 2006-12-18 in the volume Chu spaces: theory and applications. 2000 Mathematics Subject Classification: 03B70, 06A15, 06B23, 08A70, 68P99, 68Q55. Key words and phrases: Formal concept analysis, domain theory, Chu spaces. \begin{matrix}c \\ ◯ \end{matrix} Guo-Qiang Zhang and Gongqin Shen, 2006. Permission to copy for private use granted.

The fundamental idea of domain theory is partial information and successive approximation. The notion of partial information is captured by a complete partial order (cpo). Functions acting on cpos are those which preserve the limits of directed sets – this is the so-called continuity property. If one thinks of directed sets as an approximating schema for infinite objects, then members of the directed set can be thought of as finite approximations. Continuity makes sure that infinite objects can be approximated by finite computations.

An important property of continuous functions is that when ordered in appropriate ways, they form a complete partial order again. Thus a continuous function becomes once again an object in a partial order. The beauty of domain theory is that a higherorder object is treated just as another ordinary object. The notion of partiality and approximation is the key insight that allows for recursively defined domains but this also makes most notions in domain theory non-symmetric with respect to order-reversing. For further information on domain theory, see, for example, [Abramsky and Jung, 1994, Amadio and Curien, 1998, Gunter and Scott, 1990, Plotkin, 1983, Winskel, 1993] as well as [Zhang, 1991]. We highly recommend [Davey and Priestley, 2002] as an introduction to domains and information systems (Chapter 9) and to formal concept analysis (Chapter 3), even though the intimate relationship between the two areas were not explicated until [Zhang, 2003, Hitzler and Zhang, 2004], and the current paper.

1.2. Formal concept analysis. FCA is an order-theoretic method for the mathematical analysis of scientific data, pioneered by German scientists Wille and others [Ganter and Wille, 1999] in mid 80’s. The novel idea of FCA is the clustering of attributes based on the algebraic principle of Galois connection, forming a partially ordered set called concept lattice. The clustering determines which collection of attributes forms a coherent entity called a concept, by the philosophical criteria of unity between extension and intension. The extension of a concept consists of all objects belonging to the concept, while the intension of a concept consists of attributes common to all these objects. One can then take this as the defining property of a concept: a collection of attributes which agrees with the intension of its extension.

Over the past twenty years, FCA has emerged a powerful tool for clustering, data analysis, information retrieval, knowledge discovery, and ontological engineering, used by over two hundred scientific projects so far. This fruitful development of applied FCA lies in the fact that FCA is susceptible to many interpretations, so that connections can be made with different areas and used by researchers from different disciplines.

The single most important benefit of FCA-based methods is that in many applications lattices, rather than trees, are more natural. But FCA-based approaches are still not as widely spread in data analysis and machine learning as they should be, and they often come with a higher computational cost.

1.3. Chu spaces. Category theory (CT) has provided a unified language for managing conceptual complexity in mathematics and computer science. Chu spaces, having its birth place in category theory, was brought to light in computer science through the work of Barr and Seely [Bar, 1979, Bar, 1991, Seely, 1989] as constructive models of linear logic. Pratt’s extensive work [Pratt, 2000, Pratt, 1999, Pratt, 1997, Pratt, 1995, Pratt, 1995, Pratt, 2003] broadened the scope of their applications to areas such as models for concurrency and philosophy of logic, information, and computation.

There are substantial culture differences among the three areas. FCA, for example, focuses on internal properties of and algorithms for concept structures almost exclusively on an individual basis, while CT mandates that concept structures should be looked at collectively as a whole, with appropriate morphisms relating one individual structure to another – it can be seen as a universal object-oriented language. On the other hand, DT carries an intrinsic higher-order view incorporating the notion of partial information and successive approximation. In a precise sense, FCA and Chu spaces started with the same objects but went to different directions out of their own independent motivations. This paper brings them together again through domain-theoretic methods – Scott’s information systems [Scott, 1982], in particular.

Related work. The precursor of the current work is [Zhang, 2003], where the notions of information states and formal concepts are shown to be equivalent for finite contexts. This paper extends this connection to full generality by introducing the notion of approximable concepts. In Hitzler and Zhang [Hitzler and Zhang, 2004], a follow-up to this paper, the connection between approximable concept lattices and information systems is extended to a fuller extent as a categorical equivalence. A new notion of morphism on formal contexts results in a category equivalent to (a) the category of complete algebraic lattices and Scott continuous functions, and (b) a category of information systems and approximable mappings. We provide a brief account of this work in Section 7. In other related work, Lamarche [Lamarche, 1994] provides an order-theoretic model for linear logic based on a continuity condition on a special class of Chu spaces. The so-called casuistries form a full subcategory of Chu spaces. A topological space viewed as a Chu space is a casuistry exactly when the topology is T_{0}, the specialization order is a dcpo, and every open set is Scott open. This way, Lamarche obtains a *-autonomous category of topological spaces. Along the line of domains and logic, Hitzler [Hitzler 2004], Hitzler and Wendt [Hitzler and Wendt, 2003] establish close connections between reasoning in the clausal logic of Rounds and Zhang [Rounds and Zhang, 2001] (the so-called “Logic RZ”) and the concept-closure construction. Since coherent algebraic domains can be viewed as a vastly rich class of structures for hierarchical knowledge representation and since Logic RZ is intimately related to logic programming and nonmonotonic reasoning as well, this opens up new avenues for research in managing and reasoning about ontological structures, an area where a truly mathematical foundation is yet to be found.

2. Preliminaries

This section reviews terminologies and backgrounds for the three areas mentioned earlier, with the goal to bring them to some common bases.

2.1. Cpos. Let (D, ⊑) be a partial order. A subset X of D is directed if it is non-empty and for each pair of elements a, b ∈ X, there is an upper bound x ∈ X for {a, b}. A complete partial order (cpo) is a partial order (D, ⊑) with a least element (⊥) and every directed subset X has a least upper bound (or join) ⨆ X. A complete lattice is a partial order in which any subset has a join (this implies that any subset will also have a meet – greatest lower bound). Compact elements of a cpo (D, ⊑) are those inaccessible by directed sets: a ∈ D is compact if for any directed set X of D, a ⊑ ⨆ X implies that there exits x ∈ X with a ⊑ x. A cpo is algebraic if every element is the join of a directed set of compact elements. A set X ⊆ D is bounded if it has an upper bound. A cpo is bounded complete if every bounded set has a join. Scott domains are bounded complete algebraic cpos.

Notation. The upper set ↑X of a set X is defined to be {y | ∃x ∈ X, x ⊑ y}. A set is upward-closed if X = ↑X. Similarly, a set is down-closed if X = ↓X.

2.2. Closure systems and closure operators. For any set A, let P(A) denote the powerset of A. A subset C of the powerset P(A) is called a closure system on A if C is closed under arbitrary intersections, i.e., for every X ⊆ C, ⋂ X ∈ C. Note that, by convention, this implies that the whole space A is always a member of a closure system C, by instantiating X as the empty set in the definition.

A closure operator on A is a function φ : P(A) → P(A) which is inflationary (X ⊆ φ(X)), monotonic (X ⊆ Y ⇒ φ(X) ⊆ φ(Y)), and idempotent (φ(φ(X)) = φ(X)).

2.3. Proposition. Define a closed set with respect to a closure operator

φ : P(A) → P(A)

to be a fixed point of φ. Then closed sets of φ are precisely sets of the form φ(X). The collection of closed sets {φ(X) | X ∈ P(A)} forms a closure system on A.

The defining property of closure systems provides arbitrary meets. The join of a subset X can then be obtained as the meet of the set of upper bounds of X, A included. These observations lead to the following basic property about closure systems.

2.4. Proposition. For any closure system C on A, the partial order (C, ⊆) is a complete lattice with A being the top element.

2.5. Galois connections.

2.6. Definition. Let P, Q be sets. A pair of functions

s : P(P) → P(Q) and t : P(Q) → P(P)

is called a Galois connection^{1} if for each X ∈ P(P) and Y ∈ P(Q),

s(X) ⊇ Y if and only if X ⊆ t(Y).

1Galois connections appear in the literature in two equivalent versions. The original version uses order-reversing maps [Birkhoff, 1940], and the second version, more popular in computer science, uses order-preserving maps. Since set-containment is more primitive, the notion of Galois connection used in

Although we are not using the notion of Galois connection in its full generality, a slightly more general version is needed in the last section of the paper. Let P, Q be sets and A ⊆ P(P), B ⊆ P(Q). A pair of functions s : A → B and t : B → A is called a Galois connection if for each X ∈ A and Y ∈ B, s(X) ⊇ Y if and only if X ⊆ t(Y). The results below in this section refer to Definition 2.6, which may or may not hold for this slightly more general notion.

The next well-known fact shows that closure operators can be derived from Galois connections in a natural way.

2.7. Proposition. For any Galois connection s, t with s : P(P) → P(Q) and t : P(Q) → P(P), s ∘ t is a closure operator on Q, and t ∘ s is a closure operator on P.

The proof of this proposition uses some basic properties about Galois connections, summarized in the following lemma (for more details see [Melton, et.al., 1985]).

2.8. Lemma. Let the pair (s, t) with s : P(P) → P(Q) and t : P(Q) → P(P) be a Galois connection. The following are true:

1. s ∘ t and t ∘ s are inflationary.

2. s and t are anti-monotonic, i.e., if X ⊆ Y then s(Y) ⊆ s(X), and similarly for t.

3. s ∘ t and t ∘ s are monotonic.

4. s ∘ t ∘ s = s and t ∘ s ∘ t = t and, therefore, s ∘ t and t ∘ s are idempotent.

The next definition serves to fix notations only.

2.9. Definition. Any function f : A → B can be lifted to the powerset level in two canonical ways:

f^{+} : P(A) → P(B) with X ⟼ {f(a) | a ∈ X},
f^{−} : P(B) → P(A) with Y ⟼ {a | f(a) ∈ Y }.

f^{−} is the standard inverse image operation, and f^{+} is the forward image operation. The notation is chosen here by symmetry. Note that f^{+} ∘ f^{−} is less than the identity function on P(B) and f^{−} ∘f^{+} dominates identity with respect to coordinatewise inclusion (they form a Galois connection in the general sense [Birkhoff, 1940]).

2.10. Proposition. For any function f : A → B, we have

1. (f^{+} ∘ f^{−})Y ⊆ Y for any Y ∈ P(B);

2. (f^{−} ∘ f^{+})X ⊇ X for any X ∈ P(A);

3. f^{+} ∘ f^{−} is the identity function if and only if f is onto;

4. f^{−} ∘ f^{+} is the identity function if and only if f is one-to-one.

this paper is more concrete, serving our purpose well. Note that we are in fact neutral with respect to the issue of order-preserving vs. order-reversing: set-inclusion removes the potential overhead for keeping track of the direction of order.

3. Chu spaces and formal concept lattices

We will consider a special form of Chu spaces in this paper. Pratt [Pratt, 1995] provides arguments for the use of sets in place of the enriching category V.

3.1. Definition. A Chu space P is a triple (P_{o}, ⊧_{P} , P_{a}) where P_{o} is a set of objects and P_{a} is a set of attributes. The satisfaction relation ⊧_{P} is a subset of P_{o} × P_{a}. A mapping from a Chu space (P_{o}, ⊧_{P} , P_{a}) to a Chu space (Q_{o}, ⊧_{Q}, Q_{a}) is a pair of functions (f_{a}, f_{o}), with f_{a} : P_{a} → Q_{a} and f_{o} : Q_{o} → P_{o} such that for any x ∈ P_{a} and y ∈ Q_{o}, f_{o}(y) ⊧_{P} x iff y ⊧_{Q} f_{a}(x).

3.2. Example. The most common construction in data-mining is to extend a relation (context) by a row, adding one new object with the observed attributes, but the attribute set remain unchanged. This construction induces a Chu-mapping, from the enlarged space to the initial space, with f_{a} being the identity function on attributes, and f_{o} the injection of objects.

3.3. Example. Galois connections can also be viewed as Chu space mappings. Suppose a pair of functions

s : P(P) → P(Q) and t : P(Q) → P(P)

forms a Galois connection. Then (s, t) is a mapping from the Chu space (P(P), ⊇, P(P)) to the Chu space (P(Q), ⊆, P(Q)), because for each X ∈ P(P) and Y ∈ P(Q), we have t(Y) ⊇ X if and only if Y ⊆ s(X).

A Chu space is called a context in FCA, but “Chu” carries with it the notion of morphism, to form a category. On the other hand, FCA provides the notion of concept, intrinsic to a Chu space.

3.4. Definition. With respect to a Chu space P = (P_{o}, ⊧_{P} , P_{a}), two functions can be defined:

α : P(P_{o}) → P(P_{a}) with X ⟼ {a | ∀x ∈ X x ⊧_{P} a},
ω : P(P_{a}) → P(P_{o}) with Y ⟼ {o | ∀y ∈ Y o ⊧_{P} y}.

A subset A ⊆ P_{a} is called a (formal) concept (of attributes) if it is a fixed point of α ∘ ω, i.e., α(ω(A)) = A. Dually, a subset X ⊆ P_{o} is called a (formal) concept (of objects) if it is a fixed point of ω ∘ α.

The functions α and ω are dependent on P and we will use subscripts to avoid confusion. Readers familiar with FCA will notice that our notation differs from the standard notation in FCA which collapses both α_{P} and ω_{P} to a single ( )′ without the possibility of using subscripts. The elaboration of notation to a less context-sensitive one makes it more expressive and accurate (try to restate some of the results in this paper using ( )′ only!). The following is a fundamental theorem in formal concept analysis.

3.5. Theorem. [Wille] With respect to a Chu space

P = (P_{o}, ⊧_{P} , P_{a}),

the pair (α, ω) forms a Galois connection. As a consequence, we have

1. The set of attribute (object) concepts of P forms a closure system.

2. The attribute (object) concepts of P under set inclusion form a complete lattice.

3. The lattice of attribute concepts and the lattice of object concepts are anti-isomorphic to each other.

Notation. From now on, we write LP for the complete lattice of formal concepts associated with a Chu space P. To be more precise, we can write (LP_{a}, ⊆) for the complete lattice of attribute concepts, and (LP_{o}, ⊇) for the complete lattice of object concepts. But this more specific notation is usually not needed.

The next lemma indicates some specific properties of the Galois connection (α, ω) associated a Chu space. The proof follows from the definition of α, ω immediately. The lemma holds in the infinite case as well.

3.6. Lemma. With respect to a Chu space P = (P_{o}, ⊧_{P} , P_{a}) and subsets A, B ⊆ P_{a}, S, T ⊆ P_{o}, we have

\begin{aligned}ω(A ∪ B) & = ω(A) ∩ ω(B) \\ α(S ∪ T) & = α(S) ∩ α(T). \end{aligned}

3.7. Example. Here is an example which shows that Chu-mappings do not necessarily preserve concepts.

\begin{matrix}P & a & b \\ 1 & × & × \\ 2 & × \end{matrix}  \begin{matrix}Q & a & b \\ 1 & × & × \\ 2 & × & × \end{matrix}

Define f : P_{a} → Q_{a} to be the identity map, and g : Q_{o} → P_{o} to be the constant map λx.1. One can readily check that the pair (f, g) so defined gives a Chu-mapping from P to Q. Note that while {a} is a concept of P, f^{+}({a}) = {a} is not a concept of Q.

The following result, first pointed out in [Lamarche, 1994], serves as a starting point to understand how Chu-mappings interact with concept lattices.

3.8. Proposition. Let (f, g) with f : P_{a} → Q_{a} and g : Q_{o} → P_{o} be a Chu mapping from (P_{o}, ⊧_{P} , P_{a}) to (Q_{o}, ⊧_{Q}, Q_{a}). We have

α_{P} ∘ g^{+} = f^{−} ∘ α_{Q} and ω_{Q} ∘ f^{+} = g^{−} ∘ ω_{P} .

Stated differently, the pair ω_{Q} ∘ f^{+} and α_{P} ∘ g^{+} forms a Galois connection between the concept lattices (and similarly for the pair g^{−} ∘ ω_{P} and f^{−} ∘ α_{Q}). This is the basis for a a categorical equivalence between Chu spaces and complete lattices (see [Erné, 2004]).

Notation. We use ⊑ to denote the extensional order of functions on sets with respect to inclusion.

3.9. Proposition. With respect to any Chu-mapping (f, g) from (P_{o}, ⊧_{P} , P_{a}) to (Q_{o}, ⊧_{Q} , Q_{a}) with f : P_{a} → Q_{a} and g : Q_{o} → P_{o}, the following statements are true:

1. g^{+} ∘ g^{−} ∘ ω_{P} ⊑ ω_{P},

2. α_{P} ∘ g^{+} ∘ g^{−} ∘ ω_{P} ⊒ α_{P} ∘ ω_{P},

3. α_{Q} ∘ ω_{Q} ∘ f^{+} ⊒ f^{+} ∘ α_{P} ∘ ω_{P},

4. α_{P} ∘ ω_{P} ∘ f^{−} ⊑ f^{−} ∘ α_{Q} ∘ ω_{Q},

5. ω_{P} ∘ α_{P} ∘ g^{+} ⊑ g^{+} ∘ ω_{Q} ∘ α_{Q},

6. ω_{Q} ∘ α_{Q} ∘ g^{−} ⊒ g^{−} ∘ ω_{P} ∘ α_{P}.

These observations lead to the next two additional propositions identifying some conditions under which concepts are preserved under Chu-mappings.

3.10. Proposition. Let (f, g) with f : P_{a} → Q_{a} and g : Q_{o} → P_{o} be a mapping from (P_{o}, ⊧_{P} , P_{a}) to (Q_{o}, ⊧_{Q}, Q_{a}), as defined on Chu spaces. If both f and g are onto (surjective) then we have:

1. f^{+} maps (attribute) concepts over P to (attribute) concepts over Q;

2. f^{−} maps (attribute) concepts over Q to (attribute) concepts over P;

3. g^{+} maps (object) concepts over Q to (object) concepts over P;

4. g^{−} maps (object) concepts over P to (object) concepts to Q.

3.11. Proposition. Let (f, g) with f : P_{a} → Q_{a} and g : Q_{o} → P_{o} be a mapping from (P_{o}, ⊧_{P} , P_{a}) to (Q_{o}, ⊧_{Q}, Q_{a}), as defined on Chu spaces. The following statements are true.

1. If f is injective (one-to-one) and g is surjective (onto), then X is a concept if f^{+}X is a concept.

2. If g is injective and f is surjective, then Y is a concept if g^{+}Y is a concept.

3. If both f and g are surjective, then B is a concept if f^{−}B is a concept, and X is a concept if g^{−}X is a concept.

4. Concept lattices and information systems

The converse of Theorem 3.5 is also true: every complete lattice is isomorphic to a concept lattice of a Chu space. This is a standard result in FCA; we provide a proof in terms of the formulation used in this paper to make it self-contained. The proof uses the idea of “open sets as properties”. These open sets are the basis of the Alexandrov topology [Johnstone, 1982] and the construction is the so-called Dedekind-MacNeille completion.

4.1. Theorem. [Representation Theorem] For every complete lattice D, there is a Chu space P such that D is order-isomorphic to LP.

Proof. Suppose (D, ⊑) is a complete lattice. Define the Chu space P = (P_{o}, ⊧, P_{a}), where P_{o} = P_{a} = D, and x ⊧ b iff b ⊑ x. We want to show that LP is order-isomorphic to (D, ⊑).

First note that for any X ⊆ P_{a}, we have

ωX = {o | ∀x ∈ X, o ⊧ x}
= {o | ∀x ∈ X, x ⊑ o}
= {o | ⨆ X ⊑ o}
= ↑(⨆ X).

On the other hand,

αY = {a | ∀y ∈ Y, y ⊧ a}
= {a | ∀y ∈ Y, a ⊑ y}
= {a | ∀y ∈ Y, a ∈ ↓y}
= ⋂{ ↓y | y ∈ Y }.

Therefore, X is a concept iff (α ∘ ω)X ⊆ X, or

⋂{ ↓y | y ∈ ↑(⨆ X)} ⊆ X.

Since ⋂{ ↓y | y ∈ ↑(⨆ X)} = ↓⨆ X, this is equivalent to saying that ↓⨆ X ⊆ X. Hence, X ⊆ P_{a} is a concept iff X = ↓⨆ X. In other words, concepts of (D, ⊒, D) are precisely the down-closed subsets of D generated by a single element.

Since for each x, y ∈ D, x ⊑ y iff ↓ x ⊆ ↓ y, the mapping x ⟼ ↓ x provides an order-isomorphism between D and LP.

A few special cases may be worth noting. First, D, being the down-closure of the top element, is always a concept. On the other hand, the empty set does not qualify as a concept because (α ∘ ω)∅ = {⊥}.

We now move to Scott’s notion of information system [Scott, 1982] which provide a concrete representation of Scott domains, with a logical flavor.

An information system consists of a set A of tokens, a subset Con of the set of finite subsets of A, denoted as Fin(A), and a relation ⊢ between Con and A. The subset Con on A is often called the consistency predicate, and the relation ⊢ is called the entailment relation. Both the consistency predicate and the entailment relation satisfy some routine axioms, made precise in the following definition.

4.2. Definition. An information system \underline{A} is a triple (A, Con, ⊢), where

• A is the token set,

• Con is the consistency predicate (Con ⊆ Fin(A) and ∅ ∈ Con),

• ⊢ is the entailment relation (⊢ ⊆ Con × A).

Moreover, the consistency predicate and entailment relation satisfy the following properties:

• X ⊆ Y & Y ∈ Con ⇒ X ∈ Con,

• a ∈ A ⇒ { a } ∈ Con,

• X ⊢ a & X ∈ Con ⇒ X ∪ { a } ∈ Con,

• a ∈ X & X ∈ Con ⇒ X ⊢ a,

• (∀b ∈ Y. X ⊢ b) & Y ⊢ c ⇒ X ⊢ c.

Although monotonicity for ⊢ is not explicitly given, it is a derivable property. The notion of consistency can be easily extended to arbitrary token sets by enforcing compactness, i.e., a set is consistent if every finite subset of it is consistent. By overloading notation, we write X ∈ Con when every finite subset of X is consistent; hence the consistency of finite sets is a more primitive notion.

An information system (A, Con, ⊢) induces an operator F : Con → Con, given as

F (X) := {a | ∃Y (Y ⊆^{fin} X & Y ⊢ a)}.

(Here, ⊆^{fin} stands for “finite subset of”, and X need not be finite.) It follows from the properties of an information system that F is a closure operator in a generalized sense: it is inflationary, monotonic, and idempotent. However, this is not strictly a closure operator because F is defined on Con, instead of P(A).

The information states, or simply states, of an information system are sets of the form F (X) with X ∈ Con, where Con is understood in the generalized sense to include infinite sets through the compactness condition. Information states consist of consistent, deductively closed (under ⊢) sets of tokens. The importance of information systems lies in the fact that they provide a logical representation of Scott domains.

4.3. Theorem. [Scott] For any information system \underline{A}, the collection of its information states under set inclusion forms a Scott domain. Conversely, every Scott domain is orderisomorphic to the partial order of information states of some information system.

A Chu space determines an information system in the following way.

4.4. Definition. For a given Chu space P = (P_{o}, ⊧_{P} , P_{a}), define a system

(A_{P} , Con_{P} , ⊢_{P})

with A_{P} = P_{a}, X ⊢_{P} a if a ∈ α_{P} ∘ ω_{P} (X), and a consistency predicate Con_{P} for which every subset of P_{a} is consistent.

The intuition is that the entailment relation X ⊢_{P} a should satisfy the property that every model of X is a model of a, where a model here corresponds naturally to an object, or a member of P_{o} (see [Zhang, 2003] and [Hitzler and Zhang, 2004] for further details).

4.5. Proposition. Given a Chu space P = (P_{o}, ⊧_{P} , P_{a}), the triple

(A_{P} , Con_{P} , ⊢_{P})

is an information system.

The proof goes by checking each axiom of an information system, which is straightforward. The interesting question is whether a set of attributes is a concept if and only if it is an information state.

4.6. Theorem. Given a Chu space P = (P_{o}, ⊧_{P} , P_{a}) with P_{a} a finite set, X ⊆ P_{a} is a concept if and only if it is a state of the derived information system (A_{P} , Con_{P} , ⊢_{P}).

Proof. Suppose X is a concept. We show that it is deductively closed, i.e., for each a and each Y ⊆ X, Y ⊢_{P} a implies a ∈ X. Since X is a concept, we have α_{P} ∘ ω_{P} (X) = X. Suppose Y ⊆ X and Y ⊢_{P} a. Since α_{P} ∘ ω_{P} (Y) ⊆ α_{P} ∘ ω_{P} (X) and α_{P} ∘ ω_{P} (X) = X, we get a ∈ X.

For the other direction, suppose T is a deductively closed set, i.e., for any a ∈ P_{a}, T ⊢_{P} a implies a ∈ T. This implies that α_{P} ∘ ω_{P} (T) ⊆ T, and T is a concept.

The finiteness of P_{a} is needed for the second part of the proof. Every concept is a deductively closed set, but an infinite deductively closed set is not necessarily a concept, as our example below shows. Since finiteness is a severe restriction theoretically, this restriction represents a conceptual mismatch, rather than a technical shortcoming.

Note that, by the Representation Theorem 4.1, any information system (A, Con, ⊢) with a trivial consistency predicate determines a Chu space which determines an isomorphic concept lattice. A simpler and more direct construction exists. The required Chu space can be defined as follows. We can take information states x as objects, and tokens a ∈ A as attributes, and let x ⊧ a iff a is a member of x. With respect to this Chu space, the extension of a set of attributes B is the set [[B]] := {x | B ⊆ x}, where x is an information state; the intension of [[B]] is the set {a | ∀x ∈ [[B]], a ∈ x}. The requirement that B matches the intension of the extension of B can be stated precisely as B = {a | ∀x ∈ [[B]], a ∈ x}, which amounts to the statement that B is an information state of the original information system (A, Con, ⊢), observe that the information state generated by B is precisely the intension of the extension of B.

Note also that the correspondence between information states and formal concepts breaks down in the infinite case because information systems represent Scott domains, which are algebraic; on the other hand, concept lattices, though bounded complete, need not be algebraic, as the following example shows.

4.7. Example. Consider the lattice (Z ∪ {∗, ⊤, ⊥}, ⊑), where Z is the set of integers augmented with top (⊤ - positive infinity) and bottom (⊥ - negative infinity), under the usual order. Further, ∗ is an additional element on the side with ⊥ ⊏ ∗ ⊏ ⊤, with ∗ incomparable with any member in Z. This lattice is not algebraic even if one turns it up side down. We follow the construction given in the proof of Theorem 4.1 to construct a Chu space whose concepts form a lattice isomorphic to this lattice.

According to the proof of Theorem 4.1, we obtain the Chu space given by the following table

P ↑⊤ ↑⊥ ↑∗ ↑0 ↑1 ↑2 ⋯ ↑−1 ↑−2 ↑−3 ⋯
⊤ × × × × × × ⋯ ×  ×  × ⋯
⊥  ×  ⋯  ⋯
∗  × ×  ⋯  ⋯
0  ×  ×  ⋯ ×  ×  × ⋯
1  ×  × ×  ⋯ ×  ×  × ⋯
2  ×  × × ×  ×  ×  × ⋯
⋮  ⋮  ⋮ ⋮ ⋮ ⋮  ⋮  ⋮  ⋮ ...
-1  ×  ×  ×  × ⋯
-2  ×  ×  × ⋯
-3  ×  × ⋯
⋮  ⋮  ⋮ ⋮ ⋮ ⋮  ⋮  ⋮  ⋮ ...

With respect to its corresponding information system, note that for any finite subset X of { ↑i | i ≥ 0} ⊆ P_{a}, we do not have X ⊢ ∗ since ∗ is not a member in α∘ω(X). However,

∗ is a member of α ∘ ω{ ↑i | i ≥ 0} and hence it is a member of the concept generated by { ↑i | i ≥ 0}. In other words, we need “infinitary” implication { ↑i | i ≥ 0} ⊢ ∗ to capture a concept, but this cannot be captured by finitary entailment relations. In a sense, compactness fails here.

We can also see this from the proof of Theorem 4.1. While ∗ is a member of

↓⋂{ ↑i | i ≥ 0} = ↓⊤,

⊤ ∉ ↓(⋂ X) for any finite subset X of { ↑i | i ≥ 0}.

One can further observe that the composition α ∘ ω, though monotonic, is not continuous.

We mention without proof a few conditions under which the concept lattice is algebraic.

4.8. Proposition. For any context P, its corresponding concept lattice LP is algebraic if and only if α_{P} ∘ ω_{P} is continuous. (See [Gierz et al 2003], Proposition I-4.13 as well.)

The function α_{P} ∘ ω_{P} is continuous if there are no infinitely-checked columns.

4.9. Proposition. For any context P, α_{P} ∘ ω_{P} is continuous if for each a ∈ P_{a}, ω_{P} {a} is a finite set.

4.10. Proposition. For any context P, α ∘ ω is continuous if the set {ωY | Y finite} is well-founded.

4.11. Proposition. For any context P, α ∘ ω is continuous iff for any b ∈ P_{a} and any u ⊆ P_{a}, b ∈ (α∘ω)u implies b ∈ (α∘ω)X for some finite subset X of u. (See also [Ganter and Wille, 1999], p. 33f.)

5. Towards data-mining applications

Many data sets are, or can be put into the form of, Chu spaces. In this section we discuss some of the implications of our earlier results in the area of data-mining and knowledge discovery. Pfaltz and his collaborators [Pfaltz and Taylor, 2002, Pfaltz and Taylor, 2002] have done some interesting work on the minimal representation in concept lattices.

The first observation, although simple, is helpful. It is a well-known fact in formal concept analysis.

5.1. Proposition. Let P = (P_{o}, ⊧_{P} , P_{a}) be a Chu space. For each object x ∈ P_{o}, the set of its attributes α_{P} {x} is a concept.

This gives immediate structural information about concept lattices: the set of attributes collected from each row always forms a concept and, moreover, any intersection of a subset of these concepts forms another concept.

5.2. Proposition. Let P = (P_{o}, ⊧_{P} , P_{a}) be a Chu space, and let Chu space Q = (Q_{o}, ⊧_{Q} , Q_{a}) be a structure obtained from P by adding a row without changing the attribute set, i.e.,

• Q_{o} = P_{o} ∪ {n} where n is the “new” object,

• P_{a} = Q_{a},

• ⊧_{P} =⊧_{Q} when restricted to P_{o} × P_{a}.

Then the function pair (f, g) with f the identity function on Q_{a} and g the injection P_{o} → Q_{o} with x ↦ x is a Chu mapping from Q to P.

This is a more precise statement of Example 3.2. The upshot of it is that since f is surjective and g is injective, we have, by Proposition 3.11, item 2, Y is a concept if g^{+}(Y) is a concept, for any Y ⊆ P_{o}. We can state this more precisely in terms of attribute concepts, as follows.

5.3. Proposition. Let P = (P_{o}, ⊧_{P} , P_{a}) and Q = (Q_{o}, ⊧_{Q}, Q_{a}) be Chu spaces as given in the previous proposition: Q extends P by a row. Then every attribute concept A of P is also an attribute concept of Q.

Of course, transitivity allows us to generalize this result to the case when Q is an extension of P by adding rows, and this provides the foundation for an iterative, “online” construction of concept lattices when the attribute set is fixed (which is usually the case), but new data keep coming in, not all at once.

5.4. A closure-system centric view. The closure-system point of view is equivalent to that of Galois connections for concept lattices. However, closure systems sometimes provide a more straightforward theoretic basis for data-mining algorithms.

5.5. Lemma. Let A be a set. Then the set of all closure systems over A forms a (meta) closure system over P(A).

For closure systems C_{1} and C_{2} over A, let C := C_{1} ∩ C_{2}. One can check that C is again a closure system over A. In general, intersection preserves closure systems, and the intersection of an empty collection of closure systems over A is the largest closure system P(A) over A.

As an immediate consequence of this lemma, any subset of the powerset P(A) generates a closure system.

5.6. Lemma. Every subset of P(A) generates a closure system over A, which is the smallest closure system containing the starting subset.

We can then view concept lattices as a generated closure system.

5.7. Proposition. Let P = (P_{o}, ⊧_{P} , P_{a}) be a Chu space. Then its concept lattice LP is isomorphic to the closure system generated by the set {α_{P} {x} | x ∈ P_{o}}. Dually, LP is anti-isomorphic to the closure system generated by the set {ω_{P} {p} | p ∈ P_{a}}.

This brings flexibility for procedures for constructing concept lattices. For example, one can partition P_{o} into A ∪ B = P_{o}, find the closure system generated by {α_{P} {x} | x ∈ A} and {α_{P} {x} | x ∈ B}, respectively, and then find the closure system generated by the union of the two closure systems. This view provides an easy-to-understand, straightforward way to justify the correctness of many FCA related algorithms in the literature (for which correctness proofs are often omitted).

6. Approximable concepts

A fundamental idea of domain theory is partial information and successive approximation. Example 4.7 indicates that the notion of formal concept as defined in FCA does not have an appropriate structure to capture approximation.

To arrive at a suitable notion of approximable concept, let us recall the notion of affirmable predicate [Vickers, 1989]. A predicate P is called affirmable if it takes finite amount of time (computation) to confirm an object to have property P, if it is indeed the case. Moreover, P is completely determined by the set of its positive finitary “witnesses”.

Being a formal concept in the sense of Definition 3.4 is not an affirmable property because of the infinite nature of the equality α(ω(A)) = A. This is the reason why Theorem 4.6 only works for finite attribute sets.

The main purposes of this section are (1) to introduce the notion of approximable concept, (2) to provide a representation theorem for complete algebraic lattices similar to Theorem 4.1, and (3) to relate approximable concepts and information states in a similar sense to Theorem 4.6 to its fullest extent. It should be noted that on top of page 34 in [Ganter and Wille, 1999], a similar condition to the one given below in Definition 6.1 is discussed as a sufficient condition for a concept lattice to be algebraic, although its full ramifications were not explored.

6.1. Definition. With respect to a Chu space P = (P_{o}, ⊧_{P} , P_{a}) and two associated functions

α : P(P_{o}) → P(P_{a}) with X ⟼ {a | ∀x ∈ X x ⊧_{P} a}
ω : P(P_{a}) → P(P_{o}) with Y ⟼ {o | ∀y ∈ Y o ⊧_{P} y}

a subset A ⊆ P_{a} is called an approximable concept if for every finite subset X ⊆ A, we have α(ω(X)) ⊆ A.

It can be seen immediately that finite approximable concepts and finite concepts coincide because α ∘ ω is an inflationary, monotonic operator. While each concept is also an approximable concept, not every approximable concept is a concept in the sense of Definition 3.4. For example, in Example 4.7 the set

{ ↑i | i ∈ Z} ∪ { ↑⊥}

is an approximable concept but not a concept according to Definition 3.4.

6.2. Definition. A complete algebraic lattice (henceforth algebraic lattice) is a partial order which is both a complete lattice and an algebraic dcpo.

Here is our main representation theorem with respect to approximable concepts.

6.3. Theorem. [Representation Theorem] For any Chu space P, the set of its approximable concepts AP under inclusion forms an algebraic lattice. Conversely, for every algebraic lattice D, there is a Chu space P such that D is order-isomorphic to AP.

Proof. We first show that the set of approximable concepts AP for any Chu space P forms an algebraic lattice. To show that AP is a complete lattice it suffices to show that AP is a closure system. Given any subset T ⊆ AP, it suffices to show that ⋂ T is an approximable concept. Suppose X is a finite subset of ⋂ T. Then X ⊆ t for each t ∈ T. Since each t ∈ T is an approximable concept, we have α ∘ ω(X) ⊆ t for each t ∈ T. This implies α ∘ ω(X) ⊆ ⋂ T and so ⋂ T is an approximable concept.

To show that AP is algebraic, note that α ∘ ω(X) is a compact element for each finite X. To see this, let {A_{i} | i ∈ I} be a directed set of approximable concepts such that

α ∘ ω(X) ⊆ ⋃_{i∈I} A_{i}.

By Lemma 2.8, X ⊆ α ∘ ω(X). Therefore X ⊆ ⋃_{i∈I} A_{i}. Since X is finite and {A_{i} | i ∈ I} directed, X ⊆ A_{k} for some k ∈ I. But A_{k} is an approximable concept; therefore α ∘ ω(X) ⊆ A_{k} by Definition 6.1.

For any approximable concept T, we have

T = ⋃{α ∘ ω(X) | X ⊆^{fin} T }

where {α ∘ ω(X) | X ⊆^{fin} T } is clearly a directed set. Therefore, any approximable concept is the directed sup of a set of compact approximable concepts. This finishes the algebraicity part.

For the second part, suppose (D, ⊑) is an algebraic lattice. Define the Chu space P = (P_{o}, ⊧, P_{a}), with P_{o} = D and P_{a} = κ(D), where κ(D) stands for the set of compact elements of D. Further, let x ⊧ b iff b ⊑ x. We want to show that AP is order-isomorphic to (D, ⊑).

First note that for any X ⊆ P_{a}, we have

ωX = {o ∈ D | ∀x ∈ X, o ⊧ x}
= {o ∈ D | ∀x ∈ X, x ⊑ o}
= {o ∈ D | ⨆ X ⊑ o}
=↑_{D} (⨆ X).

On the other hand,

αY = {a ∈ κ(D) | ∀y ∈ Y, y ⊧ a}
= {a ∈ κ(D) | ∀y ∈ Y, a ⊑ y}
= {a ∈ κ(D) | ∀y ∈ Y, a ∈↓_{κ(D)} (y)}
= ⋂{↓_{κ(D)} (y) | y ∈ Y }.

Therefore, x ⊆ P_{a} is an approximable concept iff (α ∘ ω)(X) ⊆ x for any finite subset X ⊆^{fin} x, or

⋂{↓_{κ(D)} (y) | y ∈↑_{D} (⨆ X)} ⊆ x

for each X ⊆^{fin} x. Since

⋂{↓_{κ(D)} (y) | y ∈↑_{D} (⨆ X)} =↓_{κ(D)} (⨆ X),

this is equivalent to saying that x is a downward closed, directed subset of compact elements of D. A downward closed, directed subset is called an ideal. Hence, a subset P_{a} is an approximable concept if and only if it is an ideal. Since an algebraic domain is isomorphic to the ideal completion of the partial order of its compact elements [Amadio and Curien, 1998] through the isomorphism

d ⟼ {a ∈ κ(D) | a ⊑ d},

AP is isomorphic to D, as required.

Even though it is not needed in the proof, we note that all compact approximable concepts are of the form α ∘ ω(X) for some finite attribute set X.

The next result carries Theorem 4.6 from the finite case to arbitrary Chu spaces.

6.4. Theorem. Given a Chu space P = (P_{o}, ⊧_{P} , P_{a}), a subset x ⊆ P_{a} is an approximable concept if and only if it is a state of the derived information system (A_{P} , Con_{P} , ⊢_{P}) according to Definition 4.4.

Proof. Suppose x is an approximable concept. We show that it is deductively closed, i.e., for each a and each Y ⊆^{fin} x, Y ⊢_{P} a implies a ∈ x. Since x is an approximable concept and Y a finite subset of x, we have α_{P} ∘ ω_{P} (Y) ⊆ x. By definition, Y ⊢_{P} a means a ∈ α_{P} ∘ ω_{P} (Y) and therefore a ∈ X.

For the other direction, suppose y is a deductively closed set, i.e., for any finite subset X ⊆^{fin} y and a ∈ P_{a}, X ⊢_{P} a implies a ∈ y. To show that y is an approximable concept amounts to showing that for any finite subset X ⊆^{fin} y, α_{P} ∘ ω_{P} (X) ⊆ y. But because α_{P} ∘ ω_{P} (X) = {a | X ⊢_{P} a}, the deductive closeness of y gives rise to α_{P} ∘ ω_{P} (X) ⊆ y, as needed.

There is a dual notion of approximable concept based on objects rather than attributes.

6.5. Definition. With respect to a Chu space P = (P_{o}, ⊧_{P} , P_{a}), a subset O ⊆ P_{o} is called an approximable (object) concept if for every finite subset Q ⊆^{fin} O, we have ω(α(Q)) ⊆ O. Write OP for the set of approximable object concept of P.

By symmetry and Lemma 2.8, the following observations are immediate.

6.6. Lemma. For any Chu space P, we have

1. the set of its approximable object concepts OP under inclusion forms an algebraic lattice,

2. conversely, for every algebraic lattice D, there is a Chu space P such that D is order-isomorphic to OP,

3. for any subset A ⊆ P_{a}, ω(A) is an approximable object concept, and

4. for any subset O ⊆ P_{o}, α(O) is an approximable attribute concept.

Unlike the standard case, the relationship between the lattice of approximable attribute concepts and the lattice of approximable object concepts is more complicated. They are not necessarily reverse isomorphic to each other in the infinite case, simply because the order-reverse of an algebraic lattice need not be algebraic.

The next result seems to be the best of what we can say about the relation between AP and OP.

6.7. Theorem. With respect to a Chu space P = (P_{o}, ⊧_{P} , P_{a}), the mappings ω : AP → OP and α : OP → AP give rise to a Galois connection such that α ∘ ω(x) = x for all x ∈ κ(AP) and ω ∘ α(y) = y for all y ∈ κ(OP).

The proof is standard and uses the fact that x ∈ κ(AP) if and only if x = α ∘ ω(X) for some finite set X (and similarly for κ(OP)).

It should be informative to compare this relation between AP and OP and the relation between attribute concepts (LP_{a}, ⊆) and object concepts (LP_{o}, ⊇), for which the pair of functions α, ω provide equalities α ∘ ω(x) = x and ω ∘ α(y) = y for all x ∈ LP_{a} and y ∈ LP_{o}.

7. A cartesian closed category of approximable concept structures

We know from the previous section that lattices derived from approximable concepts are exactly the complete algebraic ones and every (classical) formal concept is approximable (on an individual basis). Furthermore, in cases where the formal contexts are finite, approximable concepts and formal concepts coincide. From a categorical viewpoint, this supplies the object part of a functor; a main contribution of [Hitzler and Zhang, 2004] is the introduction of an appropriate notion of morphisms on formal contexts and the proof that the following three categories are equivalent:

1. the category of formal contexts and context morphisms,

2. the category of complete algebraic lattices and Scott continuous functions, and

3. the category of information systems and approximable mappings.

This implies that the category of formal contexts and context morphisms is cartesian closed, and as a result a rich collection of constructions including product and function space is immediately made possible. The equivalence between the category of complete algebraic lattices with Scott continuous functions and the category of consistent information systems and approximable mappings is a folklore; for a proof see [Shen, 200x].

The rest of this section provides a brief account of some of the relevant results from [Hitzler and Zhang, 2004] and [Hitzler-Kröetzsch-Zhang, 2006].

7.1. Definition. [Context morphism [Hitzler and Zhang, 2004]] Given formal contexts P = (P_{o}, ⊧_{P} , P_{a}) and Q = (Q_{o}, ⊧_{Q}, Q_{a}), a context morphism ⇾_{P Q} = ⇾ from P to Q is a relation ⇾ ⊆ Fin(P_{a}) × Fin(Q_{a}), such that the following conditions are satisfied for all X, X′, Y_{1}, Y_{2} ∈ Fin(P_{a}) and Y, Y′ ∈ Fin(Q_{a}):

1. ∅ ⇾ ∅,

2. X ⇾ Y_{1} and X ⇾ Y_{2} imply X ⇾ Y_{1} ∪ Y_{2},

3. X′ ⊆ α_{P} (ω_{P} (X)) and X′ ⇾ Y′ and Y ⊆ α_{Q} (ω_{Q}(Y′)) imply X ⇾ Y.

Formal contexts together with context morphisms constitute a category Cxt. The relation ι_{P} defined by Xι_{P} Y iff Y ⊆ α(ω(X)) defines the identity context morphism.

The definition of context morphism above paraphrases that of approximable mappings, which are morphisms for Scott’s category ISys of on information systems [Scott, 1982]: for information systems \underline{A} and \underline{B}, an approximable mapping ⇝_{AB} = ⇝ from \underline{A} to \underline{B} is a relation ⇝ ⊆ Fin(A) × Fin(B), such that the following conditions are satisfied for all X, X′, Y_{1}, Y_{2} ∈ Fin(A) and Y, Y′ ∈ Fin(B):

1. ∅ ⇝ ∅,

2. X ⇝ Y_{1} and X ⇝ Y_{2} imply X ⇝ Y_{1} ∪ Y_{2},

3. X ⊢_{A} X′ and X′ ⇝ Y′ and Y′ ⊢_{B} Y imply X ⇝ Y.

For a formal context P = (P_{o}, ⊧, P_{a},), let IS(P) denote the associated information system given in Definition 4.4. Let P = (P_{o}, ⊧_{P} , P_{a}) and Q = (Q_{o}, ⊧_{Q}, Q_{a}) be formal contexts, and let ⇾ be a context morphism. Let IS(P) = (P_{a}, ⊢_{P}) and IS(Q) = (Q_{a}, ⊢_{Q}). By defining IS(⇾_{P Q}) = ⇝ ⊆ Fin(P_{a}) × Fin(Q_{a}) by setting X ⇝ Y iff X ⇾ Y we obtain ⇝ as an approximable mapping. Moreover, IS is a functor from Cxt to ISys.

One can prove the following.

7.2. Theorem. The functor IS : Cxt → ISys is full and faithful, and each object A in ISys is isomorphic to IS(P) for some object P in Cxt.

By a theorem of Mac Lane (Theorem 1, page 91 in [Mac Lane, 1971]), the categories Cxt and ISys are equivalent. Since ISys is cartesian closed, Cxt is cartesian closed as well. For further details see [Hitzler and Zhang, 2004], where the categorical equivalence is formulated in its original definition using two functors.

8. Conclusions and future work

This paper has brought three relatively independent areas together: Chu spaces, Formal Concepts, and Domains. The formulation and results provided here serve as a basis for many opportunities for further development, in a number of directions. For example (in no particular order):

1. Attributes in real-world data rarely come without some preliminary structural information. For example, one attribute many be in conflict with another, for scientific or logical reasons (case in point: “four-legged animal” and “two-legged animal”). In general, objects having all the attributes are not interesting, even if they exit. It would be beneficial to explore a notion of formal concept with the constraint of a consistency predicate, in the spirit of information systems. This will bring concept structures to cpos without necessarily a top element, such as bounded complete cpos, if not Scott domains.

2. A rich collection of constructions on Chu spaces exist, for the purpose of modeling linear logic. It would be interesting to see which of those constructions can be useful for exploring the structure of data, and how and if concepts are preserved with respect to these constructions. Among domain-theoretic models of linear logic, we would like to point to [Huth, 1995], where monoidal closed categories inside bounded complete dcpos and sup-preserving maps have been carefully studied. It should be relatively straightforward to formulate monoidal closed categories inside the categories Cxt and ISys based work reported here.

3. In general, logical systems for reasoning about concept structures may be profitably developed using a similar approach as “logic of domains”, or semantics-based proof systems (see, for example, [Abramsky and Jung, 1994, Coquand and Zhang, 2000, Johnstone, 1982, Vickers, 1989, Zhang, 1991]). The information-flow theory of Barwise [Barwise and Seligman, 1997] has already taken a step in this direction.

4. Last and maybe most, there is an explosion of research on ontology and ontological engineering over the last couple of years, sparked by the Semantic Web initiative [Berners-Lee, et. al, 2001]. There seems to be a great deal of potential in exploring FCA, information systems, and Chu constructions in this context, especially with respect to the understanding of ontological structures and automated learning of ontology from the Web.

Acknowledgment. Thanks go to Pascal Hitzler and John Pfaltz for stimulating discussions related to formal concept analysis, and to Austin Melton for pointers to Galois connections. We would also like to thank Markus Kröetzsch for proof-reading and for bringing up a couple of additional related references to our attention.

References

S. Abramsky and A. Jung, Domain theory. In: Handbook of Logic in Computer Science (S. Abramsky, D. Gabbay, and T. S. E. Maibaum, eds.), Vol. 3, Clarendon Press, 1994.

R. Amadio and P.-L. Curien, Domains and Lambda-Calculi. Cambirdge University Press, 1998.

M. Barr. *-Autonomous categories, with an appendix by Po Hsiang Chu. Lecture Notes in Mathematics, Vol. 752, Springer-Verlag, 1979.

M. Barr. *-Autonomous categories and linear logic. Mathematical Structures in Computer Science, Vol. 1, pp. 159-178, 1991.

J. Barwise and J. Seligman. Information Flow: the logic of distributed systems. Cambridge Tracts in TCS, Vol. 44, 1997.

T. Berners-Lee, J. Hendler, O. Lassila. The Semantic Web. Scientific American, Vol. 284, pp. 34-43, 2001.

G. Birkhoff. Lattice Theory. AMS Colloquium Publications, Vol. 25, 1940.

T. Coquand and G. Q. Zhang, Sequents, frames, and completeness, Computer Science Logic 2000 (P. Clote and H. Schwichtenberg, eds.), Lecture Notes in Computer Science, Vol. 1862, pp. 277-291, 2000.

B. Davey and H. Priestley. Introduction to Latices and Order (2nd edition). Cambridge University Press, 2002.

M. Erné. General Stone duality. Topology and Its Applications, Vol. 137, pp. 125-158, 2004.

B. Ganter and R. Wille. Formal Concept Analysis. Springer-Verlag, 1999.

G. Gierz, K. Hofmann, K. Keimel, J. Lawson, M. Mislove, D. Scott. Continuous Lattices and Domains, Cambridge University Press, 2003.

C. Gunter and D. Scott. Semantic domains. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Vol. B, pp. 633-674, Elsevier, 1990.

P. Hitzler and M. Wendt. Formal concept analysis and resolution in algebraic domains. In: Aldo de Moor and Bernhard Ganter (Eds.): Using Conceptual Structures - Contributions to ICCS 2003. Shaker Verlag, Aachen, Germany, pp. 157-170.

P. Hitzler, Default Reasoning over Domains and Concept Hierarchies. In: Proceedings of the 27th German conference on Artificial Intelligence, KI’2004, Ulm, Germany, September 2004, Lecture Notes in Artificial Intelligence. To appear.

P. Hitzler and G.-Q. Zhang. A cartesian closed category of approximable concept structures. In Pfeiffer and Wolff (eds.), Proceedings of the International Conference on Conceptual Structures, Huntsville, Alabama, USA, July 2004. Lecture Notes in Artificial Intelligence, 2004, to appear.

P. Hitzler, M. Kröetzsch, and G.-Q. Zhang. A categorical view of algebraic lattices in formal concept analysis, Fundamenta Informaticae, Vol. 74, pp. 1 - 29, 2006.

M. Huth. A maximal monoidal closed category of distributive algebraic domains. Information and Computation, Vol. 116, pp. 10-25, 1995.

P. Johnstone. Stone Spaces. Cambridge University Press, 1982.

F. Lamarche. From Chu spaces to cpos. Theory and Formal Methods of Computing 94, Imperial College Press, pp. 283-305, 1994.

J. McDill, A. Melton, and G. Strecker. A category of Galois connections. Lecture Notes in Computer Science, Vol. 283, pp. 290-300, 1987.

A. Melton, D. Schmidt, and G. Strecker. Galois connections and computer science applications. Lecture Notes in Computer Science, Vol. 240, pp. 299-312, 1985.

APPROXIMABLE CONCEPTS, CHU SPACES, AND INFORMATION SYSTEMS 101

A. Melton, B. Schröder, and G. Strecker. Lagois connections – a counterpart to Galois connections. Theoretical Computer Science, Vol. 136, pp. 79-107, 1994.

S. Mac Lane. Categories for the working mathematician. Springer-Verlag, 1971.

J. Pfaltz and C. Taylor. Scientific knowledge discovery through iterative transformation of concept lattices. SIAM Workshop on Discrete Math. and Data Mining, Arlington, VA, U.S.A., 2002.

J. Pfaltz and C. Taylor. Closed set data mining of biological data. BIOKDD 2002 (2nd Workshop on Data Mining in Bioinformatics), Edmonton, July, 2002.

G. Plotkin. Notes on Domains (Pisa Notes), University of Edinburgh, 1983. Available at:

http://www.dcs.ed.ac.uk/home/gdp/publications/

V. Pratt. Higher dimensional automata revisited. Math. Structures Comput. Sci. Vol. 10, pp. 525-548, 2000.

V. Pratt. Chu spaces from the representational viewpoint. Ann. Pure Appl. Logic, Vol. 96, pp. 319-333, 1999.

V. Pratt. Towards full completeness of the linear logic of Chu spaces. Mathematical foundations of programming semantics (Pittsburgh, PA, 1997), Electronic Notes in Theoretical Computer Science, Vol. 7, 18 pp., 1997.

V. Pratt. The Stone gamut: a coordinatization of mathematics. Proceedings of 10th Annual Symposium on Logic in Computer Science, pp. 444-454, 1995.

V. Pratt. Chu spaces and their interpretation as concurrent objects. Lecture Notes in Comput. Sci. Vol. 1000, pp. 392-405, 1995.

V. Pratt. Chu spaces as a semantic bridge between linear logic and mathematics. Theoretical Computer Science, Vol. 294, pp. 439-471, 2003.

W. Rounds and G.-Q. Zhang. Clausal logic and logic programming in algebraic domains. Information and Computation, Vol. 171, pp. 183-200, 2001.

D. S. Scott. Domains for denotational semantics, Lecture Notes in Computer Science, Vol. 140, pp. 577-613, 1982.

R.A.G. Seely. Linear logic, *-autonomous categories and cofree algebras. In Categories in Computer Science and Logic, Contemporary Mathematics, Vol. 92, pp. 371-382, 1989.

G. Shen. Formal Concept Analysis: theory and applications. PhD Thesis, Department of Electrical Engineering and Computer Science, Case Western Reserve University, 200x.

S. Vickers. Topology via Logic, Cambridge University Press, 1989.

G. Winskel. The Formal Semantics of Programming Languages. MIT Press, 1993.

G.-Q. Zhang. Logic of Domains, Birkhauser, Boston, 1991.

G.-Q. Zhang. Chu spaces, concept lattices, and domains. In: Proceedings of the 19th Conference on the Mathematical Foundations of Programming Semantics, March 2003, Montreal, Canada. Electronic Notes in Theoretical Computer Science Vol. 83, 2004, 17 pages.

Department of Electrical Engineering and Computer Science Case Western Reserve University Cleveland, OH 44106, U. S. A.

Email: gqz@eecs.cwru.edu

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/17/5/17-05.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh,

rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: mbarr@barrs.org

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com

Ezra Getzler, Northwestern University: getzler(at)math(dot)northwestern(dot)edu

Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca