# Inductive Program Synthesis Over Noisy Data

arXiv: https://arxiv.org/abs/2009.10272 · HTML: https://mlsanity.com/paper/2009.10272/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2020.

## Built on by (most cited first, 7 of 7)

- [Program Synthesis Guided Reinforcement Learning for Partially Observed Environments](https://mlsanity.com/paper/2102.11137/) (2021)
- [FormaT5: Abstention and Examples for Conditional Table Formatting with Natural Language](https://mlsanity.com/paper/2310.17306/) (2023)
- [Efficient Bottom-Up Synthesis for Programs with Local Variables](https://mlsanity.com/paper/2311.03705/) (2023)
- [Inductive Program Synthesis over Noisy Datasets using Abstraction Refinement Based Optimization](https://mlsanity.com/paper/2104.13315/) (2021)
- [Program Synthesis Over Noisy Data with Guarantees](https://mlsanity.com/paper/2103.05030/) (2021)
- [An Empirical Comparison of Cost Functions in Inductive Logic Programming](https://mlsanity.com/paper/2503.07554/) (2025)
- [Fixed-Set Robustness in Programming by Example: Example Corruption and Semantic Partition Recovery](https://mlsanity.com/paper/2607.01280/) (2026)

## Abstract (arXiv)

We present a new framework and associated synthesis algorithms for program synthesis over noisy data, i.e., data that may contain incorrect/corrupted input-output examples. This framework is based on an extension of finite tree automata called em weighted finite tree automata. We show how to apply this framework to formulate and solve a variety of program synthesis problems over noisy data. Results from our implemented system running on problems from the SyGuS 2018 benchmark suite highlight its ability to successfully synthesize programs in the face of noisy data sets, including the ability to synthesize a correct program even when every input-output example in the data set is corrupted.