An Artificial Neural Approach to the Decomposition Problem

The goal of this thesis is to develop an artificial neural approach toward addressing the intractability involved with the decomposition problem. The search for the lattice of substitution property (s. p.) partitions essential to decompositions is cast into the framework of constraint satisfaction. An artificial neural network is developed to provide solutions by performing optimization of a mathematically derived objective function over the problem space. The issue of transitivity is verified to belong to a class of problems beyond the scope of solvability for conventional quadratic-order constraint satisfaction neural networks. A theorem is stated and proved establishing that third-order correlations must be extracted by a neural network to generate s. p. partitions. A formalized method for the construction of constraint satisfaction neural networks is presented by exploiting abstract laws from relational and Boolean algebras. It is shown that a third-order Hopfield network fails to solve the s. p. partition problem, while impressive results are obtained by using a Boltzmann machine employing simulated annealing. Convergence to global solution states in large-sized problem domains have been obtained at fast rates by manipulation of the degenerate ground state characteristic of the network objective function.