Mathematics Computer Science

We discuss Wille's formal concept analysis and apply learnability results to this framework. A context is an incidence structure (X, A, I). For any C CX, I (C) denotes the members of A incident with C, and I (D) is dually defined for D C A. A formal concept is a pair (C, D) with C Ç X and D CA such that I (C)= D and I (D)= D and I (D)= C. Here,-C is called the extent of the formal concept. We briefly describe a relationship between formal concepts and monomials. The space of all formal concept extents (in the context) is denoted E (X, A, 1) and its VC dimension is called the dimension of the context. We relate the dimension of a context to its structure, defining types of boundedness properties that a context can have. In particular, we define almost uniformly bounded