Declarative logic programs (LP) based on the well-founded semantics (WFS) are widely used for knowledge representation (KR). Logical functions are desirable expressively in KR, but when present make LP inferencing become undecidable. In this paper, we present radial restraint: a novel approach to bounded rationality in LP. Radial restraint is parameterized by a norm that measures the syntactic complexity of a term, along with an abstraction function based on that norm. When a term exceeds a bound for the norm, the term is assigned the WFS's third truth-value of undefined. If the norm is finitary, radial restraint guarantees finiteness of models and decidability of inferencing, even when logical functions are present. It further guarantees soundness, even when non-monotonicity is present. We give a fixed-point semantics for radially restrained well-founded models which soundly approximate well-founded models. We also show how to perform correct inferencing relative to such models, via SLG_ABS, an extension of tabled SLG resolution that uses norm-based abstraction functions. Finally we discuss how SLG_ABS is implemented in the engine of XSB Prolog, and scales to knowledge bases with more than 10^8 rules and facts.

We show how to interoperate, semantically and inferentially, between the leading Semantic Web approaches to rules (RuleML Logic Programs) and ontologies (OWL/DAML+OIL Description Logic) via analyzing their expressive intersection. To do so, we define a new intermediate knowledge representation (KR) contained within this intersection: Description Logic Programs (DLP), and the closely related Description Horn Logic (DHL) which is an expressive fragment of first-order logic (FOL). DLP provides a significant degree of expressiveness, substantially greater than the RDF-Schema fragment of Description Logic. We show how to perform DLP-fusion: the bidirectional translation of premises and inferences (including typical kinds of queries) from the DLP fragment of DL to LP, and vice versa from the DLP fragment of LP to DL. In particular, this translation enables one to "build rules on top of ontologies": it enables the rule KR to have access to DL ontological definitions for vocabulary primitives (e.g., predicates and individual constants) used by the rules. Conversely, the DLP-fusion technique likewise enables one to "build ontologies on top of rules": it enables ontological definitions to be supplemented by rules, or imported into DL from rules. It also enables available efficient LP inferencing algorithms/implementations to be exploited for reasoning over large-scale DL ontologies.

SweetDeal is a rule-based approach to representation of business contracts that enables software agents to create, evaluate, negotiate, and execute contracts with substantial automation and modularity. It builds upon the situated courteous logic programs knowledge representation in RuleML, the emerging standard for Semantic Web XML rules. Here, we newly extend the SweetDeal approach by also incorporating process knowledge descriptions whose ontologies are represented in DAML+OIL (emerging standard for Semantic Web ontologies) thereby enabling more complex contracts with behavioral provisions, especially for handling exception conditions (e.g., late delivery or non-payment) that might arise during the execution of the contract. This provides a foundation for representing and automating deals about services -- in particular, about Web Services, so as to help search, select, and compose them. Our system is also the first to combine emerging Semantic Web standards for knowledge representation of rules (RuleML) with ontologies (DAML+OIL) for a practical e-business application domain, and further to do so with process knowledge. This also newly fleshes out the evolving concept of Semantic Web Services. A prototype (soon public) is running.

We address the problem of authorization in large-scale, open, distributed systems. Authorization decisions are needed in electronic commerce, mobile-code execution, remote resource sharing, privacy protection, and many other applications. We adopt the trust-management approach, in which "authorization" is viewed as a " proof-of-compliance " problem: Does a set of credentials prove that a request complies with a policy?We develop a logic-based language, called Delegation Logic (DL), to represent policies, credentials, and requests in distributed authorization. In this paper, we describe D1LP, the monotonic version of DL. D1LP extends the logic-programming (LP) language Datalog with expressive delegation constructs that feature delegation depth and a wide variety of complex principals (including, but not limited to, k-out-of-n thresholds). Our approach to defining and implementing D1LP is based on tractably compiling D1LP programs into ordinary logic programs (OLPs). This compilation approach enables D1LP to be implemented modularly on top of existing technologies for OLP, for example, Prolog.As a trust-management language, D1LP provides a concept of proof-of-compliance that is founded on well-understood principles of logic programming and knowledge representation. D1LP also provides a logical framework for studying delegation.

Our approach for automating the negotiation of business contracts proceeds in three broad steps. First, determine the structure of the negotiation process by applying general knowledge about auctions and domain–specific knowledge about the contract subject along with preferences from potential buyers and sellers. Second, translate the determined negotiation structure into an operational specification for an auction platform. Third, after the negotiation has completed, map the negotiation results to a final contract. We have implemented a prototype which supports these steps by employing a declarative specification (in courteous logic programs) of (1) high–level knowledge about alternative negotiation structures, (2) general–case rules about auction parameters, (3) rules to map the auction parameters to a specific auction platform, and (4) special–case rules for subject domains. We demonstrate the flexibility of this approach by automatically generating several alternative negotiation structures for the domain of travel shopping in a trading agent competition.

We address the goal of making Delegation Logic (DL) into a practically implementable and tractable trust management system. DL (N. Li et al., 1999) is a logic based knowledge representation (i.e., language) for authorization in large scale, open, distributed systems. DL inferencing is computationally intractable and highly impractical to implement. We introduce a new version of Delegation Logic that remedies these difficulties. To achieve this, we impose a syntactic restriction and redefine the semantics somewhat. We show that, for this revised version of DL, inferencing is computationally tractable under the same commonly met restrictions for which Ordinary Logic Programs (OLP) inferencing is tractable (e.g., Datalog and bounded number of logical variables per rule). We give an implementation architecture for this version of DL; it uses a delegation compiler from DL to OLP and can modularly exploit a variety of existing OLP inference engines. As proof of concept, we have implemented a large expressive subset of this version of DL, using this architecture.

We introduce Delegation Logic (DL), a logic-based knowledge representation (i.e., language) that deals with authorization in large-scale, open distributed systems. Of central importance in any system for deciding whether requests should be authorized in such a system are delegation of authority, negation of authority, and conflicts between authorities. DL's approach to these issues and to the interplay among them borrows from previous work on delegation and trust management in the computer security literature and previous work on negation and conflict handling in the logic programming and nonmonotonic reasoning literature, but it departs from previous work in some crucial ways. We present the syntax and semantics of DL and explain our novel design choices. We focus on delegation, including explicit treatment of delegation depth and delegation to complex principles. Compared to previous logic-based approaches to authorization, DL provides a novel combination of features: it is based on logic programs, expresses delegation depth explicitly, and supports a wide variety of complex principles (including but not limited to k-out-of-n thresholds). Compared to previous approaches to trust management, DL provides another novel feature: a concept of proof-of-compliance that is not entirely ad-hoc and that is based on model theoretic semantics (just as usual logic programs have a model-theoretic semantics).

We address why, and especially how, to represent business rules in e-commerce contracts.By contracts, we mean descriptions of goods and services offered or sought, including ancillary agreements detailing terms of a deal.We observe that rules are useful in contracts to represent conditional relationships, e.g., in terms & conditions, service provisions, and surrounding business processes, and we illustrate this point with several examples.We analyze requirements (desiderata) for representing such rules in contracts.The requirements include: declarative semantics so as to enable shared understanding and interoperability; prioritized conflict handling so as to enable modular updating/revision; ease of parsing; integration into WWW-world software engineering; direct executability; and computational tractability.We give a representational approach that consists of two novel aspects.First, we give a new fundamental knowledge representation formalism: a generalized version of Courteous Lugic Programs (CLP), which expressively extends declarative ordinary logic programs (OLP) to include prioritized conflict handling, thus enabling modularity in specifying and revising rule-sets.Our approach to im-