Title: An approximative inference method for solving ∃∀SO satisfiability problems
Authors: Vlaeminck, Hanne ×
Vennekens, Joost
Denecker, Marc
Bruynooghe, Maurice #
Issue Date: Sep-2012
Publisher: AI Access Foundation
Series Title: The Journal of Artificial Intelligence Research vol:45 pages:79-124
Abstract: This paper considers the fragment ∃∀SO of second-order logic. Many interesting problems, such as conformant
planning, can be naturally expressed as finite domain satisfiability problems of this logic. Such satisfiability problems are computationally hard and many of these problems are often solved approximately.
In this paper, we develop a general approximative method, i.e., a sound
but incomplete method, for solving ∃∀SO satisfiability
problems. We use a syntactic representation of a constraint
propagation method for first-order logic to transform such an ∃∀SO satisfiability problem to an ∃SO satisfiability
problem (second-order logic, extended with with inductive definitions). The finite domain satisfiability problem for the latter
language is in NP and can be handled by several existing
solvers. Next, we look at an extension of first-order logic with
inductive definitions (FO(ID)).
Inductive definitions are a powerful
knowledge representation tool, and this %motives
motivates us to also approximate ∃∀SO(ID) problems. In order to do this, we first show how to perform propagation on such inductive definitions. Next, we use this to approximate ∃∀SO(ID) satisfiability problems. All this provides a general theoretical framework for a number of approximative methods in the literature. Moreover, we also show how we can use this framework for solving practical useful problems, such as conformant planning, in an effective way.
ISSN: 1076-9757
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
Technologiecluster Computerwetenschappen
Computer Science Technology TC, Technology Campus De Nayer Sint-Katelijne-Waver
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
vlaeminck2012.pdf Published 510KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science