The
algorithms
This
annex contains the pseudocode 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, mmintegrated: Model): IntegrationStatus
global
var record: array of triples of tokens, initially
empty;
global
var try_Rearrange: integer, initially 0;
global
var try_Fleshout: integer, initially 0;
var
localrecord: 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 localrecord
[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 localrecord
mark
t2
[8]
else
store
t3 in mmintegrated
store
<t1, t2, t3> in localrecord
[9]
until null t1 or null t2
[10]
if localrecord is not empty then
update
record with the triples in localrecord
[11]
store all the tokens in mm1 or mm2 that did
not match in mmintegrated
[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 localrecord then
replace
tx with t3 in r'
store
r' in mmintegrated
return
OK
[14]
if localrecord is empty and
try_Rearrange=0 then
Rearrange(mm1,
mm2)
try_Rearrange
< try_Rearrange + 1
return(Integration(mm1,
mm2, mmintegrated))
[15]
if localrecord is empty and
try_Fleshout=0 then
Fleshout(mm1,
mm2)
try_Fleshout
< try_Fleshout + 1
try_Rearrange
< 0
return(Integration(mm1,
mm2, mmintegrated))
[16]
return FAILURE
end
Comments
to the algorithm Integration.
Integration
takes as input two models mm1 and mm2, and returns
a model mmintegrated. 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_Rearrange and try_Feshout,
initially set to 0, represents the number of attempts
to restructure information. Finally,
the local variable localrecord
keeps track of the matches that occurred in the
current attempt at Integration: the triples stored
in localrecord are then the kernel of the integrated
model. The global variable
record is updated with the triples
in localrecord.
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 repeatuntil 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 localrecord
[6], in order for them to be selectable again in
the next step of the repeatuntil loop.
Then we select a new pair of tokens for the
next step of the repeatuntil 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 localrecord).
Finally, t2 is marked because it failed all
the possible matches (each token in mm1 was tried
against it) and it is useless to reselect 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 mmintegrated (initially empty), and the triple
<t1, t2, t3> is inserted in localrecord.
The repeatuntil loop exits when no more
tokens in mm1 or in mm2 are selectable anymore [9].
If
the set localrecord is not empty
[10], i.e. some tokens have matched, then we update
record with the new matches (in
localrecord). All
the new tokens t3 are already in the matrix of tokens
of mmintegrated (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 mmintegrated. 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 mmintegrated is returned
as the result.
If
we had no match (localrecord is
empty) and it is still possible to try a Rearrange
(try_Rearrange = 0) [14], we provide
a new arrangement of the tokens and of the models,
according to the rearrangement functions described
in the text, and invoke again Integration.
After
an unsuccessful Integration that follows the first
Rearrange, it is still possible that a Fleshout
operation introduces new information and makes Integration
possible [15]. Rearrange
is applicable again, in case Integration fails after
Fleshout. Two Rearranges are possible at most,
one before and one after Fleshout.
If
all these attempts fail [16], Integration returns
a failure.
Function
Extractorofresults
type
ExtractorStatus = {OK, FAILURE}
function
Extractorofresults (integratedmodel, extractedmodel:
Model, task: Task): ExtractorStatus
case
task of
SYLL:
extractedmodel
< apply the transitivity of relations in integratedmodel
delete
the middle terms from extractedmodel and keep the
end terms
if
something goes wrong then
return FAILURE
return
OK
REL:
extractedmodel
< apply the transitivity of relations in integratedmodel
delete
the middle terms from extractedmodel and keep the
end terms
if
something goes wrong then
return FAILURE
return
OK
INFERENCE:
extractedmodel
< integratedmodel
for
each token tx in extractedmodel do
if
tx is one of the mathing tokens then
delete
tx from extractedmodel
if
something goes wrong then
return FAILURE
return
OK
JUDGEMENT:
if
identity(mm1, integratedmodel)=TRUE
then
return
OK
return
FAILURE
ACTION:
extractedmodel
< integratedmodel
if
extractedmodel contains a token tx of type 'action'
then
delete
all the tokens but tx from extractedmodel
if
something goes wrong then
return FAILURE
return
OK
return
FAILURE
end
The
code of the algorithm Extractorofresults is selfexplaining.
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, newmmresult:
Model): FalsificationStatus
/*
mmresult is the current model in the working memory
*/
begin
[1]
while Searchforalternatives(mm1,
mm2, newmmint) = OK do
[2]
if Consistency&Equivalence(task,newmmint,mmresult,
newmmresult) = INCONSISTENCY
[3]
then return
INCONSISTENCY
[4]
let newmmresult be the current model in
the working memory
return
END
end
Comments
to the algorithm Falsification.
Falsification
consists of three subfunctions, the taskindependent
Searchforalternatives and the taskdependent Consistency&Equivalence.
While the Searchforalternatives is able
to provide a new integrated model (newmmint) [1],
Falsification invokes the Consistency&Equivalence,
which produces a new result model (newmmresult)[2]:
if the new result model is inconsistent with the
current result model (mmresult), Falsification
returns an inconsistency[3]; otherwise, newmmresult
is the new current result model, and Falsification
returns END [4].
Function
Searchforalternatives
type
SearchStatus = {OK, END}
function
Searchforalternatives(mm1, mm2, mmint: Model):
SearchStatus
global
var trysearch: integer, initially 1
local
var mm: Model
begin
[1]
while Integration(mm1, mm2, mmint)=OK
and trysearch=1 do
return
OK;
trysearch
< trysearch + 1
[2]
while mm < Flesh out (mm1, mm2)
is successful do
if
Integration(mm, mm2, mmint)=OK then
return
OK;
[3]
for each integrated model mm do
while
Tokenmoving(mm, mmint) = OK do
return
OK;
return
END;
end
Comments
to the algorithm Searchforalternatives.
The
function Searchforalternatives returns a new integrated
model at each call until possible. The global variable
trysearch 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 Tokenmoving 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; mmint,
mmres: Model): ConsistencyStatus
local
var mm: Model
begin
if
Extractorofresults(mmint, mm, task)=FAILURE
then
[1]
return FAILURE
[2]
if consistency(mmres, mm, task)=INCONSISTENCY
then
return
INCONSISTENCY;
[3]
if equivalence(mmres, mm, task)=FALSE
then
[4]
evaluate the loosest between mmres 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
Extractorofresults 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,A_{1}>
and <NCW,x,y,A_{2}>
occur.
Relational:
both relations <AB,x,y,A_{1}>
and <BE,x,y,A_{2}>,
or both <AB,x,y,A_{1}>
and <SA,x,y,A_{3}>
occur.
Propositional:
in mmres there is a token x and in mm_{
}there
is a token notx.
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
Generatorofresponses
type
Status = {FAILURE,INCONSISTENCY,END}
function
Generatorofresponses (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
