Information Technology Reference
In-Depth Information
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 [10] 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
aCSCintheform
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.
B
L
i
A
.
R
f
(
L
i
)and
2.3
Abstraction
Definition 4.
Size of a CSA
A
is the number of different literals
A
involves
and is denoted with
S
(
A
)
.
Definition 5.
Abstraction
is a set of literals, which are allowed in a CSA, if
particular abstraction is applied.
A
Definition 6.
Abstraction level is a position in an abstraction hierarchy. The
lowest abstraction level is denoted with
0
and represents the original problem
space.
Definition 7.
Abstraction hierarchy
H
for a CSA
A
is a total order of abstrac-
tions such that
∀A
i
, A
j
∈H∧i
=
j∧
(
S
(
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
S
(
A
i
(
A
))
≡S
(
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.
Search WWH ::
Custom Search