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