SwePub
Sök i SwePub databas

  Utökad sökning

Träfflista för sökning "WFRF:(Lukaszewicz Witold 1947 ) srt2:(1995-1999)"

Sökning: WFRF:(Lukaszewicz Witold 1947 ) > (1995-1999)

  • Resultat 1-10 av 13
Sortera/gruppera träfflistan
   
NumreringReferensOmslagsbildHitta
1.
  •  
2.
  • Doherty, Patrick, 1957-, et al. (författare)
  • A reduction result for circumscribed semi-horn formulas
  • 1996
  • Ingår i: Fundamenta Informaticae. - : IOS Press. - 0169-2968 .- 1875-8681. ; 28:3,4, s. 261-272
  • Tidskriftsartikel (refereegranskat)abstract
    • Circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic and commonsense reasoning, but difficult to apply in practice due to the use of second-order formulas. One proposal for dealing with the computational problems is to identify classes of first-order formulas whose circumscription can be shown to be equivalent to a first-order formula. In previous work, we presented an algorithm which reduces certain classes of second-order circumscription axioms to logically equivalent first-order formulas. The basis for the algorithm is an elimination lemma due to Ackermann. In this paper, we capitalize on the use of a generalization of Ackermann's Lemma in order to deal with a subclass of universal formulas called semi-Horn formulas. Our results subsume previous results by Kolaitis and Papadimitriou regarding a characterization of circumscribed definite logic programs which are first-order expressible. The method for distinguishing which formulas are reducible is based on a boundedness criterion. The approach we use is to first reduce a circumscribed semi-Horn formula to a fixpoint formula which is reducible if the formula is bounded, otherwise not. In addition to a number of other extensions, we also present a fixpoint calculus which is shown to be sound and complete for bounded fixpoint formulas.
  •  
3.
  • Doherty, Patrick, 1957-, et al. (författare)
  • A study in modal embeddings of NML3.
  • 1996
  • Ingår i: Partiality, Modality, and Nonmonotonicity, Studies in Logic, Language and Information.. - Stanford, California : CSLI Publications. - 1575860317 - 1575860309 ; , s. 145-168
  • Bokkapitel (övrigt vetenskapligt/konstnärligt)
  •  
4.
  • 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)
  •  
5.
  • 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.
  •  
6.
  •  
7.
  • 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.
  •  
8.
  •  
9.
  • 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.
  •  
10.
  • Doherty, Patrick, 1957-, et al. (författare)
  • General domain circumscription and its effective reductions.
  • 1998
  • Ingår i: Fundamenta Informaticae. - : IOS Press. - 0169-2968 .- 1875-8681. ; 36:1, s. 23-55
  • Tidskriftsartikel (refereegranskat)abstract
    • We first define general domain circumscription (GDC) and provide it with a semantics. GDC subsumes existing domain circumscription proposals in that it allows varying of arbitrary predicates, functions, or constants, to maximize the minimization of the domain of a theory. We then show that for the class of semi-universal theories without function symbols, that the domain circumscription of such theories can be constructively reduced to logically equivalent first-order theories by using an extension of the DLS algorithm, previously proposed by the authors for reducing second-order formulas. We also show that for a certain class of domain circumscribed theories, that any arbitrary second-order circumscription policy applied to these theories is guaranteed to be reducible to a logically equivalent first-order theory. In the case of semi-universal theories with functions and arbitrary theories which are not separated, we provide additional results, which although not guaranteed to provide reductions in all cases, do provide reductions in some cases. These results are based on the use of fixpoint reductions.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 1-10 av 13

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy