Metoderna för att lindra problemet med statsexplosion vid modellkontroll kan grovt klassificeras i symboliska metoder och abstraktionsmetoder [6]. Med symboliska metoder förstår vi användningen av koncisa datastrukturer och symboliska algoritmer som hjälper till att hålla tillståndsexplosion under kontroll genom att komprimera information, t.ex. med binära beslutsscheman eller effektiva SAT-förfaranden. Abstraction metoder i kontrast försöker minska storleken på tillståndet utrymme genom att använda kunskap om systemet och specifikationen för att modellera endast relevanta funktioner i Kripke struktur. En abstraktionsfunktion associerar en Kripke struktur Ã med en abstrakt Kripke struktur Ã sådan att två egenskaper innehar: Bevarande. Ã bevarar alla beteenden i Ã. Bevarande säkerställer att varje universell specifikation som är sant i Ã är också sant i Ã. Den motsatta innebörden kommer dock inte att hålla i allmänhet: en universell egendom som är falsk i Ö kan fortfarande vara sant i Ö. I detta fall kan det motexempel som erhållits över Ö inte rekonstrueras för betong Kripke struktur Ã, och kallas en falsk motexempel [10], eller en falsk negativ. Ett viktigt exempel på abstraktion är existentiell abstraktion [11] där de abstrakta staterna i huvudsak betraktas som likvärdiga klasser av konkreta stater; en övergång mellan två abstrakta stater äger rum om det sker en övergång mellan två konkreta medlemsstater i motsvarande ekvivalensklasser. I vissa fall kommer användarkunskapen om systemet att vara tillräcklig för att möjliggöra manuell bestämning av en god abstraktionsfunktion. I allmänhet, dock, att hitta abstraktion funktioner ger upphov till följande dikotomi: Om Ã är för liten, då falska motexempel är sannolikt att uppstå. Om Ã är för stor, då verifiering förblir ogenomförbar. Counterexample-Guided Abstraction Raffinement (CEGAR) är ett naturligt tillvägagångssätt för att lösa denna situation genom att använda en adaptiv algoritm som gradvis förbättrar en abstraktion funktion genom att analysera falska kontraexempel. (i) Inledande. Skapa en initial abstraktionsfunktion. ii) Förlagakontroll. Verifiera den abstrakta modellen. Om verifieringen lyckas är specifikationen korrekt, och algoritmen avslutas framgångsrikt. Annars kan man skapa ett motexempel på den abstrakta modellen. iii) Sanitetskontroll. Bestäm, om det abstrakta motexempelet är falskt. Om ett konkret motexempel
CEGAR-metoden Den motexempelvägda abstraktionsförfiningsmetoden (CEGAR) REF baserad på modellkontroll utformades för att minska kostnaden för att utforska stort sökutrymme på ett uttömmande sätt.
Counterexample-guided abstraction refinement
{'venue': 'In Computer Aided Verification', 'journal': None, 'mag_field_of_study': ['Computer Science']}