Abstrakt. Syntetiseringsproblemet kräver att man konstruerar ett reaktivt finit-state-system från en standardspecifikation. De ursprungliga specifikationerna är ofta ogenomförbara, vilket innebär att det inte finns något system som implementerar specifikationen. Ett vanligt skäl till ogenomförbarhet är att antaganden om miljön i systemet är ofullständiga. Vi studerar problemet med att korrigera en ogenomförbar specifikation genom att beräkna ett miljöantagande  på ett sådant sätt att den nya specifikationen är realizable. Vårt mål är att konstruera ett antagande som begränsar bara miljön och är så svag som möjligt. Vi presenterar en tvåstegsalgoritm för beräkningsantaganden. Algoritmen fungerar på spelet grafen som används för att besvara frågan realizability. Först beräknar vi en säkerhetsförutsättning som tar bort en minimal uppsättning miljökanter från grafen. För det andra beräknar vi ett levande antagande som sätter rättvisa villkor på några av de återstående miljökanterna. Vi visar att problemet med att hitta en minimal uppsättning av rättvisa kanter är beräknings svårt, och vi använder probabilistiska spel för att beräkna en lokalt minimal rättvisa antagande.
Den metod som föreslås i REF använder spelgrafen som används för att besvara frågan om realizability för att konstruera en Büchi automaton som representerar ett minimalt antagande som gör specifikationen realizable.
Environment Assumptions for Synthesis
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}