Scenariobaserade specifikationer såsom textsekvensdiagram (MSC) erbjuder ett intuitivt och visuellt sätt att beskriva designkrav. MSC-grafer möjliggör bekvämt uttryck av flera scenarier, och kan ses som en tidig modell av systemet som kan utsättas för en mängd olika analyser. Problem som LTL modellkontroll är obeslutbara för MSC-grafer i allmänhet, men är kända för att vara decidable för klassen av avgränsade MSC-grafer. Vår första uppsättning resultat handlar om att kontrollera realiserbarheten av avgränsade MSC-grafer. En MSC-graf är realizable om det finns en distribuerad implementation som genererar just beteendena i grafen. Det finns två begrepp om genomförbarhet, svag och säker, beroende på om vi kräver att genomförandet ska vara dödlägesfritt eller inte. Det är känt att för en ändlig uppsättning MSC, svag realizability är coNPfullständig medan säker realizability har en polynom-tid lösning. Vi fastslår att för avgränsade MSC-grafer, är svag realiserbarhet, överraskande, obeslutbar, medan säker realiserbarhet är i Expspace. Vår andra uppsättning resultat gäller verifiering av MSC-grafer. Vid kontroll av egenskaperna hos en graf G, förutom att kontrollera alla scenarier i uppsättningen L(G) av MSC som anges av G, är det önskvärt att kontrollera alla scenarier i uppsättningen L w (G) - stängningen av G, som innehåller de underförstådda scenarier som ett distribuerat genomförande av G måste innehålla. För att kontrollera om en given MSC M är ett möjligt beteende, att kontrollera M  och L (G) är NP-komplett, men att kontrollera M  för L w (G) har en kvadratisk lösning. För tidslogik specifikationer, med tanke på stängningen gör verifieringsproblemet svårare: medan kontrollera LTL egenskaper L(G) är Pspace-komplett för avgränsade grafer G, att kontrollera även enkla "lokala" egenskaper L w (G) är oavgjort.
I REF S är en meddelande-sekvens diagram (MSC) graf, I
Realizability and Verification of MSC-Graphs
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}