A polynomial determination of the most-recent property in Pascal-like programs

AbstractIf a compiler knew which procedures (or functions) of a program fulfill the most-recent property, it could produce more adequate code. This stands in contrast to the prevailing tacit worst-case assumption on the non-most-recent behavior of those procedures being passed as parameters (for all other procedures this property holds trivially). This old and well-known phenomenon will attract new attention with the development of new computer architectures—such as RISC.We present a method which has a polynomial time complexity (in program length) for deciding this property in Wirth-Pascal-like programs by exploiting the inherent restriction concerning formal procedures. It is this restriction that enables us to 1.(1) (polynomially) reduce the most-recent problem to a reachability problem for certain procedures and2.(2) solve this reachability problem with the polynomial algorithm which we present. This polynomial result for such programs is rather unexpected since, for programs in slightly less restricted languages like ISO-Pascal, the problem is still decidable but with a complexity as bad as P-space complete