Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-04-20
2004-06-01
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S671000
Reexamination Certificate
active
06745215
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the determination of the equivalence of two algebraic functions, such as those used in computer programs. The present invention includes a method and apparatus for carrying out such a determination and also to a computer program product including a computer readable medium having recorded thereon a computer program for performing such determination.
The present invention has, for its object, a technique which is specifically relevant to the determination of whether or not two algebraic expressions share a common template or function definition. Expressed mathematically, the objective is applicable as follows.
Given an algebraic expression f(x
1
, x
2
, . . . , x
n
) of n-variables denoted by the symbol set {x
1
, x
2
, . . . , x
n
} and another expression g(y
1
, y
2
, . . . , y
n
)of n-variables denoted by the symbol set {y
1
, y
2
, . . . , y
n
} determine if there exists a permutation &sgr; of degree n on the set {y
1
, y
2
, . . . , y
n
} such that
g
(
y
1
, y
2
, . . . , y
n
)≡
f
(&sgr;(
y
1
), &sgr;(
y
2
), . . . , &sgr;(
y
n
)), n>0
where
x
1
=&sgr;(
y
1
),
x
2
=&sgr;(
y
2
), . . . ,
x
n
=&sgr;(
y
n
).
An identity would imply that f( ) and g( ) share a common template or function definition as mentioned earlier. The term “permutation” is defined as follows.
Let &OHgr; be a set consisting of n distinct objects, which we may denote either by digits or by letters, say
&OHgr;={1,2, . . . , n}.
Then a permutation on &OHgr; implies the mapping of objects 1 to n to the same objects but in a different order—this is called mapping of &OHgr; onto itself. A permutation &sgr; of degree n is an operation on the set &OHgr; which maps the digit i to the digit &sgr;(i) in such a way that &sgr;(i)≠&sgr;(j) when i≠j. We write
σ
=
(
1
2
…
n
σ
(
1
)
σ
(
2
)
…
σ
(
n
)
)
where the numbers &sgr;(1), &sgr;(2), . . . , &sgr;(n) are an arrangement of the numbers 1, 2, . . . , n.
Note that since there are n! distinct arrangements possible of n objects, there are n! distinct permutations in the form given above. For example, the permutation of degree 5 given by
σ
=
(
1
2
3
4
5
3
5
4
1
2
)
in which &sgr;(1)=3, &sgr;(2)=5 . . . , &sgr;(5)=2, may equally well be written in the form
σ
=
(
4
2
3
1
5
1
5
4
3
2
)
SUMMARY OF THE INVENTION
The invention comprises a method, apparatus and program product for determining the equivalence of two algebraic functions. In the invention, an algorithm is involved which comprises determining the symbol sets of the two functions; forming a matrix having a row for each symbol of one function and a column for each symbol of the other function; subjecting the functions to predetermined tests and incrementing the elements in the matrix in accordance with the results of said tests; and testing the matrix against predetermined rules for the symmetry of the matrix.
The algorithm may include comparing said symbol sets to determine whether they contain the same numbers of symbols.
The invention further provides a method, program and apparatus for determining the equivalence of two algebraic functions f( ) and g( ) having respective symbol sets {x
1
, x
2
, . . . , x
n
} and {y
1
, y
2
, . . . , y
n
} having equal numbers of symbols, the method comprising the steps of forming a matrix M with n rows and n columns and made up of elements M
ij
corresponding to respective pairs of said symbols x
i
and y
j
where M
ij
is calculated by initialising the values of M
ij
to zero; putting x
i
=0 in f( ) and y
j
=0 in g( ) and replacing each other variable in f( ) and g( ) with a predetermined string character, then arranging the terms of f( ) and g( ) in ASCII order and comparing them and, if they match, incrementing the current value of M
ij
; putting x
i
=1 in f( ) and y
j
=1 in g( ) and replacing each other variable in f( ) and g( ) with a predetermined string character, then arranging the terms of f( ) and g( ) in ASCII order and comparing them and, if they match, incrementing the current value of M
ij
; putting x
i
=−1 in f( ) and y
j
=−1 in g( ) and replacing each other variable in f( ) and g( ) with a predetermined string character, then arranging the terms of f( ) and g( ) in ASCII order and comparing them and, if they match, incrementing the current value of M
ij
; ensuring that every element M
ij
is either a zero or a three and that each row of the matrix M contains at least one three; for each entry M
ij
which has the value three, exchanging the contents of columns i and j one with another; and inspecting the matrix M with the exchanged columns to determine if it is symmetrical.
The method and apparatus may further comprise analysing computer code containing first and second algebraic functions f(x
1
, x
2
, . . . , x
n
) and g(y
1
, y
2
, . . . , y
n
), the method being operable for analysing a relationship between said first and second functions and comprising the steps of:
(a) in each term in each function, replacing each variable name in that term with a predetermined symbol to form two character strings F( ) and G( ) each composed of sub-strings corresponding to respective terms of the respective function;
(b) arranging the sub-strings of each string in a like predetermined order; and
(c) comparing the strings one with another to determine equivalence of the two functions.
Preferably, the method further includes taking each variable x
i
of the first function f(x
1
, x
2
, . . . , x
n
) and running through variables y
j
of the second function g(y
1
, y
2
, . . . , y
n
) one-by-one and carrying out the steps of:
(a) removing all the terms in the first function which contain x
i
and all the terms in the second function which contain y
j
and, in each remaining term of each function, replacing each variable with a predetermined symbol and rearranging said terms in a predetermined order to form two character strings f
0
( ) and g
0
( );
(b) replacing each variable x
i
and y
j
by the value 1, replacing each remaining variable with a single predetermined symbol, and rearranging the terms of the functions in a predetermined order as two character strings f
1
( ) and g
1
( );
(c) replacing each variable x
i
and y
j
by the value −1, replacing each remaining variable with a single predetermined symbol, and rearranging the terms of the functions in a predetermined order as two character strings f
−1
( ) and g
−1
( );
(d) carrying out respective character string matching operations to determine if f
0
( ) is identical to g
0
( ), if f
1
( ) is identical to g
1
( ), and if f
−1
( ) is identical to g
−1
( ).
REFERENCES:
patent: 6032144 (2000-02-01), Srivastava et al.
patent: 6061676 (2000-05-01), Srivastava et al.
Coca T. Rao
England Anthony V. S.
Mai Tan V.
Schecter Manny
LandOfFree
Computer apparatus, program and method for determining the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer apparatus, program and method for determining the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer apparatus, program and method for determining the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3295367