Synthesizing Reactive Programs
Synthesizing Reactive Programs
复制标题
综合反应式程序
DOI：
10.4230/lipics.csl.2011.428
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
P. Madhusudan
中科院分区：
文献类型：
--
作者：
P. Madhusudan
目前的理论解决方案，古典教会的综合问题的重点是综合过渡系统，而不是程序。程序是紧凑的，往往是真正的目标，在许多综合问题，而相应的过渡系统，他们往往是大的，并不是很有用的合成文物。因此，目前的实际技术首先合成一个过渡系统，然后提取一个更紧凑的表示从it.We重新反应系统的合成直接在程序合成方面，并发展一个理论，以表明在一个简单的命令式编程语言的一组固定的布尔变量的程序合成的问题是可判定的定期欧米茄规格。我们还提出了结果与递归对两个经常规范，以及合理的下推语言规范的合成程序。最后，我们展示了程序修复的应用程序，并得出结论，在合成分布式程序的开放问题。
Current theoretical solutions to the classical Church's synthesis problem are focused on synthesizing transition systems and not programs. Programs are compact and often the true aim in many synthesis problems, while the transition systems that correspond to them are often large and not very useful as synthesized artefacts. Consequently, current practical techniques first synthesize a transition system, and then extract a more compact representation from it. We reformulate the synthesis of reactive systems directly in terms of program synthesis, and develop a theory to show that the problem of synthesizing programs over a fixed set of Boolean variables in a simple imperative programming language is decidable for regular omega-specifications. We also present results for synthesizing programs with recursion against both regular specifications as well as visibly-pushdown language specifications. Finally, we show applications to program repair, and conclude with open problems in synthesizing distributed programs.