CSJ Archive > Contents > Supplemental Materials > Bara, Bucciarelli & Lombardo (2001):


Cognitive Science Journal | Supplemental Materials | Cognitive Science Conference Proceedings:


2001 — Volume 25 — Issue 6

  • Bruno G. Bara, Monica Bucciarelli and Vincenzo Lombardo,
    Model theory of deduction: A unified computational approach. (pdf)


    Supplemental Materials:

    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

     

     

     

 



^ Cognitive Science Journal Archive ^

The Cognitive Science Journal Archive currently contains electronic versions of 459 articles (of 98 issues and 24 years) of the Cognitive Science Journal and collects materials published in the Proceedings of the Annual Cognitive Science Conference. It is maintained by the CogWorks Laboratories of RPI's Cognitive Science Department.

CogWorks Labs, RPI
 CSJ Archive > Contents > Supplemental Materials > Bara, Bucciarelli & Lombardo (2001).