| 11. |
- Doherty, Patrick, 1957-, et al.
(författare)
-
Computing circumscription revisited.
- 1995
-
Ingår i: Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI). - 9781558603639 ; , s. 1502-1508
-
Konferensbidrag (refereegranskat)
|
|
| 12. |
- Doherty, Patrick, 1957-, et al.
(författare)
-
Computing circumscription revisited : A reduction algorithm
- 1997
-
Ingår i: Journal of automated reasoning. - : Kluwer Academic Publishers. - 0168-7433 .- 1573-0670. ; 18:3, s. 297-336
-
Tidskriftsartikel (refereegranskat)abstract
- In recent years, a great deal of attention has been devoted to logics of common-sense reasoning. Among the candidates proposed, circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic reasoning, but difficult to apply in practice. The major reason for this is the second-order nature of circumscription axioms and the difficulty in finding proper substitutions of predicate expressions for predicate variables. One solution to this problem is to compile, where possible, second-order formulas into equivalent first-order formulas. Although some progress has been made using this approach, the results are not as strong as one might desire and they are isolated in nature. In this article, we provide a general method that can be used in an algorithmic manner to reduce certain circumscription axioms to first-order formulas. The algorithm takes as input an arbitrary second-order formula and either returns as output an equivalent first-order formula, or terminates with failure. The class of second-order formulas, and analogously the class of circumscriptive theories that can be reduced, provably subsumes those covered by existing results. We demonstrate the generality of the algorithm using circumscriptive theories with mixed quantifiers (some involving Skolemization), variable constants, nonseparated formulas, and formulas with n-ary predicate variables. In addition, we analyze the strength of the algorithm, compare it with existing approaches, and provide formal subsumption results.
|
|
| 13. |
|
|
| 14. |
- Doherty, Patrick, 1957-, et al.
(författare)
-
Computing strongest necessary and weakest sufficient conditions of first-order formulas
- 2001
-
Ingår i: 17th International Joint Conference on Artificial Intelligence,2001. - San Francisco, CA, USA : Morgan Kaufmann Publishers Inc.. - 1558608125 - 9781558608122 ; , s. 145-151
-
Konferensbidrag (refereegranskat)abstract
- A technique is proposed for computing the weakest sufficient (wsc) and strongest necessary (snc) conditions for formulas in an expressive fragment of first-order logic using quantifier elimination techniques. The efficacy of the approach is demonstrated by using the techniques to compute snc's and wsc's for use in agent communication applications, theory approximation and generation of abductive hypotheses. Additionally, we generalize recent results involving the generation of successor state axioms in the propositional situation calculus via snc's to the first-order case. Subsumption results for existing approaches to this problem and a re-interpretation of the concept of forgetting as a process of quantifier elimination are also provided.
|
|
| 15. |
- Doherty, Patrick, 1957-, et al.
(författare)
-
Declarative PTIME queries for relational databases using quantifier elimination
- 1999
-
Ingår i: Journal of logic and computation (Print). - : Oxford University Press. - 0955-792X .- 1465-363X. ; 9:5, s. 737-758
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper, we consider the problem of expressing and computing queries on relational deductive databases in a purely declarative query language, called SHQL (Semi-Horn Query Language). Assuming the relational databases in question are ordered, we show that all SHQL queries are computable in PTIME (polynomial time) and the whole class of PTIME queries is expressible in SHQL. Although similar results have been proven for fixpoint languages and extensions to datalog, the claim is that SHQL has the advantage of being purely declarative, where the negation operator is interpreted as classical negation, mixed quantifiers may be used and a query is simply a restricted first-order theory not limited by the rule-based syntactic restrictions associated with logic programs in general. We describe the PTIME algorithm used to compute queries in SHQL which is based in part on quantifier elimination techniques and also consider extending the method to incomplete relational databases using intuitions related to circumscription techniques.
|
|
| 16. |
|
|
| 17. |
- Doherty, Patrick, 1957-, et al.
(författare)
-
Defaults as first-class citizens
- 1992
-
Ingår i: Proceedings of the 22nd International Symposium on Multiple-Valued Logic (SMVL). - : IEEE Computer Society. - 0818626801 ; , s. 146-154
-
Konferensbidrag (refereegranskat)abstract
- A nonmonotonic logic with explicit defaults, NML3, is presented. It is characterized by the following features: (1) the use of the strong Kleene three-valued logic as a basis; (2) the addition of an explicit default operator which enables distinguishing tentative conclusions from ordinary conclusions in the object language; and (3) the use of the idea of preferential entailment to generate nonmonotonic behavior. The central feature of the formalism, the use of an explicit default operator with a model-theoretic semantics based on the notion of a partial interpretation, distinguishes NML3 from most previous formalisms. By capitalizing on the distinction between tentative and ordinary conclusions, NML3 provides increased expressibility in comparison to many of the standard nonmonotonic formalisms and greater flexibility in the representation of subtle aspects of default reasoning. This is shown through examples.
|
|
| 18. |
- Doherty, Patrick, 1957-, et al.
(författare)
-
Distinguishing between facts and default assumptions.
- 1992
-
Ingår i: Non-Monotonic Reasoning and Partial Semantics. Ellis Horwood Workshops.. - New York : Ellis Horwood Ltd.. - 0136251463 - 9780136251460
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)
|
|
| 19. |
- Doherty, Patrick, 1957-, et al.
(författare)
-
Efficient reasoning using the local closed-world assumption
- 2000
-
Ingår i: Proceedings of the 9th International Conference on Artificial Intelligence: Methodology, Systems and Applications (AIMSA). - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783540410447 - 9783540453314 ; , s. 49-58
-
Konferensbidrag (refereegranskat)abstract
- We present a sound and complete, tractable inference method for reasoning with localized closed world assumptions (LCWA’s) which can be used in applications where a reasoning or planning agent can not assume complete information about planning or reasoning states. This Open World Assumption is generally necessary in most realistic robotics applications. The inference procedure subsumes that described in Etzioni et al [9], and others. In addition, it provides a great deal more expressivity, permitting limited use of negation and disjunction in the representation of LCWA’s, while still retaining tractability. The ap- proach is based on the use of circumscription and quantifier elimination techniques and inference is viewed as querying a deductive database. Both the preprocessing of the database using circumscription and quan- tifier elimination, and the inference method itself, have polynomial time and space complexity.
|
|
| 20. |
- Doherty, Patrick, 1957-, et al.
(författare)
-
Explaining explanation closure
- 1996
-
Ingår i: Proceedings of the 9th International Symposium on Methodologies for Intelligent Systems,1996. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 3540612866 ; , s. 521-530
-
Konferensbidrag (refereegranskat)abstract
- Recently, Haas, Schubert, and Reiter, have developed an alternative approach to the frame problem which is based on the idea of using explanation closure axioms. The claim is that there is a monotonic solution for characterizing nonchange in serial worlds with fully specified actions, where one can have both a succinct representation of frame axioms and an effective proof theory for the characterization. In the paper, we propose a circumscriptive version of explanation closure, PMON, that has an effective proof theory and works for both context dependent and nondeterministic actions. The approach retains representational succinctness and a large degree of elaboration tolerance, since the process of generating closure axioms is fully automated and is of no concern to the knowledge engineer. In addition, we argue that the monotonic/nonmonotonic dichotomy proposed by others is not as sharp as previously claimed and is not fully justified.
|
|
