A theory of formal synthesis via inductive learning
Open accessThe DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Abstract
Formal synthesis is the process of generating a program satisfying a high-level formal specification. In recent times, effective formal synthesis methods have been proposed based on the use of inductive learning. We refer to this class of methods that learn programs from examples as formal inductive synthesis. In this paper, we present a theoretical framework for formal inductive synthesis. We discuss how formal inductive synthesis differs from traditional machine learning. We then describe oracle-guided inductive synthesis (OGIS), a framework that captures a family of synthesizers that operate by iteratively querying an oracle. An instance of OGIS that has had much practical impact is counterexample-guided inductive synthesis (CEGIS). We present a theoretical characterization of CEGIS for learning any program that computes a recursive language. In particular, we analyze the relative power of CEGIS variants where the types of counterexamples generated by the oracle varies. We also consider the impact of bounded versus unbounded memory available to the learning algorithm. In the special case where the universe of candidate programs is finite, we relate the speed of convergence to the notion of teaching dimension studied in machine learning theory. Altogether, the results of the paper take a first step towards a theoretical foundation for the emerging field of formal inductive synthesis.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Language identification in the limit
Gold, E. M. (1967) · Information and Control · doi:10.1016/s0019-9958(67)91165-5 · Cited by 3,572
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279 · cited 2×
“Blumer et al. [12] have shown that the VC dimension of a concept class characterizes the number of examples required for learning any concept in the class under the distribution-free or probably approximately correct (PAC) model of Valiant [59].”
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (1971) · Theory of Probability & Its Applications · doi:10.1137/1116025 · Cited by 2,448
Alur, R., Bodik, R., Juniwal, G., Martin, M. M. K., Raghothaman, M., Seshia, S. A., Singh, R., Solar-Lezama, A., Torlak, E., & Udupa, A. (2013) · 2013 Formal Methods in Computer-Aided Design · doi:10.1109/fmcad.2013.6679385 · Cited by 656
Self-citationProgramming by sketching for bit-streaming programs
Solar-Lezama, A., Rabbah, R., Bodík, R., & Ebcioğlu, K. (2005) · Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation · doi:10.1145/1065010.1065045 · Cited by 195
Combining Induction, Deduction, and Structure for Verification and Synthesis
Seshia, S. A. (2015) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2471838 · Cited by 38 · cited 1×
“Many current approaches to synthesis blend induction and deduction in the sense that even as they generalize from examples, deductive procedures are used in the process of generalization (see [36,55,56] for a detailed exposition).”
MethodSelf-citation
Cited by
Artificial intelligence in Internet of things
Ghosh, A., Chakraborty, D., & Law, A. (2018) · CAAI Transactions on Intelligence Technology · doi:10.1049/trit.2018.1008 · Cited by 368
Artificial Intelligence-based Internet of Things for Industry 5.0
Chander, B., Pal, S., De, D., & Buyya, R. (2022) · Internet of Things · doi:10.1007/978-3-030-87059-1_1 · Cited by 160
Towards Verified Artificial Intelligence
Seshia, S. A., Sadigh, D., & Sastry, S. S. (2016) · arXiv · doi:10.48550/arxiv.1606.08514 · Cited by 142
Self-citationLLM-Based Test-Driven Interactive Code Generation: User Study and Empirical Evaluation
Fakhoury, S., Naik, A., Sakkas, G., Chakraborty, S., & Lahiri, S. K. (2024) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2024.3428972 · Cited by 120
“…user feedback using the code reference implementation as an idealized proxy, similar to prior works in oracle-guided inductive synthesis [15], [28] and interactive program synthesis [29], [30] where an an oracle (reference implementation or users) is queried to identify the output for a given…”
MethodA Review on Human–Machine Trust Evaluation: Human-Centric and Machine-Centric Perspectives
Gebru, B., Zeleke, L., Blankson, D., Nabil, M., Nateghi, S., Homaifar, A., & Tunstel, E. (2022) · IEEE Transactions on Human-Machine Systems · doi:10.1109/thms.2022.3144956 · Cited by 101
“Finally, the theory of formal inductive synthesis [98] is an emerging solution used to address the challenge of synthesizing “correct-by-construction” design of models for a learning system.”
Method
Metadata
- Authors
- Jha, S., & Seshia, S. A.
- Venue
- Acta Informatica
- Published
- 2017-02-15
- Volume
- 54
- Issue
- 7
- Pages
- 693-726
- ISSN
- 0001-5903 (ISSN-L)
- 1432-0525
- OpenAlex
- W258469679
- Cited by
- 99
- References
- 6
- FWCI
- 6.23
- Type
- journal article
- Language
- en
- Open access
- green
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: A theory of formal synthesis via inductive learning. https://app.cochat.ai/papers/10.1007/s00236-017-0294-5
- The paper
- Jha, S., & Seshia, S. A. (2017). A theory of formal synthesis via inductive learning. Acta Informatica. https://doi.org/10.1007/s00236-017-0294-5
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.