Проверка соответствия ориентированного графа алгебраической решётке

Рассмотрена проблема проверки изоморфности ориентированного графа диаграмме некоторой решётки. Исследованы три типа конечных решёток, используемых в моделях разграничения доступа. Построен алгоритм проверки соответствия ориентированного графа прямому произведению решётки подмножеств и линейной решётки. Алгоритм основан на анализе структуры двух множеств: множества вершин, покрывающих ровно одну вершину, и множества атомарных вершин. Доказано, что вычислительная сложность алгоритма проверки не превосходит $\mathrm O(n^3)$.