Декомпозиционный подход к исследованию формальных контекстов

Исследуется $\#$P-полная задача нахождения всех формальных понятий заданного контекста и предлагается декомпозиционный метод её решения. В качестве частей разложения предлагается использовать фрагменты исходного контекста, названные боксами. Доказано, что разделение контекста на боксы «безопасно» относительно формальных понятий: при декомпозиции ни одно формальное понятие не теряется и не появляются новые формальные понятия. Доказано, что число боксов, возникающих на каждой итерации разложения, равно числу единичных элементов $0,1$-матрицы, представляющей исходный формальный контекст. Предлагается уменьшать число боксов на каждой отдельной итерации процесса декомпозиции с помощью построения взаимно непересекающихся цепей боксов. Приводятся результаты вычислительных экспериментов, свидетельствующие о существенном повышении производительности алгоритмов нахождения всех формальных понятий при применении предлагаемого декомпозиционного метода.