Title: A similarity criterion for sequential programs using truth-preserving partial functions,
Abstract: The execution of sequential programs allows them to be represented using
mathematical functions formed by the composition of statements following one
after the other. Each such statement is in itself a partial function, which
allows only inputs satisfying a particular Boolean condition to carry forward
the execution and hence, the composition of such functions (as a result of
sequential execution of the statements) strengthens the valid set of input
state variables for the program to complete its execution and halt succesfully.
With this thought in mind, this paper tries to study a particular class of
partial functions, which tend to preserve the truth of two given Boolean
conditions whenever the state variables satisfying one are mapped through such
functions into a domain of state variables satisfying the other. The existence
of such maps allows us to study isomorphism between different programs, based
not only on their structural characteristics (e.g. the kind of programming
constructs used and the overall input-output transformation), but also the
nature of computation performed on seemingly different inputs. Consequently, we
can now relate programs which perform a given type of computation, like a loop
counting down indefinitely, without caring about the input sets they work on
individually or the set of statements each program contains.