Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Synthesis Through Unification
verfasst von : Rajeev Alur, Pavol Černý, Arjun Radhakrishna
Erschienen in: Computer Aided Verification
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Given a specification and a set of candidate programs (program space), the program synthesis problem is to find a candidate program that satisfies the specification. We present the synthesis through unification (STUN) approach, which is an extension of the counter-example guided inductive synthesis (CEGIS) approach. In CEGIS, the synthesizer maintains a subset S of inputs and a candidate program \(\mathtt {Prog}\) that is correct for S. The synthesizer repeatedly checks if there exists a counterexample input c such that the execution of \(\mathtt {Prog}\) is incorrect on c. If so, the synthesizer enlarges S to include c, and picks a program from the program space that is correct for the new set S.
The STUN approach extends CEGIS with the idea that given a program \(\mathtt {Prog}\) that is correct for a subset of inputs, the synthesizer can try to find a program \(\mathtt {Prog}'\) that is correct for the rest of the inputs. If \(\mathtt {Prog}\) and \(\mathtt {Prog}'\) can be unified into a program in the program space, then a solution has been found. We present a generic synthesis procedure based on the STUN approach and specialize it for three different domains by providing the appropriate unification operators. We implemented these specializations in prototype tools, and we show that our tools often performs significantly better on standard benchmarks than a tool based on a pure CEGIS approach.