Abstrakt. Många oändliga tillståndssystem kan ses som välstrukturerade övergångssystem (WSS), d.v.s. system utrustade med en väl-kvasi-ordning på stater som också är en simuleringsrelation. WSTS är ett attraktivt mål för formell analys eftersom det finns generiska algoritmer som bestämmer intressanta verifieringsproblem för denna klass. Bland de mest populära algoritmerna finns accelerationsbaserade framåtanalyser för beräkning av täckande uppsättning. Uppsägning av dessa algoritmer kan endast garanteras för flattable WSTS. Ändå är många WSTS av praktiskt intresse inte platt och frågan om någon viss WSTS är platt är i sig obeslutbar. Vi föreslår därför en analys som beräknar täckande uppsättning och fångar essensen av accelerationsbaserade algoritmer, men offrar precision för garanterad terminering. Vår analys är en abstrakt tolkning vars abstrakta domän bygger på det ideala fullbordandet av det välbeställda tillståndsutrymmet, och en allt större operatör som härmar acceleration och kontrollerar förlusten av precision i analysen. Vi presenterar exempel på vårt ramverk för olika klasser av WSTS. Vår erfarenhet av prototypimplementering visar att vår analys, trots den inneboende precisionsförlusten, ofta beräknar den exakta täckande uppsättningen av det analyserade systemet.
I REF presenteras en ungefärlig algoritm för beräkning av täckningen för en över tillnärmning av uppsättningen nåbara termer i ett system med djup som avgränsas av k.
Ideal Abstractions for Well-Structured Transition Systems
{'venue': 'VMCAI', 'journal': None, 'mag_field_of_study': ['Computer Science']}