×

On computable formal concepts in computable formal contexts. (Russian, English) Zbl 1164.03344

Sib. Mat. Zh. 48, No. 5, 1083-1092 (2007); translation in Sib. Math. J. 48, No. 5, 871-878 (2007).
Summary: We introduce and study the notions of computable formal context and computable formal concept. We give some examples of computable formal contexts in which the computable formal concepts fail to form a lattice and study the complexity aspects of formal concepts in computable contexts. In particular, we give some sufficient conditions under which the computability or noncomputability of a formal concept could be recognized from its lattice-theoretic properties. We prove the density theorem showing that in a Cantor-like topology every formal concept can be approximated by computable ones. We also show that not all formal concepts have lattice-theoretic approximations as suprema or infima of families of computable formal concepts.

MSC:

03D45 Theory of numerations, effectively presented structures
68T30 Knowledge representation
PDFBibTeX XMLCite
Full Text: EuDML EMIS