We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Bottom-up Construction of Semantic Tableaux.
- Authors
PELTIER, NICOLAS
- Abstract
We present a new proof procedure for first-order logic. Our approach is closely related to semantic tableaux, but it uses a more compact representation of the search space. The idea is to construct the tableau from the leaves to the root, which helps to factorize common subtrees and reduces the information that must be stored in a given branch. We prove that the method is sound and refutationally complete and we provide simplification rules in order to prune the search space and delete redundant inferences. We show that our procedure runs in polynomial time for several propositional classes, including the Horn-renamable class or the Krom class. This article is an extended version of Peltier (2007, LNAI 4548).
- Subjects
FIRST-order logic; POLYNOMIALS; MODERN logic; SEMANTICS; LOGIC
- Publication
Journal of Logic & Computation, 2010, Vol 20, Issue 1, p283
- ISSN
0955-792X
- Publication type
Article
- DOI
10.1093/logcom/exn069