Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports of the Computer Science Department
    • View Item
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports of the Computer Science Department
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Optimal Models of Disjunctive Logic Programs: Semantics, Complexity, and Computation

    Thumbnail
    View/Open
    CS-TR-4298.ps (326.6Kb)
    No. of downloads: 293

    Auto-generated copy of CS-TR-4298.ps (388.2Kb)
    No. of downloads: 884

    Date
    2001-11-01
    Author
    Leone, Nicola
    Scarcello, Francesco
    Subrahmanian, V. S.
    Metadata
    Show full item record
    Abstract
    Almost all semantics for logic programs with negation identify a set, SEM(P), of models of program P, as the intended semantics of P, and any model M in this class is considered a possible meaning of P w.r.t. the semantics the user has in mind. Thus, for example, in the case of stable models, choice models, answer sets, etc., different possible models correspond to different ways of ``completing'' the incomplete information in the logic program. However, different end-users may have different ideas on which of these different models in SEM(P) is a reasonable one from their point of view. For instance, given SEM(P), user U1 may prefer model M1 to model M2 based on some evaluation criterion that she has. In this paper, we will develop a notion of logic program semantics based on the concept of an Optimal Model. This semantics doesn't add yet another semantics to thelogic programming arena -- rather, it takes as input, an existing semantics SEM(P) and a user-specified objective function Obj, and yields a new semantics that realizes the objective function within the framework of preferred models identified already by SEM(P) in different ways. Thus, the user who may or may not know anything about logic programming has considerable flexibility in making the system reflect her own objectives by building ``on top'' of existing semantics known to the system. In addition to the declarative semantics characterization, we provide a complete complexity analysis and algorithms to compute optimal models under varied conditions when SEM(P) is the stable model semantics, the minimal models semantics, and the all-models semantics.
    URI
    http://hdl.handle.net/1903/529
    Collections
    • Technical Reports of the Computer Science Department

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility