On Half Iterates of Functions Defined on Finite Sets

Abstract

Four algorithms determining all functional square roots (half iterates) and seven algorithms finding one functional square root of any function f : X ! X defined on a finite set X, if these square roots exist, are presented herein. Time efficiency of these algorithms depending on the complexity of examined functions is compared and justification of correctness is given. Moreover, theorems which make finding half iterates possible in some cases or facilitate this task are formulated.