ASP RuleML

ASP RuleML is an approach to accommodate the RuleML language to express answer-set programs. It consists of a layered family of XML schemas, derived from the RuleML Datalog dialect, extending it in order to capture a variety of ASP-related language features.

The framework presented here is supposed to be a starting point that prompts both the Semantic Web and the ASP community to discuss and achieve a comprehensive RuleML interchange format for the ASP semantics. It is work in progress which, as we believe, will attract other participants after initial dissemination.

The Language

The new sublanguage currently consists of two layers:

ASP Base encapsulates the syntax of traditional answer-set programs. ASP Oracle facilitates the expression of a number of advanced constructs which are provided by current ASP solvers, such as aggregates, built-ins or external atoms, by a general syntactical element.

ASP Base

The language that underlies the ASP semantics described in the seminal paper of Gelfond and Lifschitz [1] can be regarded as the core language of answer-set programming and constitutes the language variant we call ASP Base. It corresponds to disjunctive Datalog, extended with strong negation and constraints (i.e., rules with empty head). The language is defined in aspbase.xsd and derives from the schema nafnegdatalog with the following main modifications:

This defines the core dialect that serves as a base for various ASP extensions.

ASP Oracle

Several state-of-the-art answer-set solvers such as DLV or Smodels provide specific language extensions. Such extensions either represent a special kind of atom, like custom built-in predicates or aggregate atoms, or constructs that aim at adding qualitative information to the result, like weak constraints. Although each of these extensions has a well-defined semantics, they mostly remain specific to a particular reasoner and are not portable in the sense of a universal ASP syntax. We propose a syntactic entity, called oracle atom, offering a general and versatile as a most general representation for such sophisticated, ASP-related language features.

Informally, an oracle atom consists of

where the elements of both lists are terms and literals. An oracle atom can occur wherever an ordinary atom is allowed; it has an input list and an output list of either terms or literals.

The process of giving semantics to oracles is up to the specific reasoners, respectively translators which convert the ASP program from RuleML to a textual representation tailored to such a reasoner. We emphasize the fact that an oracle atom is a pure syntactic instrument to express any language feature which goes beyond the traditional elements of answer-set programming, i.e., (possibly weakly negated) Literals. Considering the substantial number of such features which are provided by DLV and Smodels alone, a separate RuleML syntax for each of them would result in a complex and unmanageable set of highly specific language elements. Permitting the usage of string terms in input and output lists of the oracle eventually allows for arbitrarily complex functionalities.

By adding the oracle atom to ASP Base, we define the schema ASP oracle, which is capable of syntactically embracing most of these features.

Implementation

ASP Base is defined by aspbase.xsd and derives from the RuleML variant nafnegdatalog, adding head disjunction and constraints. ASP Oracle is defined by asporacle.xsd, building on ASP Base and adding the oracle atom.

Examples

Consider a rule with a comparative predicate, such as

pair(X,Y) :- Y > X, color(X,green), color(Y,green).

The sign > is intuitive, but cannot be translated into an XML syntax in a straightforward way. However, since Y > X stands for an atom, we can represent it by the following XML construct, which can be used wherever an <Atom> element is allowed:

    <Oracle>
        <Rel>greaterThan</Rel>
        <Input>
            <Var>Y</Var>
            <Var>X</Var>
        </Input>
    </Oracle>

Another example illustrates the expression of a more sophisticated construct. Smodels allows for the specification of so-called cardinality constraints, that filters the models by occurence of specific combination of literals (cf. [2]). This cardinality constraint

1 { a, b, not c} 2

could be represented by the following oracle:

    <Oracle>
        <Rel>cardCons</Rel>
        <Input>
            <Data xsi:type="xs:integer">1</Data>
            <Atom>
                <Rel>a</Rel>
            <Atom>
            <Atom>
                <Rel>b</Rel>
            <Atom>
            <Naf>
                <Atom>
                    <Rel>c</Rel>
                <Atom>
            <Naf>
            <Data xsi:type="xs:integer">2</Data>
        </Input>
    </Oracle>

Instead of specifying fixed bounds, also variables can be given, like <Var>X</Var>. At least one bound must be specified - if both are given, their position within the input-list determines whether the respective value is a lower or an upper bound.

Another construct of Smodels, the weight constraint, which assigns weights to literals inside a constraint, such as

1.02 ≤ { a(p) = 1.0, b(p,z) = 0.02, not c(q) = 0.04} ≤ 1.03

could be realized by nesting oracles:

    <Oracle>
        <Rel>weightCons</Rel>
        <Input>
            <Data xsi:type="xs:double">1.2</Data>
            <Oracle>
                <Rel>assign</Rel>
                <Input>
                    <Atom>
                        <Rel>a</Rel>
                        <Ind>p</Ind>
                    <Atom>
                    <Data xsi:type="xs:double">1.0</Data>
                </Input>
            </Oracle>
            <Oracle>
                <Rel>assign</Rel>
                <Input>
                    <Atom>
                        <Rel>b</Rel>
                        <Ind>p</Ind>
                        <Ind>z</Ind>
                    <Atom>
                    <Data xsi:type="xs:double">0.02</Data>
                </Input>
            </Oracle>
            <Oracle>
                <Rel>assign</Rel>
                <Input>
                    <Naf>
                        <Atom>
                            <Rel>c</Rel>
                            <Ind>q</Ind>
                        <Atom>
                    <Naf>
                    <Data xsi:type="xs:double">0.04</Data>
                </Input>
            </Oracle>
            <Data xsi:type="xs:double">1.03</Data>
        </Input>
    </Oracle>

Here, the assignment of numerical values to specific literal is realized through oracles, which are then specified in the input list of the weight constraint oracle.

Further dialects

A type of program which needs a further schema extension are HEX-programs [3], which also allow for variable predicate symbols, facilitating a simple higher-order syntax. The distinctive feature of HEX-programs are external atoms, providing an interface to an arbitrary external source of computation under well-defined semantics. The characteristic feature of HEX-atoms is to foster a loose coupling between the logic program and the external source, while facilitating a bidirectional flow of information. External atoms can be accomodated by oracle atoms in a straighforward way, their semantics is determined by the respective external evaluation function. The asphex.xsd schema modifies ASP Oracle by allowing variable predicate symbols. The intuition behind oracle atoms used in ASP HEX is to interpret them as external atoms.

For instance, the external atom

&rdf[A](S,P,O)
can be captured by this oracle:

    <Oracle>
        <Rel>rdf</Rel>
        <Input>
            <Var>A</Var>
        </Input>
        <Output>
            <Var>X</Var>
            <Var>Y</Var>
            <Var>Z</Var>
        </Output>
    </Oracle>

Translators

We implemented translators to convert answer-set programs from classical datalog-syntax into ASP RuleML and back. Try it!

ASP:
[to ruleml]   [to hex]
ASP RuleML:

References

[1] M. Gelfond and V. Lifschitz. Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing, 9:365--385, 1991.

[2] I. Niemelä, P. Simons, and Tommi Syrjänen. Smodels: A System for Answer Set Programming. CoRR, cs.AI/0003033, 2000. http://arxiv.org/abs/cs.AI/0003033

[3] T. Eiter, G. Ianni, R. Schindlauer, and H. Tompits. A Uniform Integration of Higher-Order Reasoning and External Evaluations in Answer Set Programming. In Proc. IJCAI-05, pp. 90--96, 2005.