Toward automatic program synthesis
Open accessAbstract
An elementary outline of the theorem-proving approach to automatic program synthesis is given, without dwelling on technical details. The method is illustrated by the automatic construction of both recursive and iterative programs operating on natural numbers, lists, and trees. In order to construct a program satisfying certain specifications, a theorem induced by those specifications is proved, and the desired program is extracted from the proof. The same technique is applied to transform recursively defined functions into iterative programs, frequently with a major gain in efficiency. It is emphasized that in order to construct a program with loops or with recursion, the principle of mathematical induction must be applied. The relation between the version of the induction rule used and the form of the program constructed is explored in some detail.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Program synthesis automatically generates source code in a programming language using user-specified constraints.
“Using user-specified constraints, program synthesis (or source code generation) automatically generates source code in a programming language (Waldinger et al. 1969; Manna and Waldinger 1971).”
From Large language models (LLMs): survey, technical frameworks, and future challenges (2024) · cites this paper as Manna and Waldinger 1971
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
A Machine-Oriented Logic Based on the Resolution Principle
Robinson, J. A. (1965) · Journal of the ACM · doi:10.1145/321250.321253 · Cited by 3,916 · see citing works
An Introduction to Mathematical Logic
Mendelson, E. (2005) · A K Peters/CRC Press eBooks · doi:10.1201/b13782-17 · Cited by 1,739 · see citing works
Assigning meanings to programs
Floyd, R. W. (1967) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/019/0235771 · Cited by 1,411 · see citing works
A Basis for a Mathematical Theory of Computation )
Mccarthy, J. (1963) · Studies in logic and the foundations of mathematics · doi:10.1016/s0049-237x(08)72018-4 · Cited by 695 · see citing works
Towards a Mathematical Science of Computation
McCarthy, J. (1993) · Studies in cognitive systems · doi:10.1007/978-94-011-1793-7_2 · Cited by 529 · see citing works
Green, C. (1981) · Elsevier eBooks · doi:10.1016/b978-0-934613-03-3.50019-2 · Cited by 459 · see citing works
Proving Properties of Programs by Structural Induction
Burstall, R. M. (1969) · The Computer Journal · doi:10.1093/comjnl/12.1.41 · Cited by 326 · see citing works
Application of Theorem Proving to Problem Solving
Green, C. (1969) · doi:10.21236/ada459656 · Cited by 290 · see citing works
King, J. C. (1970) · IFIP Congress · Cited by 208 · see citing works
Introduction to Mathematical Logic.
Evans, T. V., & Mendelson, E. (1966) · American Mathematical Monthly · doi:10.2307/2313586 · Cited by 187 · see citing works
Manna, Z. (1969) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(69)80009-7 · Cited by 132 · see citing works
Self-citationPROW: a step toward automatic program writing
Waldinger, R. J., & Lee, R. C. T. (1969) · International Joint Conference on Artificial Intelligence · Cited by 114 · see citing works
Self-citationThe use of theorem-proving techniques in question-answering systems
Green, C. C., & Raphael, B. (1968) · ACM National Conference · doi:10.1145/800186.810578 · Cited by 114 · see citing works
The application of theorem proving to question-answering systems
Green, C. C. (1969) · Stanford University eBooks · Cited by 102 · see citing works
E-Resolution: Extension of Resolution to Include the Equality Relation
Morris, J. B. (1983) · Springer eBooks · doi:10.1007/978-3-642-81955-1_17 · Cited by 86 · see citing works
Formalization of Properties of Functional Programs
Manna, Z., & Pnueli, A. (1970) · Journal of the ACM · doi:10.1145/321592.321606 · Cited by 76 · see citing works
Self-citationExperiments with a deductive question-answering program
Slagle, J. R. (1965) · Communications of the ACM · doi:10.1145/365691.365960 · Cited by 71 · see citing works
Experiments with a Heuristic Compiler
Simon, H. A. (1963) · Journal of the ACM · doi:10.1145/321186.321192 · Cited by 65 · see citing works
Extracting information from resolution proof trees
Luckham, D. C., & Nilsson, N. J. (1971) · Artificial Intelligence · doi:10.1016/0004-3702(71)90003-8 · Cited by 61 · see citing works
CONSTRUCTING PROGRAMS AUTOMATICALLY USING THEOREM PROVING.
Waldinger, R. J. (1969) · Cited by 33 · see citing works
Self-citationMathematical logic applied to the semantics of computer programs
Ashcroft, E. A. (1970) · Spiral (Imperial College London) · Cited by 15 · see citing works
An interpretation oriented theorem prover over integers
King, J. C., & Floyd, R. W. (1970) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800161.805162 · Cited by 15 · see citing works
Translating recursion equations into flow charts
Strong, H. R. (1970) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800161.805164 · Cited by 15 · see citing works
Flagged first, then by citations
1 of the 24 references couldn’t be matched to a known paper.
Research works printed but not linked: 4
- ----. Formal description of program structure and semantics in first-order logic. In Machine Intelligence 5, Meltzer and Michie, Eds., Edinburgh U. Press, Edinburgh, 1970, pp. 79-98.
- Floyd, R. W. Assigning meaning to programs. In Proc. Symposia in Applied Mathematics, Vol. 19, American Mathematical Society, 1967, pp. 19-32.
- ----, and McCarthy, J. Properties of programs and partial function logic. In Machine Intelligence 5, Meltzer and Michie, Eds., Edinburgh U. Press, Edinburgh, 1970, pp. 79-98.
- Park, D. Fixpoint induction and proofs of program properties. In Machine Intelligence 5. Meltzer and Michie, Eds., Edinburgh U. Press, Edinburgh, pp. 59-78.
Cited by
Sorted by citations
STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving
Fikes, R. E., & Nilsson, N. J. (1971) · Artificial Intelligence · doi:10.1016/0004-3702(71)90010-5 · Cited by 4,882 · see citing works
Evaluating Large Language Models Trained on Code
Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. D. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al. (2021) · arXiv · doi:10.48550/arxiv.2107.03374 · Cited by 1,436 · see citing works
“More recently, language models have also fueled progress towards the longstanding challenge of program synthesis (Simon, 1963; Manna & Waldinger, 1971), spurred by the presence of code in large datasets (Husain et al., 2019; Gao et al., 2020) and the resulting programming capabilities of language…”
BackgroundCompetition-level code generation with AlphaCode
Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Dal Lago, A., et al. (2022) · Science · doi:10.1126/science.abq1158 · Cited by 1,043 · see citing works
Structured Programming with go to Statements
Knuth, D. E. (1974) · ACM Computing Surveys · doi:10.1145/356635.356640 · Cited by 678 · see citing works
Combinatorial sketching for finite programs
Solar-Lezama, A., Tancau, L., Bodík, R., Seshia, S., & Saraswat, V. (2006) · ASPLOS XII · doi:10.1145/1168857.1168907 · Cited by 922 · see citing works
Large language models for software engineering: survey and open problems
Fan, A., Gokkaya, B., Harman, M., Lyubarskiy, M., Sengupta, S., Yoo, S., & Zhang, J. M. (2023) · 2023 IEEE/ACM International Conference on Software Engineering: Future of Software Engineering (ICSE-FoSE) · doi:10.1109/icse-fose59343.2023.00008 · Cited by 650 · see citing works
The Robots Are Coming: Exploring the Implications of OpenAI Codex on Introductory Programming
Finnie-Ansley, J., Denny, P., Becker, B. A., Luxton-Reilly, A., & Prather, J. (2022) · Proceedings of the 24th Australasian Computing Education Conference · doi:10.1145/3511861.3511863 · Cited by 463 · see citing works
Automated Program Repair in the Era of Large Pre-trained Language Models
Xia, C. S., Wei, Y., & Zhang, L. (2023) · 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE) · doi:10.1109/icse48619.2023.00129 · Cited by 433 · see citing works
Synthetic Data for Deep Learning
Nikolenko, S. (2021) · Springer optimization and its applications · doi:10.1007/978-3-030-75178-4 · Cited by 434 · see citing works
Putting theories together to make specifications
Burstall, R. M., & Goguen, J. A. (1977) · International Joint Conference on Artificial Intelligence · Cited by 420 · see citing works
Program Synthesis with Large Language Models
Austin, J., Odena, A., Nye, M., Bosma, M., Michalewski, H., Dohan, D., Jiang, E., Cai, C., Terry, M., Le, Q., et al. (2021) · arXiv · doi:10.48550/arxiv.2108.07732 · Cited by 388 · see citing works
“Program synthesis is a longstanding goal of artificial intelligence research [Manna and Waldinger, 1971, Waldinger et al., 1969, Summers, 1977, Shaw et al., 1975, Pnueli and Rosner, 1989, Manna and Waldinger, 1975], dating as far back as the 1940s and 50s [Copeland, 2012, Backus et al., 1957].”
BackgroundLarge language models (LLMs): survey, technical frameworks, and future challenges
Kumar, P. (2024) · Artificial Intelligence Review · doi:10.1007/s10462-024-10888-y · Cited by 395 · see citing works
Gulwani, S., Polozov, O., & Singh, R. (2017) · Foundations and Trends® in Programming Languages · doi:10.1561/2500000010 · Cited by 357 · see citing works
Wegbreit, B. (1975) · Communications of the ACM · doi:10.1145/361002.361016 · Cited by 293 · see citing works
From program verification to program synthesis
Srivastava, S., Gulwani, S., & Foster, J. S. (2010) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/1706299.1706337 · Cited by 274 · see citing works
Degano, P. (1983) · Springer eBooks · doi:10.1007/978-3-642-82017-5_12 · Cited by 265 · see citing works
An Empirical Study of the Non-Determinism of ChatGPT in Code Generation
Ouyang, S., Zhang, J. M., Harman, M., & Wang, M. (2025) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3697010 · Cited by 258 · see citing works
“Relatively early work includes deductive synthesis approaches [19, 45] and inductive synthesis approaches [8, 56–58].”
MethodGenetic Improvement of Software: A Comprehensive Survey
Petke, J., Haraldsson, S. O., Harman, M., Langdon, W. B., White, D. R., & Woodward, J. R. (2017) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2017.2693219 · Cited by 230 · see citing works
Constructing Programs from Example Computations
Biermann, A. W., & Krishnaswamy, R. (1976) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1976.233812 · Cited by 158 · see citing works
Manna, Z., & Waldinger, R. J. (1979) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1979.234198 · Cited by 155 · see citing works
Self-citationCost analysis of logic programs
Debray, S., & Lin, N.-W. (1993) · ACM Transactions on Programming Languages and Systems · doi:10.1145/161468.161472 · Cited by 152 · see citing works
Kunčak, V., Mayer, M., Piskač, R., & Suter, P. (2010) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/1806596.1806632 · Cited by 145 · see citing works
Automated software transplantation
Barr, E. T., Harman, M., Jia, Y., Marginean, A., & Petke, J. (2015) · International Symposium on Software Testing and Analysis · doi:10.1145/2771783.2771796 · Cited by 134 · see citing works
Natural Language Generation and Understanding of Big Code for AI-Assisted Programming: A Review
Wong, M.-F., Guo, S., Hang, C. N., Ho, S., & Tan, C. W. (2023) · Entropy · doi:10.3390/e25060888 · Cited by 137 · see citing works
Search based software engineering for software product line engineering
Harman, M., Jia, Y., Krinke, J., Langdon, W. B., Petke, J., & Zhang, Y. (2014) · International Software Product Line Conference (SPLC) · doi:10.1145/2648511.2648513 · Cited by 128 · see citing works
An Assessment of Techniques for Proving Program Correctness
Elspas, B., Levitt, K., Waldinger, R. J., & Waksman, A. (1972) · ACM Computing Surveys · doi:10.1145/356599.356602 · Cited by 121 · see citing works
Self-citationFreeman, P. (1974) · Computer · doi:10.1109/mc.1974.6323495 · Cited by 118 · see citing works
A new deductive approach to planning
Hölldobler, S., & Schneeberger, J. (1990) · New Generation Computing · doi:10.1007/bf03037518 · Cited by 114 · see citing works
Synthesis modulo recursive functions
Kneuss, E., Kuraj, I., Kunčak, V., & Suter, P. (2013) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2509136.2509555 · Cited by 109 · see citing works
Knowledge and reasoning in program synthesis
Manna, Z., & Waldinger, R. J. (1975) · Artificial Intelligence · doi:10.1016/0004-3702(75)90008-9 · Cited by 105 · see citing works
Self-citationA Deductive Solution for Plan Generation
Bibel, W. (1986) · Topics in information systems · doi:10.1007/978-3-642-83397-7_21 · Cited by 103 · see citing works
Ouh, E. L., Gan, B. K. S., Shim, K. J., & Wlodkowski, S. (2023) · ACM Conference on Innovation and Technology in Computer Science Education (ITiCSE) · doi:10.1145/3587102.3588794 · Cited by 101 · see citing works
Programming with a Differentiable Forth InterpreterPreprint
Bošnjak, M., Rocktäschel, T., Naradowsky, J., & Riedel, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.06640 · Cited by 93 · see citing works
Template-based program verification and program synthesis
Srivastava, S., Gulwani, S., & Foster, J. S. (2012) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-012-0223-4 · Cited by 89 · see citing works
On the inference of Turing machines from sample computations
Biermann, A. W. (1972) · Artificial Intelligence · doi:10.1016/0004-3702(72)90048-3 · Cited by 85 · see citing works
Combinatorial sketching for finite programs
Solar-Lezama, A., Tancau, L., Bodík, R., Seshia, S. A., & Saraswat, V. (2006) · ACM SIGOPS Operating Systems Review · doi:10.1145/1168917.1168907 · Cited by 83 · see citing works
Combinatorial sketching for finite programs
Solar-Lezama, A., Tancau, L., Bodík, R., Seshia, S. A., & Saraswat, V. (2006) · ACM SIGPLAN Notices · doi:10.1145/1168918.1168907 · Cited by 78 · see citing works
Neural-Guided Deductive Search for Real-Time Program Synthesis from ExamplesPreprint
Kalyan, A., Mohta, A., Polozov, O., Batra, D., Jain, P., & Gulwani, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1804.01186 · Cited by 74 · see citing works
Sørensen, M. H., & Urzyczyin, P. (2006) · Studies in logic and the foundations of mathematics · doi:10.1016/s0049-237x(06)80005-4 · Cited by 73 · see citing works
An Empirical Study of Code Smells in Transformer-based Code Generation Techniques
Siddiq, M. L., Majumder, S. H., Mim, M. R., Jajodia, S., & Santos, J. C. S. (2022) · 2022 IEEE 22nd International Working Conference on Source Code Analysis and Manipulation (SCAM) · doi:10.1109/scam55253.2022.00014 · Cited by 70 · see citing works
Piccolo, S., Denny, P. C., Luxton-Reilly, A., Payne, S., & Ridge, P. G. (2023) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1011511 · Cited by 81 · see citing works
From program verification to program synthesis
Srivastava, S., Gulwani, S., & Foster, J. S. (2010) · ACM SIGPLAN Notices · doi:10.1145/1707801.1706337 · Cited by 66 · see citing works
Interactive Program Synthesis by Augmented Examples
Zhang, T., Lowmanstone, L., Wang, X., & Glassman, E. L. (2020) · ACM Symposium on User Interface Software and Technology (UIST) · doi:10.1145/3379337.3415900 · Cited by 57 · see citing works
Chaudhuri, S., Ellis, K., Polozov, O., Singh, R., Solar-Lezama, A., & Yue, Y. (2021) · Foundations and Trends® in Programming Languages · doi:10.1561/2500000049 · Cited by 58 · see citing works
The verification and synthesis of data structures
Spitzen, J. M., & Wegbreit, B. (1975) · Acta Informatica · doi:10.1007/bf00288745 · Cited by 56 · see citing works
Approaches to Automatic Programming
Biermann, A. W. (1976) · Advances in computers · doi:10.1016/s0065-2458(08)60519-7 · Cited by 54 · see citing works
Path-based inductive synthesis for program inversion
Srivastava, S., Gulwani, S., Chaudhuri, S., & Foster, J. S. (2011) · ACM SIGPLAN Notices · doi:10.1145/1993316.1993557 · Cited by 51 · see citing works
Artificial intelligence and automatic programming in CAI
Koffman, E. B., & Blount, S. E. (1975) · Artificial Intelligence · doi:10.1016/0004-3702(75)90001-6 · Cited by 51 · see citing works
How Readable is Model-generated Code? Examining Readability and Visual Inspection of GitHub Copilot
Al Madi, N. (2022) · Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering · doi:10.1145/3551349.3560438 · Cited by 50 · see citing works
Design and Implementation of a Web-Service-Based Public-Oriented Personalized Health Care Platform
Wang, P., Ding, Z., Jiang, C., & Zhou, M. (2013) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmca.2012.2210412 · Cited by 48 · see citing works
Justification of the structural synthesis of programs
Mints, G. E., & Tyugu, E. (1982) · Science of Computer Programming · doi:10.1016/0167-6423(83)90016-3 · Cited by 48 · see citing works
An overview of nonprocedural languages
Leavenoworth, B. M., & Sammet, J. Ε. (1974) · doi:10.1145/800233.807040 · Cited by 46 · see citing works
Fully Autonomous Programming with Large Language Models
Liventsev, V., Grishina, A., Härmä, A., & Moonen, L. (2023) · Proceedings of the Genetic and Evolutionary Computation Conference · doi:10.1145/3583131.3590481 · Cited by 45 · see citing works
Speeding up the Synthesis of Programs from Traces
Biermann, A. W., Baum, R. I., & Petry, F. E. (1975) · IEEE Transactions on Computers · doi:10.1109/t-c.1975.224180 · Cited by 45 · see citing works
Bauer, M. (1979) · Artificial Intelligence · doi:10.1016/0004-3702(79)90002-x · Cited by 44 · see citing works
Clover: Closed-Loop Verifiable Code Generation
Sun, C., Sheng, Y., Padon, O., & Barrett, C. (2024) · Lecture Notes in Computer Science · doi:10.1007/978-3-031-65112-0_7 · Cited by 43 · see citing works
A Symbolic Approach to Safety ltl Synthesis
Zhu, S., Tabajara, L. M., Li, J., Pu, G., & Vardi, M. Y. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70389-3_10 · Cited by 43 · see citing works
Path-based inductive synthesis for program inversion
Srivastava, S., Gulwani, S., Chaudhuri, S., & Foster, J. S. (2011) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/1993498.1993557 · Cited by 41 · see citing works
Structured programming with go to statements
Knuth, D. E. (1979) · Cited by 40 · see citing works
Kunčak, V., Mayer, M., Piskač, R., & Suter, P. (2012) · Communications of the ACM · doi:10.1145/2076450.2076472 · Cited by 39 · see citing works
A General Large Neighborhood Search Framework for Solving Integer Linear ProgramsPreprint
Song, J., Lanka, R., Yue, Y., & Dilkina, B. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.00422 · Cited by 39 · see citing works
A situated-automata approach to the design of embedded agents
Kaelbling, L. P. (1991) · ACM SIGART Bulletin · doi:10.1145/122344.122361 · Cited by 38 · see citing works
Combinatorial sketching for finite programs
Solar-Lezama, A., Tancau, L., Bodík, R., Seshia, S. A., & Saraswat, V. (2006) · ACM SIGARCH Computer Architecture News · doi:10.1145/1168919.1168907 · Cited by 37 · see citing works
The Inevitable Pain of Software Development: Why There Is No Silver Bullet
Berry, D. M. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24626-8_4 · Cited by 36 · see citing works
Improving and refining programs by program manipulation
Standish, T. A., Kibler, D. F., & Neighbors, J. M. (1976) · ACM Annual Conference · doi:10.1145/800191.805652 · Cited by 36 · see citing works
Program synthesis: challenges and opportunities
David, C., & Kroening, D. (2017) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2015.0403 · Cited by 33 · see citing works
An improved program-synthesizing algorithm and its correctness
Lee, R. C. T., Waldinger, R. J., & Chang, C. L. (1974) · Communications of the ACM · doi:10.1145/360924.360967 · Cited by 33 · see citing works
Self-citationSALLM: Security Assessment of Generated Code
Siddiq, M. L., Santos, J. C. S., Devareddy, S., & Muller, A. (2024) · IEEE/ACM International Conference on Automated Software Engineering Workshops (ASEW) · doi:10.1145/3691621.3694934 · Cited by 49 · see citing works
Sequential Synthesis Using S1S
Aziz, A., Balarin, F., Brayton, R. K., & Sangiovanni-Vincentelli, A. L. (1995) · Cited by 32 · see citing works
Academic Legitimacy of the Software Engineering Discipline
Berry, D. M. (1992) · doi:10.21236/ada260241 · Cited by 30 · see citing works
Learning a Meta-Solver for Syntax-Guided Program Synthesis
Si, X., Yang, Y., Dai, H., Naik, M., & Song, L. (2018) · International Conference on Learning Representations · Cited by 28 · see citing works
Reliability and integrity of large computer programs
Ramamoorthy, C. V., Cheung, R. C. C., & Kim, K. H. (1974) · Lecture notes in computer science · doi:10.1007/3-540-06786-8_260 · Cited by 26 · see citing works
Interpretable Program Synthesis
Zhang, T., Chen, Z., Zhu, Y., Vaithilingam, P., Wang, X., & Glassman, E. L. (2021) · CHI Conference on Human Factors in Computing Systems · doi:10.1145/3411764.3445646 · Cited by 26 · see citing works
Program extrapolation with jennisys
Leino, K. R. M., & Milicevic, A. (2012) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2384616.2384646 · Cited by 25 · see citing works
Kunčak, V., Mayer, M., Piskač, R., & Suter, P. (2010) · ACM SIGPLAN Notices · doi:10.1145/1809028.1806632 · Cited by 25 · see citing works
Will Code Remain a Relevant User Interface for End-User Programming with Generative AI Models?
Sarkar, A. (2023) · ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!) · doi:10.1145/3622758.3622882 · Cited by 25 · see citing works
Functional synthesis for linear arithmetic and sets
Kunčak, V., Mayer, M., Piskač, R., & Suter, P. (2011) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-011-0217-7 · Cited by 23 · see citing works
Transformation Rules for Synthesis of UML Activity Diagram from Scenario-Based Specification
Kang, S., Kim, H., Baik, J., Choi, H.-J., & Keum, C. (2010) · IEEE Annual International Computer Software and Applications Conference (COMPSAC) · doi:10.1109/compsac.2010.51 · Cited by 23 · see citing works
Gascón, A., Tiwari, A., Carmer, B., & Mathur, U. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-63390-9 · Cited by 24 · see citing works
Program synthesis from natural deduction proofs
Goto, S. (1979) · International Joint Conference on Artificial Intelligence · Cited by 22 · see citing works
Synthesis modulo recursive functions
Kneuss, E., Kuraj, I., Kunčak, V., & Suter, P. (2013) · ACM SIGPLAN Notices · doi:10.1145/2544173.2509555 · Cited by 21 · see citing works
Automatic program synthesis from example problems
Siklóssy, L., & Sykes, D. A. (1975) · International Joint Conference on Artificial Intelligence · Cited by 21 · see citing works
UML diagram synthesis techniques
Torre, D., Labiche, Y., Genero, M., Baldassarre, M. T., & Elaasar, M. (2018) · doi:10.1145/3193954.3193957 · Cited by 19 · see citing works
Bugs, Moles and Skeletons: Symbolic Reasoning for Software Development
de Moura, L., & Bjørner, N. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14203-1_34 · Cited by 18 · see citing works
Teaching GP to program like a human software developer
Sobania, D., & Rothlauf, F. (2019) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/3321707.3321738 · Cited by 18 · see citing works
A fold/unfold transformation framework for rewrite theories extended to CCT
Alpuente, M., Ballis, D., Baggi, M., & Falaschi, M. (2010) · ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM) · doi:10.1145/1706356.1706367 · Cited by 18 · see citing works
Sequential synthesis using S1S
Aziz, A., Balarin, F., Brayton, R. K., & Sangiovanni-Vincentelli, A. L. (2000) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.875301 · Cited by 18 · see citing works
Algorithms and Architectures of Artificial Intelligence
Tyugu, E. (2007) · Cited by 18 · see citing works
Helmuth, T. (2021) · Scholarworks (University of Massachusetts Amherst) · doi:10.7275/7408407.0 · Cited by 18 · see citing works
Elspas, B., Green, M. W., & Levitt, K. (1971) · Computer · doi:10.1109/c-m.1971.216741 · Cited by 18 · see citing works
Learning to Represent Programs with Property SignaturesPreprint
Odena, A., & Sutton, C. A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.09030 · Cited by 18 · see citing works
Reductions for Synthesis Procedures
Jacobs, S., Kunčak, V., & Suter, P. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-35873-9_8 · Cited by 17 · see citing works
Enhancing Large Language Models-Based Code Generation by Leveraging Genetic Improvement
Pinna, G., Ravalico, D., Rovito, L., Manzoni, L., & Lorenzo, A. D. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-56957-9_7 · Cited by 18 · see citing works
Orvalho, P., Terra-Neves, M., Ventura, M., Martins, R., & Manquinho, V. M. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3415478.3415492 · Cited by 16 · see citing works
Neuro-Symbolic Program Search for Autonomous Driving Decision Module Design.
Sun, J., Sun, H., Han, T., & Zhou, B. (2020) · Conference on Robot Learning · Cited by 16 · see citing works
Knowledge and reasoning in program synthesis
Manna, Z., & Waldinger, R. J. (1975) · Lecture notes in computer science · doi:10.1007/3-540-07131-8_29 · Cited by 16 · see citing works
Self-citationA Production Rule Mechanism for Generating LISP Code
Biermann, A. W., & Smith, D. R. (1979) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1979.4310195 · Cited by 16 · see citing works
Automatic Program Repair Using Genetic Programming
Goues, C. L. (2013) · doi:10.18130/v3kz3c · Cited by 16 · see citing works
An overview of nonprocedural languages
Leavenoworth, B. M., & Sammet, J. Ε. (1974) · ACM SIGPLAN Notices · doi:10.1145/942572.807040 · Cited by 16 · see citing works
LLM4TDD: Best Practices for Test Driven Development Using Large Language Models
Piya, S., & Sullivan, A. (2024) · International Workshop on Large Language Models for Code (LLM4Code) · doi:10.1145/3643795.3648382 · Cited by 15 · see citing works
- Authors
- Manna, Z., & Waldinger, R. J.
- Affiliations
- Stanford University (US)
- SRI International (US)
- Venue
- Communications of the ACM
- Published
- 1971-03
- Volume
- 14
- Issue
- 3
- Pages
- 151-165
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W2037237472
- Cited by
- 285
- References
- 24
- Citations by year
- 2026: 7 · 2025: 17 · 2024: 10 · 2023: 12 · 2022: 5 · 2021: 12 · 2020: 14 · 2019: 8 · 2018: 9 · 2017: 11 · 2016: 5 · 2015: 6 · 2014: 9 · 2013: 12 · 2012: 7
- FWCI
- 21.08
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Communications of the ACM (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Keywords
- program synthesis, theorem proving, mathematical induction, recursive programs, iterative programs, program transformation, specification-based synthesis, lists, trees, natural numbers
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
