Metrisk intervall temporal logik

Vid modellkontroll är Metric Interval Temporal Logic (MITL) ett fragment av Metric Temporal Logic (MTL). Detta fragment föredras ofta framför MTL eftersom vissa problem som är oavgörbara för MTL blir avgörbara för MITL.

Definition

En MITL-formel är en MTL-formel, så att varje uppsättning av reella värden som används i nedsänkt är intervall, som inte är singlar, och vars gränser antingen är ett naturligt tal eller är oändliga.

Skillnad från MTL

MTL kan uttrycka ett påstående som meningen S: " P hölls för exakt tio tidsenheter sedan". Detta är omöjligt i MITL. Istället kan MITL säga T: " P hölls för mellan 9 och 10 tidsenheter sedan". Eftersom MITL kan uttrycka T men inte S , på sätt och vis, är MITL en begränsning av MTL som endast tillåter mindre exakta uttalanden.

Problem som MITL undviker

En anledning till att vilja undvika ett påstående som S är att dess sanningsvärde kan ändras ett godtyckligt antal gånger i en enda tidsenhet. Sanningsvärdet för detta påstående kan faktiskt ändras lika många gånger som sanningsvärdet för P ändras, och P själv kan ändra ett godtyckligt antal gånger i en enda tidsenhet.

Låt oss nu betrakta ett system, såsom en tidsinställd automat eller en signalautomat , som vid varje ögonblick vill veta om S håller eller inte. Detta system bör återkalla allt som hänt under de senaste 10 tidsenheterna. Som framgått ovan betyder det att den måste återkalla ett godtyckligt stort antal händelser. Detta kan inte implementeras av ett system med ändligt minne och klockor.

Begränsad variabilitet

En av de största fördelarna med MITL är att varje operatör har egenskapen bounded variability. Exempel:

Med tanke på påståendet T definierat ovan. Varje gång sanningsvärdet för T växlar från falskt till sant förblir det sant under minst en tidsenhet. Bevis: Vid en tidpunkt t där T blir sant betyder det att:

• mellan 9 och 10 tidsenheter sedan var P sant.
• strax före tid t var P falsk .

Därför var P sant för exakt 9 tidsenheter sedan. Det följer att, för varje $t'\in [0,1]$ , vid tiden $t+t'$ , var P sant ${ \displaystyle 9+t'}$ tidsenheter sedan. Eftersom $9+t'\in [9,10]$ , vid tiden $t'$ , gäller T.

Ett system vill vid varje ögonblick veta värdet på T . Ett sådant system måste påminna om vad som hänt under de senaste tio tidsenheterna. Men tack vare den begränsade variabilitetsegenskapen måste den återkalla högst 10 tidsenheter när T blir sant. Och därav 11 gånger när T blir falskt. Detta system måste alltså återkalla högst 21 händelser och kan följaktligen implementeras som en tidsinställd automat eller en signalautomat .

Exempel

Exempel på MITL-formler:

• $\square \diamond _{(0,1)}p$ anger att bokstaven $p$ förekommer minst en gång i varje öppet intervall av längd 1.
• $\triangleright _{\{i\}}p$ där $\triangleright _{\{i\}}p$ är profetiaoperatorn definierad som ${\displaystyle \square _{(0,i)}\neg p\land \diamond _{(0,i]}p} och som$ anger att den första förekomsten av $p$ i framtiden är i $i$ tidsenhet.
• $p\land \square (p\implies \triangleright _{\{1\}}p)$ anger att $p$ håller exakt vid varje integral tid och inte någon annan gång.

Fragment

Säkerhet-MTL _0,∞

Fragmentet Safety-MTL _0,v definieras som delmängden av MITL _0,∞ som endast innehåller formler i positiv normalform där intervallet för varje tills operator har en övre gräns. Till exempel formeln $\Box (a\implies \Diamond _{(0,1]}b)$ som anger att varje $a$ följs , mindre än en tidsenhet senare, av a $b$ , tillhör denna logik.

Öppen och stängd MITL

Fragmentet Open-MTL innehåller formeln i positiv normal form så att:

• för varje ${U}}_{I}} är$ mathcal $I$ öppen, och
• för varje $}}_{I}}$ R stängs ${\displaystyle I} .$

Fragmentet Closed-MITL innehåller negationen av formler för Open-MITL .

Flat och Coflat MITL

Fragmentet Flat-MTL innehåller formeln i positiv normal form så att:

• för varje ${\displaystyle \phi _{1}{\mathcal {U}}_{I}\phi _{2}} ,$ om $I$ är obegränsad, då ${ \displaystyle \phi _{1}}$ är en LTL-formel
• för varje ${\displaystyle \phi _{1}{\mathcal {R}}_{I}\phi _{2}} ,$ om $I$ är obegränsad, då ${ \displaystyle \phi _{2}}$ är en LTL-formel

Fragmentet Coflat-MITL innehåller negationen av formlerna för Flat-MITL .

Icke strikt variant

Givet vilket fragment L som Lns ^helst , är fragmentet restriktionen av L i vilken endast icke strikta operatorer används.

MITL _0,∞ och MITL ₀

Givet vilket fragment L som helst , är fragmentet L _0,∞ delmängden av L där den nedre gränsen för varje intervall är 0 eller den övre gränsen är oändlig. På liknande sätt betecknar vi med L ₀ (respektive L _∞ ) delmängden av L så att den nedre gränsen för varje intervall är 0 (respektive den övre gränsen för varje intervall är ∞).

Expressivitet över signaler

₀ Över signaler är MITL lika uttrycksfullt som MITL. Detta kan bevisas genom att tillämpa följande omskrivningsregler på en MITL-formel.

• $\phi {\mathcal {U}}_{(a,b)}\psi$ är ekvivalent med ${\displaystyle \Box _{(0,a]}\phi {\mathcal {U}}\psi \land \Diamond _{(a,b)}\psi } (konstruktionen för halvstängda och stängda intervall$ är liknande).
• $\Diamond _{(a,b)}\phi$ är ekvivalent med ${\displaystyle \Diamond _{(2a-b,a)}\Box _{(0,ba)}\Diamond _{(0,ba)}\phi } om 2 a − b$ ≥ $b \geq 0}$ .
• $\Diamond _{(a,b)}\phi$ är ekvivalent med $\Diamond _{(a, ba)}\Diamond _{(0,a)}\phi$ om $a<b$ .
• $\Diamond _{(a,+\infty )}\phi$$\Box _{(0,a)}\ Diamant \phi$ ekvivalent med .

Genom att tillämpa dessa omskrivningsregler ökar storleken på formeln exponentiellt. Faktum är att talen $a$ och $b$ är traditionellt skrivna i binärt, och dessa regler bör tillämpas $O\left({\frac {b}{ ba}}\right)$ gånger.

Uttrycksförmåga över tidsbestämda ord

I motsats till fallet med signaler är MITL mer uttrycksfullt än MITL _0,∞ . Omskrivningsreglerna ovan gäller inte i fallet med tidsinställda ord eftersom, för att skriva om $\Diamond _{(a,b)}$ måste antagandet vara att någon händelse inträffar mellan tiderna 0 och $a$ , vilket inte nödvändigtvis är fallet.

Tillfredsställelse problem

Problemet med att avgöra om en MITL-formel är tillfredsställbar över en signal är i PSPACE-komplett .

Referenser behövs

R. Alur, T. Feder och TA Henzinger. Fördelarna med avkopplande punktlighet. Journal of the ACM, 43(1):116–146, 1996. R. Alur och TA Henzinger. Logiker och modeller för realtid: en undersökning. I Proc. REX Workshop, Realtid: Teori i praktiken, sidorna 74–106. LNCS 600, Springer, 1992. TA Henzinger. Det handlar om tid: Realtidslogik granskad. I Proc. CONCUR'98, sidorna 439–454. LNCS 1466, Springer, 1998.