Synteza sterowana gramatyką i solwerami (SyGuS)

Syntax-guided and solver-based synthesis (SyGuS) · id sygus · aliases: syntax-guided synthesis, SyGuS, synteza sterowana składnią

Synteza funkcji spełniającej formułę w teorii tła (SMT) i jednocześnie wyrażalnej gramatyką; standaryzowana formatem SyGuS-IF i konkursem SyGuS-Comp.

Synthesising a function satisfying a formula in a background theory (SMT) while expressible in a grammar; standardised by the SyGuS-IF format and SyGuS-Comp.

In one sentence

Szukanie programu, który spełnia ściśle zapisany warunek logiczny i zbudowany jest tylko z dozwolonych klocków.

Searching for a program that meets a precisely written logical condition and uses only permitted building blocks.

Problem it solves

W kodzie krytycznym nie wystarczy, że program działa na kilku przykładach; musi działać dla każdego możliwego wejścia.

In critical code it is not enough for a program to work on a few examples; it must work for every possible input.

What it does

Łączy zgadywanie z kontrolą: jeden mechanizm proponuje program, drugi szuka wejścia, na którym zawodzi, i tak aż do skutku.

Combines guessing with checking: one part proposes a program, another hunts for an input where it fails, until none remains.

Everyday example

Narzędzie dla programistów samo wylicza warunek, który musi być prawdziwy w każdym obrocie pętli, żeby udowodnić jej poprawność.

A developer tool works out by itself a condition that must hold on every loop iteration, to prove the loop correct.

This concerns you if you…

Sources