Minimum matrix representation of closure operations (Q1065561): Difference between revisions

Let a be a column of the matrix M and A be a set of its columns. We say that A implies a iff M contains no two rows equal in A but different in a. It is easy to see that if \(L_ M(A)\) denotes the columns implied by A, then \(L_ M(A)\) is a closure operation. We say in this case that M represents this closure operation. Let s(L) denote the minimum number of rows of the matrices representing a given closure operation L. The paper contains three types of results. In section 3 s(L) is determined for some special closure operations. In section 4, \(s(L_ 1\times L_ 2)\) is given in terms of \(s(L_ 1)\) and \(s(L_ 2)\). Finally closure operations L with large s(L) are considered.