| Reference : Topological Aspects of Matrix Abduction 2 |
| Parts of books : Contribution to collective works | |||
| Engineering, computing & technology : Computer science | |||
| http://hdl.handle.net/10993/26045 | |||
| Topological Aspects of Matrix Abduction 2 | |
| English | |
Gabbay, Dov M.  [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)] | |
| Bessos, Mai [> >] | |
| 2015 | |
| The Road to Universal Logic - Festschrift for the 50th Birthday of Jean-Yves Béziau Volume II, Chapter 17 | |
| Birkh\''auser Basel | |
| Studies in Universal Logic | |
| Yes | |
| 978-3-319-15367-4 | |
| [en] Bit-vector encodings ; Partially ordered sets ; Matrix abduction | |
| [en] 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 AA with entries that are either in {0,1}{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. | |
| http://hdl.handle.net/10993/26045 |
There is no file associated with this reference.
All documents in ORBilu are protected by a user license.
