一句话：提出在函数式合成与自动机合成间迭代的算法，从观测数据中合成因果反应式程序。
本文研究如何从观测数据中合成反应式程序，尤其针对观测不完整、需要推断潜在状态的因果动态。其核心方法是在两个步骤间迭代：函数式合成尝试在已观测状态上生成转移函数；自动机合成则补充任何必需的额外潜在状态，以完全解释观测数据。为支撑这一方法，作者设计了名为 Autumn 的函数式反应式 DSL，能够表达 Atari 风格网格世界中丰富的时变因果动态，并从数据中合成 Autumn 程序。评估在 30 个 Autumn 程序基准和第三方网格世界风格视频游戏语料上进行，分别成功合成了 27/30 和 21/27 个程序，其中包含若干描述复杂潜在状态变换的程序，且输入轨迹包含数百条观测。作者期望该方法能为在其他归纳领域整合函数式合成与自动机合成提供模板。
We present a new algorithm that synthesizes functional reactive programs from observation data. The key novelty is to iterate between a functional synthesis step, which attempts to generate a transition function over observed states, and an automata synthesis step, which adds any additional latent state necessary to fully account for the observations. We develop a functional reactive DSL called Autumn that can express a rich variety of causal dynamics in time-varying, Atari-style grid worlds, and apply our method to synthesize Autumn programs from data. We evaluate our algorithm on a benchmark suite of 30 Autumn programs as well as a third-party corpus of grid-world-style video games. We find that our algorithm synthesizes 27 out of 30 programs in our benchmark suite and 21 out of 27 programs from the third-party corpus, including several programs describing complex latent state transformations, and from input traces containing hundreds of observations. We expect that our approach will provide a template for how to integrate functional and automata synthesis in other induction domains.
@article{paperbot2063,
title = {Combining Functional and Automata Synthesis to Discover Causal Reactive Programs},
author = {Ria Das and Joshua B. Tenenbaum and Armando Solar-Lezama and Zenna Tavares},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {POPL},
year = {2023},
doi = {10.1145/3571249}
}