Accession Number : AD0672923

Title :   THE FORMAL THEORETIC ANALYSIS OF STRONG EQUIVALENCE FOR ELEMENTAL PROGRAMS.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Kaplan,Donald M.

Report Date : 12 JUN 1968

Pagination or Media Count : 270

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)

Descriptors :   (*COMPUTER PROGRAMMING, THEORY), MATHEMATICAL LOGIC, SET THEORY, FLOW CHARTING, PROGRAMMING LANGUAGES, ARTIFICIAL INTELLIGENCE, SYNTAX, SEMANTICS, THEOREMS, THESES

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE