ACM Home Page
Please provide us with feedback. Feedback
An Assessment of Techniques for Proving Program Correctness
Full text PdfPdf (4.36 MB)
Source ACM Computing Surveys (CSUR) archive
Volume 4 ,  Issue 2  (June 1972) table of contents
Pages: 97 - 147  
Year of Publication: 1972
ISSN:0360-0300
Authors
Bernard Elspas  Information Science Laboratory, Stanford Research Institute, Menlo Park, California
Karl N. Levitt  Information Science Laboratory, Stanford Research Institute, Menlo Park, California
Richard J. Waldinger  Information Science Laboratory, Stanford Research Institute, Menlo Park, California
Abraham Waksman  Information Science Laboratory, Stanford Research Institute, Menlo Park, California
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 7,   Downloads (12 Months): 78,   Citation Count: 53
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/356599.356602
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
AMAREL, S. "An approach to heuristic problem solving and theorem prowng in the propositional calculus." In Systems and computer science, Hart and Takasu (Eds.), Univ. Toronto Press, Toronto, Ont., Canada, 1967.
 
2
ANDERSON, l:{. "Completeness results for E- esolution." In Proc. AFIPS 1970 SJCC, Vol. 36, AFIPS Press, Montvale, N.J., 653-656
3
 
4
ANDREWS, P. B. "Resolution in type theory." Dept of Mathematics, Carnegie Mellon Univ., Pittsburgh, Pa, 1970
 
5
BURGE, W. H "Provlng the correctness of a compiler." IBM Research Rept RC 2111, Yorktown Heights, N.Y, June 1969
 
6
BURSTALL, R M "Proving properties of programs by structural induction." Computer J. 12, 1 (Feb 1969), 41-48
 
7
 
8
COOPER, D. C "Program scheme equivalences and second order logic." In Machine ,ntelhgence 4, B. Meltzer and D. Mlchie (Eds.), American Elsevier Publ. Co., New York, 1969, 3-15.
 
9
DARI,INGTON, J. L. "Automatic theorem proving with equality substitution and mathematical induction." In Machine ~ntelligence 3, D. Miehm (Ed.), American Elsevier Publ. Co., New York, 1968, 113-127.
 
10
DAvis, M. Computability and unsolvabiIity McGraw-Hill Book Co , New York, 1958.
11
 
12
DE BAKKER, J W. "Semantics of programming languages." In Advances ~n znformatwn systems sczence, Vol 2, J. T. Ton (Ed.), Plenum Press, New York, 1969.
 
13
DIJKSTRA, E. W. "A constructive approach to the problem of program correctness " BIT 8, 3 (1968), 174-186.
 
14
DIJKSTRA, E W. "Notes on structured programming." TH Rept 70-WSK-03, 2nd ed., Technische Hogeschool, Eindhoven, The Netherlands, April 1970.
 
15
ELsPAS, B.; M W. GREEN; AND K. N. LEVITT. "Software reliability." Computer 4, 1 (Jan.- Feb. 1971), 21-27
 
16
FLORENTIN, J J. "Language definitmn and computer validation " In Machine ~nteIligence S, D. Michie (Ed.), American Elsevier Publ. Co., New York, 1968, 33-41.
 
17
FLOYD, R W A protocol of an ~maginary program retailer. Preliminary draft, July 1967.
 
18
FLOYD, R. W. "Assigning meanings to programs." In Mathematical aspects of computer science, Vol. 19, J. T. Schwartz (Ed), Amer. Math. Soc , Providence, R.I, 1967, 19-32
 
19
GOLDSTINE, H. H.; AND J. YON NEUMANN "Planning and coding problems for an electronic computer instrument, part 2, vol 1-3." In John yon Neumann collected works, Vol. 5, A. H. Taub (General Ed.), Pergamon Press, New York, 1963, 80-235.
 
20
 
21
GOVLD, W. E. "A matching procedure for ~-order logic." PhD Thesis, Princeton Univ., Princeton, N.J., 1966.
 
22
GREEN, C. "Application of theorem proving to problem solving." In Proc. Internat. Joznt Conf. on A rhfic~al InteIhgence, D. E. Walker and L. M. Norton (Eds.), Mitre Corp , Bedford, Mass., 1969, 219-239.
 
23
GREF~N, C. "The application of theorem proving to question-answering systems." Tech. Note 8, SRI Project 7494, Stanford Research Inst., Menlo Park, Calif., June 1969.
 
24
GREEN, C. "Theorem proving by resolution as a basis for question-answering systems." In Machine intelhgence ~4, B. Meltzer and D. Michie (Eds.), Edinburgh Univ. Press, Edinburgh, Scotland, 1969, 183-205
 
25
GREEN, M. W.; B. ELs~As; AND K. N. LEVITT. "Translation of recursive schemas into labelstack flow-chart schemas." Prehminary draft, Stanford Research Inst., Menlo Park, Calif., June 1971.
26
 
27
HAYES, P. J. "A machine-oriented formulation of the extended functmnal calculus " Stanford Artificial Intelligence Project, Memo 62; also appeared as Metamathematics Unit Report, Univ. Edinburgh, Scotland, 1969.
 
28
HEaBR.~ND, J. "Recherches sur la th~orie de la d6monstration." Travaux de la Societ6 des Sciences et des Lettres de Varsovm, Classe IiI, No. 33, Paris, 1930.
 
29
HEWlTT, C. "More comparative schematology." Artificial Intelligence Memo No. 207, Project MAC, MIT, Cambridge, Mass., Aug. 1970.
30
 
31
IANOV, Y. I. "The logical schemes of algorithms " In Problems of cybernetics, Vol 1, Translated from the Russmn by Nadler, Grifi~ths, Kms, and Muir, Pergamon Press, New York, 1960, 82-140
 
32
KAPLAN, D. M. "Proving things about programs." Presented at ~th Annual Pmnceton Conf. on Information Science and Systems, Princeton Univ, March 1970.
 
33
34
 
35
KLEENE, S. C Introductwn to metamathemattes, D. Van Nostrand Co., Inc, Princeton, N.J., 1952.
 
36
KONIG, D. Theome der endlichen ur~d unendl~chen Graphen Chelsea Publ. Co., Bronx, N Y, 1950, 81
 
37
LANDIN, P. J ; AND ~. M. BURSTALL "Programs and their proofs: an algebraic approach." In Machzne ~ntell, gence 4, B. Meltzer and D. Mlchie (Eds.), American Elsevmr Publ. Co, New York, 1969
 
38
LEAVENWORTH, B. Review of paper by P Naur {"Programming by action clusters " BIT 9, 3 (1969), 250-258}. Computing Reviews ll, 7 (July 1970), Rev. 19,420
 
39
LONDON, }~. L. "Computer programs can be proved correct " In Proc ~th Systems Symposium-Formal Systems and Non-Numemcal Problem Solwng by Computers, held at Case Western Reserve Univ., November 1968, R. B. Banerji and M D. Mesarovic (Eds.), Springer Verlag, New York, 1970, 281-302.
40
 
41
LONDON, ~. L "Bibliography on proving the correctness of computer programs." In Machine ~ntellzgence 5, B Meltzer and D Michie (Eds.), American Elsevier Publ. Co., New York, 1970, 569-580.
 
42
LONDON, ~. L. "Software reliability through proving programs correct " Publ 71C 6-C, IEEE Computer Society, New York, March 1971
 
43
LONDON, }:{. L.; AND J. H. HA.LTON. "Proofs of algorithms for asymptotic series " Computer Sciences Tech Rept No. 54A, Univ Wisconsin, Madison, Wise , May 1969.
 
44
LOVELAND, D. A "A linear format for resolution " Proc Symposium on Automatw Deductwn, Inst de Recherche d'Informatique et d'Automatique, Versailles, France, Dec. 1968 In Lecture notes ~n mathematzcs, No 125, Springer Verlag, New York, 1970.
 
45
LUCKHAM, }_). "Some tree-paring strategies for theorem-proving " In Machine ,ntelligence 3, D. Michie (Ed), American Elsevier Publ. Co., York, 1968, 95-112.
 
46
LUCKUa~, D "Refinement theorems in resolution theory " Proc. Symposium on Automatzc Deductwn, Inst. de Recherche d'Informatique et d'Automa~lque, Versailles, France, Dec. 1968. In Lecture notes ~n mathematics, No. 125, Springer Verlag, New York 1970; also in Stunford Artificial Intelhgence Project Memo AI-81, 1969
 
47
LUCKHAM, D. C.; D. M. R. PAR~; AND M S. PATERSOn. "On formalized computer programs " J. Computer & System Sciences 4, 3 (June 1970), 220-249.
48
 
49
MANNA, Z. "The correctness of programs." J. Compu~,er & System Sciences 3, 2 (May 1969), 119-127.
50
 
51
MANNA, Z.; AND J. MCCARTHY "Properties of programs and partial functmn logic " In Macine mtelhgence 5, B. Meltzer and D. Mlchie (Eds.), American Elsevier Publ .Co., New York, 1970, 27-37
 
52
MANNA, Z.; AND A PNUELI "The validity problem of the 91-function." Artificial Intelligence Memo No 68, Stanford Univ., Stanford, Calif., Aug. 1968
53
54
55
 
56
MCCARTHY, J. "A basis for a mathematical theory of computation." In Computer programm~ng and formal systems, P Braffort and D. Hirschberg (Eds.), North-Holland Publ. Co., Amsterdam, 1963, 33-70; also ia Proc. Western Joint Computer Conf, Vol. 19, Spartan Books, New York, 1961, 225-238
 
57
McCAaTHY, J "Towards a mathematical science of computation " In Proc. IFIP Cong. 62, C. M Popplewell (Ed.), North-Holland Publ. Co , Amsterdam, 1963, 21-28.
 
58
MCCARTHY, J ; AND J A. PAINTER "Correctness of a compiler for arithmetic expressmns." In Mathematical aspects of computer science, Vol. 19, J T. Schwartz (Ed), Amer. Math Soc , Providence, R I , 1967, 33-41
 
59
MEJ~ZER, B. "Theorem-proving for computers some results on resolution and renaming." Computer J 8, 4 (Jan. 1956), 341-343.
 
60
 
61
Mo~s, J. B., J~. "E-resolutmn: extension of resolutmn to include the equality relation." In Proc. Internatl. Joint Conf. on Artificial Intelligence, D. E. Walker and L M. Norton (Eds), The Mitre Corp , Bedford, Mass., 1969, 287-294
 
62
NAun, P. "Proof of algorithms by general snapshots " BIT 6, 4 (1966), 310-316.
 
63
NAun, P. "Programming by action clusters." BIT 9, 3 (1969), 250-258.
 
64
NEWELL, A.; J C SH~W; AND H. A. SIMON. "Empirical explorations of the logic theory machine a case study in heuristic " In Proc. Western Joint Computer Conf , Vol. 11, Spartan Books, New York, 1957, 218-230.
 
65
PARK, D. "F1xpomt induction and proofs of program properties " In Machine ~ntelhgence 5, B Meltzer and D Michie (Eds), American Elsevier Publ. Co , New York, 1969, 59-78.
 
66
PATERSON, M S. "Equivalence problems in a model of computation " PhD Thesis, Cambridge Univ., Cambridge, England, Aug. 1967.
 
67
PATERSON, M S ; AND C E. HEWITT. "Comparative schematology " In Record o~ the Prosect MAC Conf on Concurrent Systems and Parallel Computatwn, ACM:, New York, 1970, 119-127
 
68
PI~AWlTZ, D. "An improved proof procedure " Theorm 26, (1980), 102-139.
 
69
ROBINSON, G ;AND L. WoN. "Paramodulation and theorem-proving ~n first-order theories with equality " In Machine zntelhgence 4, B. Meltzer and D. Michm (Eds.), American Elsevier Publ. Co, New York, 1969, 135-150.
70
 
71
ROBINSON, J. A. "Automatic deduction with hyper-resolutlon " Internatl J. Computer Math 1, (1965), 227-234
 
72
ROBINSON, J A. "Mechanizing htgher-order logic " In Machine ~ntelhgence 4, B Meltzer and D Mlchle (Eds.), Amerman Elsevier Publ. Co., New York, 1969, 151-170
 
73
 
74
RULXFSON, J. F, R. J. WALDINGER, AND J. DERKSEN "A language for wmting problemsolving programs " Presented at IFIP Cong. 1971, Ljubljana, Yugoslavia, Aug 1971, North- Holland Publ. Co, Amsterdam, 1972.
 
75
RUSSELL, B;AND A N WHITEHEAD Pr~ncipia mathematzca, Vo{s 1-3. University Press, Cambridge, England, 1925-7 (2d ed.).
76
77
78
79
 
80
WALDINGER, R J "Constructing programs automatically using theorem proving." PhD Thesis, Carnegie-Mellon Univ., Pittsburgh, Pa., 1969
 
81
WALDINGER, R J.; AND R. C. T. LEE. "PRow: a step toward automatic program writing " In Proc Internat Joint Conf. on Art~ficzal Intelhgence, D. E Walker and L. M Norton (Eds), Mitre Corp, Bedford, Mass., 1969, 241-252.
 
82
WANG, H "Toward mechanical m~thematics." IBM d. R & D 4, (1960), 2-22.
 
83
WENSbEY, J. H. "A class of non-analytical iteratlve processes " Computer J. 1, (1958), 163-167
84
 
85
Wos, L ; D. F. CARSON; AND G. A ROBINSON. "The unit preference strategy in theorem proving" In Proc. I964 FJCC, Vol 26, Pt 1, Spartan Books, New York, 615-621
 
86
YATES, R, B RAPHAEL; AND T. P HART. "Resolution graphs." Artificial Intelligence Group, Stanford Research Inst. Tech. Note 24, Menlo Park, Callf, 1970

CITED BY  53

Collaborative Colleagues:
Bernard Elspas: colleagues
Karl N. Levitt: colleagues
Richard J. Waldinger: colleagues
Abraham Waksman: colleagues