| The
algorithms
This
annex contains the pseudo-code for the main functions
of the computational model UNICORE. The implementation
reflects precisely this code. In the following,
types begin with a capital letter, variables are
in lower case, constants are all in upper case.
General
types in use: Token, Model, Task = {SYLL,
REL,
INFERENCE,
JUDGMENT,
ACTION},
Boolean = {TRUE,
FALSE}.
Function
Match
type
MatchStatus = {OK, FAILURE}
function
match(t1, t2, t3: Token): MatchStatus
begin
if
identity (t1, t2) = TRUE then
t3
<- t1
return
OK
return
FAILURE
end
Function
Integration
type
IntegrationStatus = {OK, FAILURE}
function
Integration(mm1, mm2, mm-integrated: Model): IntegrationStatus
global
var record: array of triples of tokens, initially
empty;
global
var try_Re-arrange: integer, initially 0;
global
var try_Flesh-out: integer, initially 0;
var
local-record: array of triples of tokens, initially
empty;
begin
[1]
<t1, t2> <- a pair of tokens such
that: t1 is a rightmost token
in mm1 and
t2
is a leftmost token in mm2 and
<t1,
t2, _> is not in record
[2]
repeat
[3]
while match(t1, t2, t3) = FAILURE
and not null t1 do
[4]
mark t1
t1
<- unmarked rightmost token in mm1 such that
<t1, t2, _> not in record
[5]
if null t1 then
[6]
unmark all the tokens in mm1 not in local-record
[7]
<t1, t2> <- a pair of tokens such
that:
t1
is an unmarked rightmost token in mm1 and
t2
is an unmarked leftmost token in mm2 and
<t1,
t2, _> is not in record and
<t1,
t2, _> is not in local-record
mark
t2
[8]
else
store
t3 in mm-integrated
store
<t1, t2, t3> in local-record
[9]
until null t1 or null t2
[10]
if local-record is not empty then
update
record with the triples in local-record
[11]
store all the tokens in mm1 or mm2 that did
not match in mm-integrated
[12]
for each relation r in mm1 or
mm2 do
r'
<- copy(r)
[13]
for each token tx in r' do
if
tx is in a triple <tx, t2, t3> or <t1,
tx, t3> in local-record then
replace
tx with t3 in r'
store
r' in mm-integrated
return
OK
[14]
if local-record is empty and
try_Re-arrange=0 then
Re-arrange(mm1,
mm2)
try_Re-arrange
<- try_Re-arrange + 1
return(Integration(mm1,
mm2, mm-integrated))
[15]
if local-record is empty and
try_Flesh-out=0 then
Flesh-out(mm1,
mm2)
try_Flesh-out
<- try_Flesh-out + 1
try_Re-arrange
<- 0
return(Integration(mm1,
mm2, mm-integrated))
[16]
return FAILURE
end
Comments
to the algorithm Integration.
Integration
takes as input two models mm1 and mm2, and returns
a model mm-integrated. The
global variable record keeps track
of the tokens that matched, in order to avoid multiple
matches on the same pair of tokens.
The matches already performed are stored
as triples <t1, t2, t3>, where t1 and t2 are
the original tokens that matched and t3 is the result
token. 'Record' is initially
assigned the empty set, and then updated at each
successful match. The global
variables try_Re-arrange and try_Fesh-out,
initially set to 0, represents the number of attempts
to restructure information. Finally,
the local variable local-record
keeps track of the matches that occurred in the
current attempt at Integration: the triples stored
in local-record are then the kernel of the integrated
model. The global variable
record is updated with the triples
in local-record.
In the following comments to the algorithm
the numbers in square brackets refer to relevant
points.
In
the beginning, two adjacent tokens t1 and t2 are
selected in the two models [1]. The
selection process (not specified in the algorithm)
considers the tokens of the matrix in the top down
order of rows (the column is the rightmost or leftmost
respectively). The tokens
t1 and t2 must not be in record
to avoid multiple matches on the same pair: when
try=1, any pair of adjacent tokens fits.
Then the procedure tries to find all the
possible matches in the repeat-until loop [2].
To find a match, the while loop [3] scans
all the rightmost tokens in mm1 while t2 remains
fixed. The marking [4] forbids
to select twice a token in mm1, while trying to
match the token t2 in mm2. If
the while loop exits because no more tokens t1 can
be selected (null t1) [5], then we 'unmark' all
the tokens in mm1 not in local-record
[6], in order for them to be selectable again in
the next step of the repeat-until loop.
Then we select a new pair of tokens for the
next step of the repeat-until loop [7].
With respect to the selection in [1], we
also have to exclude the pairs of tokens that matched
in the current attempt at Integration (in local-record).
Finally, t2 is marked because it failed all
the possible matches (each token in mm1 was tried
against it) and it is useless to re-select it.
Otherwise, if the while loop exits because
of a successful match [8], the token t3 that results
from the match is inserted in the matrix of tokens
of mm-integrated (initially empty), and the triple
<t1, t2, t3> is inserted in local-record.
The repeat-until loop exits when no more
tokens in mm1 or in mm2 are selectable anymore [9].
If
the set local-record is not empty
[10], i.e. some tokens have matched, then we update
record with the new matches (in
local-record). All
the new tokens t3 are already in the matrix of tokens
of mm-integrated (see the point [8]).
We have to complete the set of tokens in
mm3 with the other tokens that describe the two
states of affairs of mm1 and mm2 respectively [11].
The for loop [12] introduces the relations
in mm-integrated. Each relation
in mm1 or in mm2 is copied and, in case it involves
some token tx that matched [13], tx is replaced
by the token t3 that resulted from matching.
Eventually, the model mm-integrated is returned
as the result.
If
we had no match (local-record is
empty) and it is still possible to try a Re-arrange
(try_Re-arrange = 0) [14], we provide
a new arrangement of the tokens and of the models,
according to the re-arrangement functions described
in the text, and invoke again Integration.
After
an unsuccessful Integration that follows the first
Re-arrange, it is still possible that a Flesh-out
operation introduces new information and makes Integration
possible [15]. Re-arrange
is applicable again, in case Integration fails after
Flesh-out. Two Re-arranges are possible at most,
one before and one after Flesh-out.
If
all these attempts fail [16], Integration returns
a failure.
Function
Extractor-of-results
type
ExtractorStatus = {OK, FAILURE}
function
Extractor-of-results (integrated-model, extracted-model:
Model, task: Task): ExtractorStatus
case
task of
SYLL:
extracted-model
<- apply the transitivity of relations in integrated-model
delete
the middle terms from extracted-model and keep the
end terms
if
something goes wrong then
return FAILURE
return
OK
REL:
extracted-model
<- apply the transitivity of relations in integrated-model
delete
the middle terms from extracted-model and keep the
end terms
if
something goes wrong then
return FAILURE
return
OK
INFERENCE:
extracted-model
<- integrated-model
for
each token tx in extracted-model do
if
tx is one of the mathing tokens then
delete
tx from extracted-model
if
something goes wrong then
return FAILURE
return
OK
JUDGEMENT:
if
identity(mm1, integrated-model)=TRUE
then
return
OK
return
FAILURE
ACTION:
extracted-model
<- integrated-model
if
extracted-model contains a token tx of type 'action'
then
delete
all the tokens but tx from extracted-model
if
something goes wrong then
return FAILURE
return
OK
return
FAILURE
end
The
code of the algorithm Extractor-of-results is self-explaining.
We
only add a comment on transitivity of relations.
Relations are (see the ontology): CW = Connected
With; NCW = Never Connects With; AA = Above; BE
= Below; SA = Same height. Specifically:
<CW,a,b>
and <CW,b,c>
then <CW,a,c>
<CW,a,b>
and <NCW,b,c>
then <NCW,a,c>
<NCW,a,b>
and <NCW,b,c>
then <NCW,a,c>
<AB,a,b>
and <AB,b,c>
then <AB,a,c>
<BE,a,b>
and <BE,b,c>
then <BE,a,c>
<SA,a,b>
and <SA,b,c>
then <SA,a,c>
<AB,a,b>
and <SA,b,c>
then <AB,a,c>
<BE,a,b>
and <SA,b,c>
then <BE,a,c>
Function
Falsification
type
FalsificationStatus = {END, INCONSISTENCY}
function
Falsification(task: Task; mm1, mm2, new-mm-result:
Model): FalsificationStatus
/*
mm-result is the current model in the working memory
*/
begin
[1]
while Search-for-alternatives(mm1,
mm2, new-mm-int) = OK do
[2]
if Consistency&Equivalence(task,new-mm-int,mm-result,
new-mm-result) = INCONSISTENCY
[3]
then return
INCONSISTENCY
[4]
let new-mm-result be the current model in
the working memory
return
END
end
Comments
to the algorithm Falsification.
Falsification
consists of three subfunctions, the task-independent
Search-for-alternatives and the task-dependent Consistency&-Equivalence.
While the Search-for-alternatives is able
to provide a new integrated model (new-mm-int) [1],
Falsification invokes the Consistency&Equivalence,
which produces a new result model (new-mm-result)[2]:
if the new result model is inconsistent with the
current result model (mm-result), Falsification
returns an inconsistency[3]; otherwise, new-mm-result
is the new current result model, and Falsification
returns END [4].
Function
Search-for-alternatives
type
SearchStatus = {OK, END}
function
Search-for-alternatives(mm1, mm2, mm-int: Model):
SearchStatus
global
var try-search: integer, initially 1
local
var mm: Model
begin
[1]
while Integration(mm1, mm2, mm-int)=OK
and try-search=1 do
return
OK;
try-search
<- try-search + 1
[2]
while mm <- Flesh- out (mm1, mm2)
is successful do
if
Integration(mm, mm2, mm-int)=OK then
return
OK;
[3]
for each integrated model mm do
while
Token-moving(mm, mm-int) = OK do
return
OK;
return
END;
end
Comments
to the algorithm Search-for-alternatives.
The
function Search-for-alternatives returns a new integrated
model at each call until possible. The global variable
try-search keeps distinct the calls which require
an Integration and the following ones. First, it
tries some new Integration [1] (remember that, to
prevent the return of an old integrated model, the
variable record stores the tokens that matched).
Then, it tries to flesh out some implicit
models [2] and applies again Integration.
Finally, the procedure Token-moving is called
[3]. Token moving duplicates
the free tokens, and moves them
to free positions in the matrix of the model.
In all the three phases ([1], [2], [3]) the
function yields a new integrated model.
When it is not able to produce a new integrated
model, it returns END.
Consistency-&-Equivalence
type
ConsistencyStatus = {OK, FAILURE, INCONSISTENCY}
function
Consistency-&-Equivalence (task: Task; mm-int,
mm-res: Model): ConsistencyStatus
local
var mm: Model
begin
if
Extractor-of-results(mm-int, mm, task)=FAILURE
then
[1]
return FAILURE
[2]
if consistency(mm-res, mm, task)=INCONSISTENCY
then
return
INCONSISTENCY;
[3]
if equivalence(mm-res, mm, task)=FALSE
then
[4]
evaluate the loosest between mm-res and mm;
make
the loosest model the current result model;
return
OK;
end
Comments
to the algorithm Consistency-&-Equivalence.
The
function Consistency-&-Equivalence calls the
Extractor-of-results to yield a new result model.
If there occurs an extraction error, the function
returns FAILURE [1]. Otherwise, the function check
the consistency between the old and the new result
models. Consistency depends on the task, and implements
the following inconsistency tests [2]:
Syllogisms:
both relations <CW,x,y,A1>
and <NCW,x,y,A2>
occur.
Relational:
both relations <AB,x,y,A1>
and <BE,x,y,A2>,
or both <AB,x,y,A1>
and <SA,x,y,A3>
occur.
Propositional:
in mm-res there is a token x and in mm
there
is a token not-x.
If
the two result models pass Consistency, the function
tests whether they are equivalent. Also the equivalence
check depends on the task, and implement the following
equivalence tests [3]:
Syllogistic
and Relational: The elements in the two models have
the same names (even if the two models have a different
number of elements), and participate in the same
relations (i.e. relations with the same relation
symbol and the same argument names), possibly none.
Propositional:
The tokens (models) in the two models have the same
analogical structure <T, R, A>.
If
the two result models are equivalent, there is no
necessity to update the current result model, which
remains inalterate. If the two result models are
not equivalent (FALSE), the function keeps in the
working memory the loosest of the two. The evaluations
for looseness [4] are the following:
Syllogisms
and Relational: if one model contains more free
tokens than the other;
Propositional:
at least a token x in one model which is not in
the other.
Function
Generator-of-responses
type
Status = {FAILURE,INCONSISTENCY,END}
function
Generator-of-responses (task: Task; flag: Status):
void
let
m be the current result model in the working memory
if
flag is in {FAILURE, INCONSISTENCY}
and
task is not JUDGEMENT then
print
('No valid conclusion');
return;
case
task of
SYLL:
if
all the tokens of class x are in relation CW with
tokens of class y then
print
('All x are y');
if
at least one token x is in relation CW with a token
y and at least one x is not then
print
('Some x are y');
if
all the tokens of class x are in relation NCW with
all the tokens of class y then
print
('No x are y');
if
at least one token x is in relation NCW with all
the tokens y and at least one x is not then
print
('Some x are not y');
return;
REL:
let
x be the token on the left of the matrix
let
y be the token on the right of the matrix
if
the position of x is higher that the position of
y in the matrix then
print
('x is more W
than y');
if
the position of x is lower that the position of
y in the matrix then
print
('x is less W
than y')
return;
INFERENCE:
if
there is a (non annotated) token z in m then
print('There
is z');
if
there is a token z annotated with NOT then
print('There
is not z');
return;
JUDGEMENT:
if
flag = END then
print('TRUE')
else
print('FALSE')
return;
ACTION:
if
the unique token in m represents action a
then
print('Execute
action a')
if
the unique token in m blocks action a
then
print('Do
not execute action a
')
return;
end
|
