Accession Number : AD0675648

Title :   REGULAR EXPRESSIONS AND THE EQUIVALENCE OF PROGRAMS,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Kaplan,Donald M.

Report Date : 01 JUL 1968

Pagination or Media Count : 47

Abstract : The strong equivalence of ALGOL-like programs is, in general, an undecidable property. Several mechanical procedures are discussed which nevertheless are useful in the detection of strong equivalence. These methods depend on a regular expression representation of programs. An unorthodox semantics for these expressions is introduced which appreciably adds to the ability to detect strong equivalence. Several other methods of extending this ability are also discussed. (Author)

Descriptors :   (*PROGRAMMING LANGUAGES, MATHEMATICAL LOGIC), ARTIFICIAL INTELLIGENCE, SEMANTICS, ALGORITHMS, AUTOMATA, SEQUENCES(MATHEMATICS), THEOREMS

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE