The Formal Theoretic Analysis of Strong Equivalence for Elemental Programs

摘要

The syntax and semantics is given for elemental programs, and the strong equivalence of these simple ALGOL-like flow-charts is shown to be undecidable. A formal theory is introduced for deriving statements of strong equivalence, and the completeness of this theory is obtained for various sub-cases. Several applications of the theory are discussed. Using a regular expression representation for elemental programs and an unorthodox semantics for these expressions, several strong equivalence detecting procedures are developed. (Author)