Repository | Book | Chapter

In the last few years, several publications discussed a new method of matrix completion, called matrix abduction, which is particularly useful in the context of Talmudic logic and legal ruling systems in general. Given a matrix (mathbf{A}) with entries that are either in ({0,1}) or blank, the method allows us to decide whether each blank entry should be 0 or 1, or remain undecided. Unlike existing matrix completion methods, which are based on notions of analogy using distance (analogy to nearest neighbors), the new method takes a different approach and completes the matrix using only topological criteria; as a result, the outcome of the process is often significantly different. This chapter will focus specifically on one of these criteria, involving the representation of the finite partially ordered set as minimally generated multisets (ordered by inclusion) for which there is no known exact polynomial-time evaluation algorithm. We examine the existing efficient greedy algorithm for this criteria, its connection the similar known concepts dimension and two dimension of a poset (partial ordered set) then derive new useful properties and an algorithm. We start by proving that the exact evaluation of the criteria is NP-complete both in the general case and in the limited context of matrix abduction. We then discuss one-point removal properties of the problematic criteria, which may aid in solving specific cases and be utilized by new algorithms. Finally, we present a new greedy algorithm that offers a significant improvement over the existing one, and discuss the possibility of reusing existing algorithms that approximate 2-dimension of a poset.

DOI: 10.1007/978-3-319-15368-1_17

Full citation: