Abstrakt. Problemet med tillståndsrymdexplosion är centralt för automatiska verifieringsalgoritmer. En av de framgångsrika metoderna för att lindra detta problem kallas "partial order reduction". Det är baserat på observationen att i många fall specifikationen av samtidiga program inte beror på den ordning i vilken samtidigt utförda händelser interleaved. I detta dokument presenterar vi en ny version av partiell orderminskning som gör det möjligt att fastställa alla minskningar vid tidpunkten för sammanställningen av systembeskrivningen. Normalt, partiell orderminskning kräver att utveckla specialiserade verifieringsalgoritmer, som under loppet av en tillståndsrymd sökning, välja en delmängd av de möjliga övergångar från varje nått globala tillstånd. I vår strategi, den uppsättning atomära övergångar som erhålls från systembeskrivningen efter vår speciella sammanställning, genererar redan ett mindre antal val från varje stat. I stället för att genomföra en modifierad sökning av det tillståndsutrymme som genereras av den ursprungliga statsövergångsförhållandet innebär vårt tillvägagångssätt således en vanlig sökning av det nåbara tillståndsutrymme som genereras av ett modifierat tillståndsövergångsförhållande. Bland fördelarna med denna teknik jämfört med andra versioner av minskningen är att den kan genomföras direkt med hjälp av befintliga verifieringsverktyg, eftersom den inte kräver någon ändring av verifieringsmotorn: hela reduktionsmekanismen inrättas vid kompileringstidpunkten. En viktig tillämpning är användningen av denna reduktionsteknik tillsammans med symbolisk modellkontroll och lokalisering minskning, erhålla en kombinerad minskning. Vi diskuterar en implementering och experimentella resultat för SDL-program översatt till COSPAN notation genom att tillämpa våra reduktionstekniker. Detta är en del av ett projekt för co-verifiering av hårdvaruprogramvara.
I REF föreslås en ny teknik som syftar till att inrätta hela minskningsmekanismen vid sammanställningstidpunkten.
H.: Static partial order reduction
{'venue': 'In: TACAS ’98: Proceedings of the 4th International Conference on Tools and Algorithms for Construction and Analysis of Systems', 'journal': None, 'mag_field_of_study': ['Computer Science']}