Морозов А. С., Львова М. А.
О вычислимых формальных понятиях в вычислимых формальных контекстах

Вводятся и изучаются вычислимые формальные контексты и вычислимые формальные понятия в них. Даны примеры вычислимых формальных контекстов, в которых вычислимые понятия не образуют решетки. Изучаются сложностные вопросы формальных понятий в вычислимых формальных контекстах. В частности, сформулированы условия, достаточные для того, чтобы вычислимость или невычислимость формального понятия следовала из его теоретико-решеточных свойств. Доказана теорема плотности, показывающая, что в топологии Кантора каждое формальное понятие может быть аппроксимировано вычислимыми понятиями. Показано, что не все формальные понятия имеют теоретико-решеточные аппроксимации в виде точных верхних или нижних граней семейств вычислимых формальных понятий.

Morozov A. S.,  L’vova  M. A.
On computable formal concepts in computable formal contexts

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.

Полный текст статьи / Full texts:

• PDF file (205 KB)
• PostScript file (920 KB)