Declarative Logic Programming: Theory, Systems, and Applications by Michael Kifer & Yanhong Annie Liu

Author:Michael Kifer & Yanhong Annie Liu
Language: eng
Format: epub
Publisher: Association for Computing Machinery and Morgan & Claypool Publishers
Published: 2018-03-14T16:00:00+00:00

• I′ = I [U : f], where U is a set of domain atoms unknown in I such that for every P(d̄) ∈ U and every rule ∀x̄ : P(x̄) ← φ in Δ, it holds that φ[x̄/d̄]I′ = f (such a set U is called an unfounded set of Δ in I [Van Gelder et al. 1991]).

A refinement is strict if I′ ≠ I.

The first refinement evaluates all rule bodies of all defined domain atoms and assigns the largest truth value (e.g., if one rule derives an atom to be true, and the second rule does not yet derive information about that atom (u), the atom obtains the value t) to each defined atom. The second refinement identifies an unfounded set: a set of domain atoms such that the bodies of rules defining them can only become true if at least one of these atoms is true in the first place (due to cyclic dependencies). Such atoms can never be derived constructively using the definition, hence they must be false.

Definition 5.2 Well-founded induction. Let I be a partial structure that interprets only the open symbols of Δ. A well-founded induction of Δ in I is a sequence (Ii)i≤n, with n ∈ ℕ, of partial structures such that the following hold:5

• I0 = I; and

• for each i < n, Ii+1 is a refinement of Ii.

A well-founded induction is terminal if its limit (In) has no strict refinements.

Denecker and Vennekens [2007] showed that all terminal well-founded inductions in I have the same limit, namely the well-founded model of Δ in context I.

To extend this satisfaction check to definitions defining functions, one treats a function f/n as if it is defining an n + 1-ary relation. For what concerns the use of partial functions in the head of a rule, note that ∀ȳ : p(t̄) ← φ is equivalent with ∀x̄ ȳ : p(x̄) ← x̄ = t̄ ∧ φ. Partial functions in bodies have the same meaning as in formulas.

In FO(ID, AGG, PF, T), a definition is seen in a pure declarative way, as a proposition stating a special logical relationship between defined predicates and parameter symbols. In case a theory contains multiple definitions of the same predicate, the theory states multiple independent such propositions. For instance, a theory that contains

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.