The check of the correspondence of the directed graph to the algebraic lattice | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 41. DOI: 10.17223/20710410/41/6

The isomorphism check problem for a directed graph and a lattice diagram is considered in this paper. Three specific finite lattices used in the access control models are investigated. Special attention is paid to MLS-lattice which is the Cartesian product of the lattice of subsets and the linear lattice. Necessary and sufficient conditions for the isomorphism of a finite lattice S to the MLS-lattice are found. For the lattice S, these conditions define some limitations to the number of all nodes, of atomic nodes, and of nodes covered by each element of the lattice S. An algorithm which checks the correspondence of the directed graph to the MLS-lattice is offered. This algorithm is based on the structure of two sets: the set of the nodes which cover exactly one node and the set of the atomic nodes. The following conditions are checked: the number of nodes of the directed graph n = 2ⁿⁱn₂; all nodes of the directed graph cover at least two others except the nodes x₁,... , x_ni, t, t₁,... , t_n2-1, wherein t is an outlet of the directed graph; the nodes x₁,..., x_ni, t₁,..., t_n2-1 cover exactly one node; the nodes x₁,..., x_ni, t₁ are atomic nodes; the nodes t_n2-1,..., t₁, t form a chain t_n2-1 >- ... >- t₁ >- t in which the nodes successively cover each other. We prove that the computing complexity of this algorithm does not exceed O(n³).