Abstrakt. Explicit state-metoder har visat sig användbara för att verifiera säkerhetskritiska system som innehåller samtidiga processer som kör asynkront och kommunicerar. Sådana metoder består i att inspektera stater och övergångar av en graf representation av systemet. Deras huvudsakliga begränsning är tillståndsexplosion, vilket händer när grafen är för stor för att lagras i det tillgängliga datorminnet. Flera tekniker kan användas för att palliera tillståndsexplosion, såsom on-the-fly-verifiering, kompositionsverifiering och partiella orderminskningar. I detta dokument föreslår vi en ny teknik för partiella orderminskningar baserade på detektion av kompositionskonfluens (Ccd), som kan kombineras med de tekniker som nämns ovan. Ccd bygger på en generalisering av begreppet konfluens som definieras av Milner och utnyttjar det faktum att synkronisering av övergångar som är sammanflätade i de enskilda processerna ger en sammanflätad övergång i systemgrafen. Den består således av att analysera övergångarna av de enskilda processgraferna och synkroniseringsstrukturen för att identifiera sådana sammanfallande övergångar kompositionellt. Under vissa ytterligare omständigheter kan de sammanfallande övergångarna prioriteras framför de andra övergångarna, vilket gör det möjligt att minska graferna. Vi föreslår två sådana ytterligare villkor: ett som säkerställer att den genererade grafen är likvärdig med den ursprungliga systemgrafen Modulo grenning bisimulation, och ett som säkerställer att den genererade grafen innehåller samma dödläge som den ursprungliga systemgrafen. Vi beskriver också hur Ccd-baserade minskningar genomfördes i verktygslådan Cadp, och presenterar exempel och en fallstudie där tillägg av Ccd förbättrar minskningar med avseende på kompositionskontroll och andra partiella orderminskningar.
Lang m.fl. REF, föreslog en variant av POR med hjälp av kompositionskonfluens detektion.
Partial Order Reductions using Compositional Confluence Detection
{'venue': "16TH INTERNATIONAL SYMPOSIUM ON FORMAL METHODS FM'2009", 'journal': None, 'mag_field_of_study': ['Computer Science']}