Information Technology Reference
where I and O are multiplicative conjunctions of literals and f is a function,
which implements the computation step.
The succedent and the antecedent of CSC C are denoted with succ ( C )and
ant ( C ) respectively.
Definition 2. Computation Specification (CS) is a finite set of CSCs.
Definition 3. Computation Specification Application (CSA) is defined as
Γ ; S G,
where Γ is a CS, S is the initial state and G is the goal state of computation.
Both S and G are represented with multiplicative conjunctions of literals.
We are going to use letters S , G and Γ throughout the paper in this con-
text. PD back- and forward chaining steps, respectively
R b ( L i )and
R f ( L i ), are
defined  with the following rules:
S B ⊗ C
S A ⊗ C R b ( L i ) A ⊗ C G
B ⊗ C G R f ( L i )
L i in the inference figures is a labelling of a particular LL axiom representing
R b ( L i ) apply clause L i to move
the initial state towards the goal state or the other way around. A , B and
C are multiplicative conjunctions. This brings us to the essence of PD, which
is program manipulation, in our case basically modification of initial and goal
states. As a side-effect of PD a modified program is created.
R f ( L i )and
Definition 4. Size of a CSA A is the number of different literals A involves
and is denoted with
( A ) .
Definition 5. Abstraction
is a set of literals, which are allowed in a CSA, if
particular abstraction is applied.
Definition 6. Abstraction level is a position in an abstraction hierarchy. The
lowest abstraction level is denoted with 0 and represents the original problem
Definition 7. Abstraction hierarchy
for a CSA A is a total order of abstrac-
tions such that
∀A i , A j ∈H∧i
A i ( A )) < S
A j ( A )))
⇒A j ( A )
≺A i ( A ) ,
whereas i and j are abstraction levels.
Due to the way we construct abstraction hierarchies, it is not possible that
A i ( A ))
A j ( A )), unless i ≡ j .
Definition 8. If l is a literal, then Level ( l ) is the highest abstraction level where
l can appear.