Kripke struktur

En Kripke-struktur er en beregningsmodel, tæt på en ikke-deterministisk endelig automat , opfundet af Saul Kripke . Det bruges for eksempel til modelkontrol for at repræsentere et systems opførsel. Det er en rettet graf, hvis knudepunkter repræsenterer systemets tilgængelige tilstande, og hvis buer repræsenterer overgange mellem tilstande. En mærkningsfunktion matcher hver tilstand med et sæt logiske propositioner sandt i den tilstand. Den timelige logik fortolkes generelt i Kripke-strukturer. Eksistensen af ​​visse stier i grafen betragtes derefter som en mulighed for realisering af formler.

Formel definition

Lad være et sæt af atomiske propositioner , det vil sige boolske udtryk, der vedrører variabler, konstanter og predikater. Vi betegner sæt af dele af . PÅP{\ displaystyle AP}2PÅP{\ displaystyle 2 ^ {AP}}PÅP{\ displaystyle AP}

En Kripke-struktur er en 4-tuple hvor: M=(S,jeg,R,L){\ displaystyle M = (S, I, R, L)}

• S{\ displaystyle S} er et endeligt sæt stater;
• jeg⊆S{\ displaystyle I \ subseteq S} er et sæt initialtilstande;
• R⊆S×S{\ displaystyle R \ subseteq S \ times S}er en overgangsrelation, der verificerer: for alt findes der sådan, at  ;s∈S{\ displaystyle s \ in S}s′∈S{\ displaystyle s \ \ i S}(s,s′)∈R{\ displaystyle (s, s ') \ i R}
• L:S→2PÅP{\ displaystyle L: S \ rightarrow 2 ^ {AP}}er en mærknings- eller fortolkningsfunktion .

Betingelsen forbundet med overgangsrelationen specificerer, at hver stat skal have en efterfølger i , hvilket indebærer, at man altid kan konstruere en uendelig sti i Kripke-strukturen. Denne egenskab er vigtig, når man beskæftiger sig med reaktive systemer . For at modellere en blokering i en Kripke-struktur er det tilstrækkeligt at løkke fastlåsningstilstanden på sig selv. R{\ displaystyle R}R{\ displaystyle R}

Mærkningsfunktionen definerer for hver tilstand sættet med alle atomforslag, der er gyldige i den tilstand. L{\ displaystyle L}s∈S{\ displaystyle s \ in S}L(s){\ displaystyle L (s)}

En sti i strukturen er en sekvens af tilstande, således at for alt . Den etiket af stien er sekvensen af sæt , som kan ses som en uendelig ord på alfabetet . M{\ displaystyle M}vs.=s1,s2,s3,...{\ displaystyle c = s_ {1}, s_ {2}, s_ {3}, \ ldots}(sjeg,sjeg+1)∈R{\ displaystyle (s_ {i}, s_ {i + 1}) \ i R}jeg{\ displaystyle i}w=L(s1),L(s2),L(s3),...{\ displaystyle w = L (s_ {1}), L (s_ {2}), L (s_ {3}), \ ldots}2PÅP{\ displaystyle 2 ^ {AP}}

Med denne definition kan en Kripke-struktur ses som en Moore-automat med et alfabet reduceret til en singleton, og hvis outputfunktion er mærkningsfunktionen.

Eksempel

I det modsatte eksempel er sættet med atomforslag . Her og er vilkårlige boolske egenskaber. Stat 1 indeholder de to propositioner, henholdsvis stater 2 og 3 og . Automaten indrømmer stien , og ordet er fortsættelsen af ​​de tilknyttede etiketter. De accepterede sekvenser af etiketter er beskrevet med det regulære udtryk: PÅP={s,q}{\ displaystyle AP = \ {p, q \}}s{\ displaystyle p}q{\ displaystyle q}q{\ displaystyle q}s{\ displaystyle p}vs.=1,2,1,2,3,3,3,...{\ displaystyle c = 1,2,1,2,3,3,3, \ ldots}w={s,q},q,{s,q},q,s,s,s,...{\ displaystyle w = \ {p, q \}, q, \ {p, q \}, q, p, p, p, \ ldots}

{s,q}ω∪({s,q}∗q)ω∪({s,q}∗q)∗sω{\ displaystyle \ {p, q \} ^ {\ omega} \ cup (\ {p, q \} ^ {*} q) ^ {\ omega} \ cup (\ {p, q \} ^ {*} q) ^ {*} p ^ {\ omega}}

Link til andre forestillinger

En Kripke-struktur kan ses som et tilstandsovergangssystem, hvor buer er umærket, og hvor stater er. I nogle forfattere er overgange af Kripke-strukturer mærket af handlinger, der træffes i et endeligt sæt, der normalt betegnes som lov . Når denne definition anvendes, kaldes den underliggende struktur, opnået ved at udelade handlingerne, tilstandsgrafen .

Tværtimod, Clarke et al. omdefinere en Kripke-struktur som et sæt overgangsrelationer (og ikke længere kun en), der hver svarer til en af ​​overgangsmærkerne, dette inden for rammerne af definitionen af ​​semantikken i den modale μ-calculus.

Noter og referencer

Bemærkninger

1. Kripke, Saul, 1963, "  Semantiske overvejelser om modal logik  ", Acta Philosophica Fennica , 16: 83-94.
2. Clarke, Grumberg og Peled 1999 , s.  14.
3. Schneider 2004 , s.  45.
4. Klaus Schneider, i Schneider 2004 , s.  12 skelner mellem tre typer systemer: transformationssystemer, interaktive systemer og reaktive systemer . Disse har den mest fleksible interaktion med brugeren.
5. Baier og Katoen 2008 , s.  20–21 og 94–95.
6. Clarke, Grumberg og Peled 1999 , s.  98.

(fr) Denne artikel er helt eller delvist taget fra den engelske Wikipedia- artikel med titlen "  Kripke-struktur (modelkontrol)  " ( se forfatterlisten ) .

Bibliografi

• Saul A. Kripke, ”  Semantisk analyse af modalogik. I. Normal modal propositional calculi  ”, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , vol.  9,1963, s.  67–96

• Saul A. Kripke, ”  Semantiske overvejelser om modalogik  ”, Acta Philosophica Fennica Fasc. , Vol.  16,1963, s.  83–94

• (en) Christel Baier og Joost-Pieter Katoen , principper for modelkontrol , The MIT Press ,2008, 975  s. ( ISBN  978-0-262-02649-9 )

• (en) Klaus Schneider , Verification of Reactive Systems: Formal Methods and Algorithms , Springer-Verlag , coll.  “Tekster inden for teoretisk datalogi. En EATCS-serie ”,2004, xiv + 600  s. ( ISBN  978-3-540-00296-3 , online præsentation )

• (en) Edmund M. Clarke , Orna Grumberg og Doron A. Peled , Model Checking , Cambridge, MIT Press ,1999, 314  s. ( ISBN  978-0-262-03270-4 , online præsentation )

Relaterede artikler

• Temporal logik
• Modalogik
• Beregnelighed
• Teori om automata
• Ikke-deterministisk Turing-maskine
• Kripke semantik
• Saul Kripke

Kursus noter

Der er mange kursusnotater på fransk om Kripke-strukturer i forbindelse med programlogik eller verifikation.

• “  Temporal Logics and Program Verification  ” (adgang 30. juni 2012 )

• Béatrice Berard, “  Formel verifikation af distribuerede systemer  ” (hørt 30. juni 2012 )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">