Logical inference and polyhedral projection Export

@incollection{hooker-92, abstract = {We explore connections between polyhedral projection and inference in propositional logic. We formulate the problem of drawing all inferences that contain a restricted set of atoms (i.e., all inferences that pertain to a given question) as a logical projection problem. We show that polyhedral projection partially solves this problem and in particular derives precisely those inferences that can be obtained by a certain form of unit resolution. We prove that this unit resolution algorithm is exponential in the number of atoms in the restricted set but is polynomial in the problem size when this number of fixed. We also survey a number of new satisfiability algorithms that have been suggested by the polyhedral interpretation of propositional logic.}, author = {Hooker, J.}, citeulike-article-id = {2749273}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/BFb0023767}, doi = {10.1007/BFb0023767}, journal = {Computer Science Logic}, keywords = {logic}, pages = {184--200}, posted-at = {2009-05-15 09:12:41}, priority = {2}, publisher = {Springer}, title = {Logical inference and polyhedral projection}, url = {http://dx.doi.org/10.1007/BFb0023767}, year = {1992} }

TY - CHAP ID - hooker-92 L3 - citeulike-article-id:2749273 N2 - We explore connections between polyhedral projection and inference in propositional logic. We formulate the problem of drawing all inferences that contain a restricted set of atoms (i.e., all inferences that pertain to a given question) as a logical projection problem. We show that polyhedral projection partially solves this problem and in particular derives precisely those inferences that can be obtained by a certain form of unit resolution. We prove that this unit resolution algorithm is exponential in the number of atoms in the restricted set but is polynomial in the problem size when this number of fixed. We also survey a number of new satisfiability algorithms that have been suggested by the polyhedral interpretation of propositional logic. JF - Computer Science Logic EP - 200 TI - Logical inference and polyhedral projection PB - Springer SP - 184 KW - logic AU - Hooker, J PY - 1992/// UR - http://dx.doi.org/10.1007/BFb0023767 ER -