THE FORMAL THEORETIC ANALYSIS OF STRONG EQUIVALENCE FOR ELEMENTAL PROGRAMS.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 12, 1968
- Accession Number
- AD0672923
Entities
People
- Donald M. Kaplan
Organizations
- Stanford University