{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T19:54:02Z","timestamp":1648929242643},"reference-count":0,"publisher":"AI Access Foundation","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["jair"],"abstract":"This paper considers the fragment \u2203\u2200SO 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 (\u03a3P2) 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 \u2203\u2200SO satisfiability problems. We use a syntactic representation of a constraint propagation method for first-order logic to transform such an \u2203\u2200SO satisfiability problem to an \u2203SO(ID) satisfiability problem (second-order logic, extended with inductive definitions). The finite domain satisfiability problem for the latter language is in NP and can be handled by several existing solvers. Inductive definitions are a powerful knowledge representation tool, and this moti- vates us to also approximate \u2203\u2200SO(ID) problems. In order to do this, we first show how to perform propagation on such inductive definitions. Next, we use this to approximate \u2203\u2200SO(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.<\/jats:p>","DOI":"10.1613\/jair.3658","type":"journal-article","created":{"date-parts":[[2018,7,18]],"date-time":"2018-07-18T13:29:44Z","timestamp":1531920584000},"page":"79-124","source":"Crossref","is-referenced-by-count":1,"title":["An approximative inference method for solving \u2203\u2200SO satisfiability problems"],"prefix":"10.1613","volume":"45","author":[{"given":"H.","family":"Vlaeminck","sequence":"first","affiliation":[]},{"given":"J.","family":"Vennekens","sequence":"additional","affiliation":[]},{"given":"M.","family":"Denecker","sequence":"additional","affiliation":[]},{"given":"M.","family":"Bruynooghe","sequence":"additional","affiliation":[]}],"member":"16860","published-online":{"date-parts":[[2012,9,25]]},"container-title":["Journal of Artificial Intelligence Research"],"original-title":[],"link":[{"URL":"http:\/\/jair.org\/index.php\/jair\/article\/download\/10779\/25737","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/jair.org\/index.php\/jair\/article\/download\/10779\/25738","content-type":"application\/postscript","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/jair.org\/index.php\/jair\/article\/download\/10779\/25737","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,17]],"date-time":"2019-10-17T22:31:03Z","timestamp":1571351463000},"score":1,"resource":{"primary":{"URL":"http:\/\/jair.org\/index.php\/jair\/article\/view\/10779"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,25]]},"references-count":0,"URL":"https:\/\/doi.org\/10.1613\/jair.3658","relation":{},"ISSN":["1076-9757"],"issn-type":[{"value":"1076-9757","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,25]]}}}