SMT-Based Satisfiability of First-Order LTL with Event Freezing Functions and Metric Operators

Contents lists available atScienceDirect

Information

and

Computation

www.elsevier.com/locate/yinco

SMT-based

satisfiability

of

first-order

LTL

with

event

freezing

functions

and

metric

operators

✩

Alessandro Cimatti,

Alberto Griggio,

Enrico Magnago,

Marco Roveri,

Stefano Tonetta

∗

FBK-irst,viaSommarive18,Trento,Italy

a

r

t

i

c

l

e

i

n

f

o

a

b

s

t

r

a

c

t

Articlehistory:

Received27February2018

Receivedinrevisedform15February2019 Accepted15February2019

Availableonline10December2019 Keywords:

First-orderlinear-timetemporallogic Metrictemporallogic

SMT-basedmodelchecking Temporalsatisfiability

In this paper, we propose to extend First-Order Linear-time Temporal Logic with Past addingtwo operators“atnext”and “atlast”,whichtake ininputatermand aformula and return the value of the term atthe next state in the future or laststate in the pastinwhichtheformula holds.The newlogic, namedLTL-EF,can beinterpretedwith different models of time (including discrete, dense, and super-dense time) and with differentfirst-ordertheories(àlaSatisfiabilityModuloTheories(SMT)).Weshowthatthe “atnext”and“atlast”canencode(first-order)MTL0,∞withcounting.Weproviderewriting procedures to reduce the satisfiability problem to the discrete-time case (to leverage onthemature state-of-the-artcorresponding verificationtechniques)and toremovethe extrafunctionalsymbols.Weimplementedthesetechniquesinthe nuXmv modelchecker enablingtheanalysisofLTL-EF andMTL0,∞basedonSMT-basedmodelchecking.Weshow thefeasibilityoftheapproachexperimentingwithseveralnon-trivialvalidandsatisfiable formulas.

©2019TheAuthors.PublishedbyElsevierInc.ThisisanopenaccessarticleundertheCC BY-NC-NDlicense(http://creativecommons.org/licenses/by-nc-nd/4.0/).

1. Introduction

Informalverification,thequestforasuitableformal specificationlanguagethatprovidestherighttrade-offamong ex-pressiveness,usability,andautomatedreasoning,isalwaysadifficulttask.Inthecontextofreal-timeembeddedsystems,the functionalspecificationofinput/outputvariablesisoftenentangledwithtimingaspects.Moreover,whenasystemor com-ponentisseenasablackbox,thepropertiesmustbespecifiedintermsoftheobservablevariablesormessagesexchanged withthesystemenvironment.Thisis,forexample,thecaseofpropertiesofmonitors(whichtriggeralarmsbasedonsome conditionontheobservedvariables/messages)orcontract-basedspecifications(whichformalizetheassumptions/guarantees ofcomponentsindependentlyoftheimplementation).Inthesecases,thepropertiesmustbeabletoexpresstherelationship betweentheobservable variables atdifferentpointsof time,without referringto internalsystemvariables that storethe corresponding values.Itis thereforenecessaryto havesuitable mechanismstorefer tothe value ofvariablesatdifferent pointsoftime.

✩ _{Thispaperextendstheworkpresentedin[1] withatranslationfromMTL0,∞withcountingoperatorsandwithamorerobusttoolimplementation}

andevaluation.ThisworkhasreceivedfundingfromtheEuropeanUnion’sHorizon2020researchandinnovationprogram undertheGrantAgreementNo. 700665(projectCITADEL).

*

Correspondingauthor.

E-mailaddresses:[email protected](A. Cimatti),[email protected](A. Griggio),[email protected](E. Magnago),[email protected](M. Roveri),[email protected]

(S. Tonetta).

https://doi.org/10.1016/j.ic.2019.104502

0890-5401/©2019TheAuthors.PublishedbyElsevierInc.ThisisanopenaccessarticleundertheCCBY-NC-NDlicense (http://creativecommons.org/licenses/by-nc-nd/4.0/).

One of the mostpopular logics used in computer science to specify properties for formal verification is Linear-time TemporalLogic(LTL)[2]. Thetemporal domainistypicallydiscrete andmodelsare discrete,linearsequences ofstates.In thecaseofreal-timesystems,LTL isinterpretedoveradenseorsuper-densemodelsoftime [3].Inparticular,insuper-dense timemodels,thetemporaldomaincombinesdensesetsofrealtimepointswith(discrete)sequencesofinstantaneoustime points, as needed for example for asynchronous real-time systems. When considering real models of time, it becomes natural to haveconstraints onthe time elapsing betweendifferentevents. Therefore,LTL has been extended eitherwith clocks/freezingoperators, asinTPTL [3],orwithmetricoperators asin[4–7]. Theseextensionshavebeencombinedwith first-orderlogictorepresentmessagepassing [8] orformonitoringspecification [9].

Inthispaper,weconsiderFirst-OrderLTL [10] withfutureaswellaspastoperators [11].The systemstateisdescribed by individualvariables, andfirst-orderfunctions/predicatesexpresstheirrelationship.Inthe spiritofSatisfiabilityModulo Theories(SMT) [12],theformulasareinterpretedmoduloabackgroundfirst-ordertheoryasin [13] (here,we restricttoa quantifier-freefragmentwhereallthesymbolsinthesignaturearerigid).

We proposea newlogicthat extendsthequantifier-freefragment ofFirst-OrderLinear-TimeTemporalLogicwithPast operatorsbyaddingthe“atnext”u@F

˜

(φ)

andthe“atlast”u@P

˜

(φ)

functionsymbols,whichareused(resp.)torepresentthe valueofatermu atthenextstateinthefutureoratthelaststateinthepastinwhichtheformula

φ

holds.Forexample, theformulaG

(

alarm

↔

x@P

˜

(

read

)

= (

x@P

˜

(

read

))

@P

˜

(

read

))

saysthatalarm istrueiffinthelasttwo pointsinwhichread

wastruethevariablex hadthesamevalue.WerefertothisextensionofLTL asLTL withEvent-freezingFunctions(LTL-EF). AsforLTL,itcanbeinterpretedoverdifferenttemporaldomains(includingdiscrete,dense,andsuper-densetime)andwith differentfirst-ordertheories(àlaSMT).The“atnext”and“atlast”functionscanbeseenasageneralizationofEvent-Clock TemporalLogic(ECTL)operators [14,15,6] (which,inturn,arethelogicalcounterpartofeventclocks [16])andcanencode thefragmentMTL0,∞ [16] ofMetricTemporalLogic(MTL) [4],alsowithcounting [17,18].

WeproviderewritingprocedurestoreducethesatisfiabilityproblemofLTL-EF tothediscrete-timecasewithouttheextra functionsymbols.Thisreductionenablesfortheuseofallthematureandstate-of-the-artsatisfiability checkingtechniques developed for the discrete-timecase (see e.g. [19,20]). We implemented thesetechniques in the nuXmv modelchecker, which provides efficient SMT-based model checkingprocedures to verify temporal propertieson systems described with first-orderformulas(asdiscussedforinstancein [19,20]).Thisprovidesan effectivetool supportfortheanalysisofLTL-EF

andMTL0,∞.

Themaincontributionsofthepaperarethefollowing.First,weidentifyanextensionofLTL thatcanexpressinteresting properties relatingvariables at differentpoints of time. Second, we define the newoperators in a very rich settingthat includes first-order constraints, pastoperators, dense andsuper-dense semantics; this givesalso a uniform treatment of

LTL satisfiability modulo theories inthe caseofreal-time models.Third, we show how MTL0,∞ formulas (extendedwith

counting) can beexpressed inLTL-EF.Fourth, we implementedthe approachin amaturemodel checker,showingthat it caneffectivelyproveinterestingproperties,whilemanylogicsinthereal-timesettinglacktoolsupport.

The restofthepaperisorganized asfollows:Section 2providesan analysisoftherelatedwork. Section3introduces theconsideredtemporaldomains,thelogicsLTL andMTL0,∞,andtheir satisfiabilitymodulotheories;Section4definesthe extension withtheneweventfreezingfunctions;Section 5details howtotranslateanMTL0,∞ formulaintoanequivalent

LTL-EF formula;Section6showshowtotranslateanLTL-EF formulaoversuper-densetimeintoanequisatisfiableoneover discrete time;Section7describeshowtotranslate anLTL-EF formulaoverdiscretetime intoanequisatisfiableoneinLTL;

Section8presentstheexperimentalresults;finally,Section9concludesthepaperanddrawsdirectionsforfuturework.

2. Relatedwork

The most naturalalternative to the newoperators proposed in thispaper wouldbe to use registers [21] orfreezing quantifiers [3]. LTL-EF adopts a more declarative style with functions that directly return the value of variables at the next or last state in which a formula will be/was true, resulting in a more natural specification. Despite the fact that freezingquantifiersprovidea higherexpressiveness(alsowithrespecttoMTL [22]),they arenotsocommoninindustrial applications (at least compared toLTL and MTL),either because they are lessintuitive touse, orbecause they lack tool support.

The“atnext”and“atlast”functionsymbolsofLTL-EF canbeseenasageneralizationoftheEvent-ClockTemporalLogic (ECTL) operators [14,15,6] and canbe used toencode the fragment MTL0,∞ [16] ofMetric TemporalLogic(MTL) [4] also withcounting [17,18].WeremarkthattheECTL operatorsarethelogicalcounterpartofeventclocks [16].Oursemanticsfor

LTL-EF isclosetotheonedefinedin[15] foreventclocksinEvent-ClockTimedAutomataandforthecorresponding quanti-fiersintheequally-expressivemonadiclogic.However,differentlyfrom[15],wedonotrequiretheuseofanynonstandard realnumber,whichisinsteadusedin[15] tohandleoperatorswithleft-openintervals.

Therewriting weadoptedtoreducethesatisfiabilityproblemforLTL-EF tothediscretetime case [2] isinspiredbythe onedescribed in [23]:wealsosplitthetimeevolutionintoasequenceofsingularoropenintervalsinsuchawaythatan executiontraceisfinefortheinputformulaonsuchintervals. However,theconsideredtemporallogicisdifferentandthe discretizationofformulasdiffersevenforthecommonfragment:infact,inthispaper,weconsiderastandardsemanticsof

LTL wheretimepointsarequantifiedoveradenseorsuper-densetemporaldomain,whilein[23] thesemanticsoftemporal operatorsquantifiesoversequencesofintervals.

Fig. 1. Illustration of a super-dense time model (from [29]).

Regardingtoolsupport,wearenotawareofanyothertoolthatisabletoprovethevalidityofMTL0,∞ withparametric

boundsin the caseof dense or super-dense time, while instead ourimplementation in nuXmv supports also first-order constraints.Weareawareofonlythreerelatedtools,namelyMigthyL [24],Zot [25],andATMOC [26,27].However,MigthyL usesa(discrete)pointwisesemanticsforMTL,whileZotandATMOConlysupportboundedsatisfiabilityofMTL properties.

3. Background

Inthissection, we providethebackgroundmaterial onwhich thelater technicalsectionsarebased.We beginwitha formaldescriptionofthetemporaldomains weconsider(§3.1),andthenproceedtointroducingthesyntax andsemantics offirst-orderLinearTemporalLogic(§3.2and§3.4)andMetricTemporalLogic(§3.6),making explicittheassumptionson tracesonwhichwerelyforourresults(§3.5).

3.1. Timemodels

R

+₀isthesetofnon-negativerealnumbers.Atimeintervalisaconvexsubsetof

R

+₀.Theleftendpointofaninterval I

isdenotedbyl

(

I

)

,whiletherightendpointbyr

(

I

)

.Twointervals I andIarealmostadjacentiffr

(

I

)

=

l

(

I

)

(sotheymay overlapinatmostonepoint).Asingularintervalisanintervalintheform

[

a

,

a

]

forsomea

∈ R

+₀.Atimeintervalsequence isasequence I0

,

I1

,

I2

,

. . .

oftimeintervalssuchthat,foralli

≥

0,Ii andIi+1 arealmostadjacentand



i≥0Ii

= R

+0.

Weconsiderdifferentmodelsoftime [28,3].Atime modelisa structure

τ

= 

T

,

<,

0,v

withatemporaldomain T ,a totalorder

<

over T ,aminimumelement0

∈

T ,andafunction v

:

T

→ R

+₀ thatrepresentstherealtimeofatimepoint in T .The v functionisused insteadofa distance(e.g.,asin[4])to treatthe weakly-monotoniccasein amoreuniform way.Atimepoint isanelementofT .Inparticular,weconsiderthefollowingmodels:

•

discrete time model, where T

= N

, 0 and

<

are the standard zero andorder over naturalnumbers, v

(

0

)

=

0 and

v

(

0

),

v

(

1

),

v

(

2

),

. . .

is anon-decreasing divergentsequence(this isalsocalledthepointwisesemantics; weusethese

modelsalsofordiscrete-timeLTL ignoringthesereal-timetimestamps);

•

dense(strictly-monotonic)timemodel,whereT

= R

+₀,0 and

<

arethestandardzeroandorderovertherealnumbers, andv istheidentityfunction;

•

super-dense(weakly-monotonic)timemodel,where1)T

⊂ N × R

+₀ suchthatthesequenceofsetsI0

,

I1

,

I2

,

. . .

where, forall i

≥

0,theset Ii

:= {

r

| 

i

,

r

∈

T

}

,isatime intervalsequence (thussubsequentintervalscan overlapinatmost onepoint),2)



i

,

r

<



i

,

r

iffi

<

iori

=

iandr

<

r,3)0

= 

0

,

0

∈ N × R

₀+,and4) v

(



i

,

r

)

=

r.

Intuitively,super-densetimemodelsconsistofalternatingdiscretesequencesofpointsintheform

{

i

,

r

},

{

i

+

1

,

r

,

. . .

(withthesametimestampr)anddensesets(containinganuncountablenumberoftimepointswithdifferenttimestamps)

oftheform



i

,

r

,



i

,

r

,



i

,

r

,

. . .

(withthesamecounter i). ThisisillustratedinFig.1(taken from[29]),wherediscrete

pointsarerepresentedbycircles(andarelabeledwiththeircorrespondingtimepoints),anddensesetsarerepresentedby continuouslines.

Notethatanysuper-densetimemodelwheretheintervalsintheunderlyingtimeintervalsequencearenotoverlapping isisomorphictothedensetimemodel.

3.2. First-orderlinear-timetemporallogic

WeconsiderFirst-OrderLinear-timeTemporalLogicwithPastOperators,whichwerefertoforsimplicityasLTL.Weusea non-strictversionof“until”and“since”operatorsandaddadense-timeversionof X andY ,denotedX and

˜

Y respectively.

˜

This allows us to define a simpler discretization, since discrete-time LTL typically uses non-strict version of “until” and “since” (althoughtheapproach can beextended to handlealsothestrict version of“until” and“since” asshownin [1]). Intuitively,thesemantics ofthe“discrete” X operatoranditsdense-timecounterpart X in

˜

thesuper-dense settingisthe following: X

φ

istrue atatime point t if andonly ift isimmediatelyfollowed byanother time point t withthe same timestampinwhich

φ

holds(e.g.if

φ

holdsat



4

,

6

inFig.1,then X

φ

holdsat



3

,

6

);instead,X

˜

φ

holdsatt ifandonlyif

t isimmediatelyfollowedbyadensesetoftimepointsinwhich

φ

holds(e.g.intheexampleofFig.1,X

˜

φ

holdsat



2

,

1

.

5

if

φ

holdsintheintervalbetween



2

,

1

.

5

and



3

,

6

).

Givenafirst-ordersignature



andasetV ofvariables,wedefinethesyntaxof



-formulasasfollows:

φ

:=

p

(

u

, . . . ,

u

)

| φ ∧ φ | ¬φ | φ

U

φ

| φ

S

φ

|

X

φ

| ˜

X

φ

|

Y

φ

| ˜

Y

φ

where p is apredicatesymbol in



, u is a term, f is a functionsymbol in



, c isa constant symbolin



, andx is a variableinV .



-formulasareviewedasa first-orderstructureinterpretingthe symbolsin



andassignments tovariablesthat vary along time. Morespecifically, a state s

= 

M

,

μ

is givenby a first-orderstructure M and an assignment

μ

of variables of V intothe domainof M. Givena state s

= 

M

,

μ

anda symbol c in



or variablex

∈

V ,we uses

(

c

)

todenote the interpretation ofc in M ands

(

x

)

to denotethevalue

μ

(

x

)

assignedby

μ

to x.Given M,let VM _{bethesetofstateswith} first-orderstructureM.Atrace

σ

= 

M

,

τ

,

μ

isgivenbyafirst-orderstructureM,atimemodel

τ

,andamapping

μ

from thedomainof

τ

intoVM.Givenatrace

σ

= 

M

,

τ

,

μ

andt

∈

τ

,wedenoteby

σ

(

t

)

thestate



M

,

μ

(

t

)

.

Inourdefinitionoftrace,thefirst-orderstructure M issharedbyalltimepoints,meaningthattheinterpretationofthe symbolsin thesignature



isrigid, thatis,it doesnotvary withtime. However, note thatthe interpretationofsymbols maynot be“fixed”by thebackgroundtheory.These“uninterpreted”symbolsare alsocalledparameters.Forexample,the signature



can includethesymbolsof thetheory ofreals (includingthe constants 0 and1) andan additionalconstant symbol p,whosevalue(i)isnotdeterminedbythetheorybut(ii)doesnotvarywithtime(thus,p isaparameter).

Weassumea



first-ordertheory

T

tobegiven.Givena



first-orderstructureM, anassignment

μ

tovariablesofV ,

anda



first-orderformula

φ

over V ,weusethestandard notionof



M

,

μ

|=

T

φ

.Intherestofthepaper,we omitthe first-ordersignature



andtheory

T

forsimplicity.

Givena trace

σ

= 

M

,

τ

,

μ

,a time pointt of

τ

,anda



formula

φ

, wedefine

σ

,

t

|= φ

recursively onthe structure of

φ

:

σ

,

t

|=

p

(

u

, . . . ,

u

)

iff

σ

(

t

)

|=

p

(

u

, . . . ,

u

)

σ

,

t

|= φ

1

∧ φ

2iff

σ

,

t

|= φ

1and

σ

,

t

|= φ

2

σ

,

t

|= ¬φ

iff

σ

,

t

|= φ

σ

,

t

|= φ

1U

φ

2iff there exists t

≥

t

,

σ

,

t

|= φ

2and for all t

,

t

≤

t

<

t

,

σ

,

t

|= φ

1

σ

,

t

|= φ

1S

φ

2iff there exists t

≤

t

,

σ

,

t

|= φ

2and for all t

,

t

<

t

≤

t

,

σ

,

t

|= φ

1

σ

,

t

|=

X

φ

iff there exists t

>

t

,

σ

,

t

|= φ

and there exists no t

,

t

<

t

<

t

σ

,

t

|= ˜

X

φ

iff for all t

>

t

,

there exists t

,

t

<

t

<

t

,

σ

,

t

|= φ

σ

,

t

|=

Y

φ

iff t

>

0 and there exists t

<

t

,

σ

,

t

|= φ

and there exists no t

,

t

<

t

<

t

σ

,

t

|= ˜

Y

φ

iff t

>

0 and for all t

<

t

,

there exists t

,

t

<

t

<

t

,

σ

,

t

|= φ

Finally,

σ

|= φ

iff

σ

,

0

|= φ

.Wesaythat

φ

issatisfiableiffthereexists

σ

suchthat

σ

|= φ

.Wesaythat

φ

isvalidiff,for all

σ

,

σ

|= φ

.

We say that aformula

φ

1 globally entailsanother formula

φ

2, denotedby

φ

1

|=

G

φ

2, iffforall

σ

,forall t,

σ

,

t

|= φ

1 impliesthat

σ

,

t

|= φ

2.Wesaythattwoformulas

φ

1 and

φ

2 aregloballyequivalent,denotedby

φ

1

≡

G

φ

2iff

φ

1

|=

G

φ

2and

φ

2

|=

G

φ

1.

3.3. Nextandyesterday

Asdiscussedatthebeginningofprevioussection,wedefinethesemanticsofX (“next”)andY (“yesterday”)alsointhe caseofdenseorsuper-dense time.Inthecaseofweakly-monotonictime, X

φ

canbe trueonlyona discretestep(i.e.,in



n

,

t

if



n

+

1

,

t

isalsoinT ).Inthecaseofstrictly-monotonictime, X

φ

isalwaysfalse.

As forthe“dense” counterpartof X and Y ,inthe super-densetime case, X

˜

φ

isfalse inthediscrete steps,while itis trueonrightaccumulationpointsforpointssatisfying

φ

.Thus, X

˜

φ

isalwaysfalseinthecaseofdiscretetime,whileinthe caseofdensetimeitistrueintherightaccumulationpointsofpointssatisfying

φ

.

Inthediscrete-timesetting,weoftenusealsothefunctionalcounterpartof X ,heredenotedbynext,asin [10].Givena termu,theinterpretationofnext

(

u

)

inatrace

σ

atthetimepointt isequaltothevalueofu assignedby

σ

atthetime pointt

+

1.“next”doesnottypicallyhaveacounterpartinthedensetimecase.

3.4. Abbreviations

Weusethefollowingstandardabbreviations:

φ

1

∨ φ

2

:= ¬(¬φ

1

∧ ¬φ

2

)

 :=

p

∨ ¬

p

⊥ := ¬

F

φ

:= 

U

φ

G

φ

:= ¬(

F

¬φ)

Z

φ

,whichinthediscrete-timesettingisusuallydefinedas

¬

Y

¬φ

(whichisequivalenttoY



→

Y

φ

),isaweakversion ofY thatisalwaystrueintheinitialpoint.Here,itisextendedtotakeintoaccountthe(super-)densetimemodels:

Z

φ

:= (

Y

 ∨ ˜

Y

) →

Y

φ

Z

˜

φ

:= (

Y

 ∨ ˜

Y

) → ˜

Y

φ

Finally,wedefinefurtherabbreviationstorepresentthestrictversionsof F andP alsowithcounting:

˜

F

φ

:= ˜

X F

φ

|

X F

φ

P

˜

φ

:= ˜

Y P

φ

|

Y P

φ

˜

F1

φ

:= ˜

F

φ

P

˜

1

φ

:= ˜

P

φ

˜

Fk

φ

:= ˜

F

(φ

∧ ˜

Fk−1

φ)

P

˜

k

φ

:= ˜

P

(φ

∧ ˜

Pk−1

φ)

˜

G and H are

˜

definedas:

˜

G

φ

:= ¬( ˜

F

¬φ)

H

˜

φ

:= ¬( ˜

P

¬φ)

˜

Gk

φ

:= ¬( ˜

Fk

¬φ)

H

˜

k

φ

:= ¬( ˜

Pk

¬φ)

3.5. Finitevariability

Asusual inmanyworksonreal-timetemporallogics(e.g.,[5,30]),weassume the“finitevariability”oftraces, i.e.,that theevaluationofpredicatesbyatrace changesfromtruetofalse orvice versaonlyfinitely-ofteninanyfiniteintervalof time. Thiscanbe liftedtotemporal formulasinthesense thattemporal operatorspreserve thefinitevariabilityproperty (asproved,forexample,in[5]).Formally,wesaythatatrace

σ

isfine for

φ

inatimeintervalI iffforallt

,

t

∈

I,

σ

,

t

|= φ

iff

σ

,

t

|= φ

.Atrace

σ

hasthefinitevariability propertyiffforeveryformula

φ

thereexistsasequenceofpointst0

,

t1

,

t2

. . .

of

σ

suchthat

σ

isfine for

φ

ineveryinterval

(

ti

,

ti+1

)

,fori

≥

0.

Notethat, inthecaseoffinite variability, X

˜

φ

meansthat

φ

istrue inarightneighborhood (thuscoincidingwiththe definitiongivenin[1])1_{andthat X}

˜

_φ

_{∨ ˜}

_X

_¬φ

_{isalways trueinanynon-discretepoint.Moreover,thefollowingequivalences}

hold:

¬ ˜

X

φ

=

X

 ∨ ˜

X

¬φ

¬

X

φ

= ˜

X

 ∨

X

¬φ.

Inthefollowing,weassumethattraceshavethefinitevariabilityproperty.

3.6. Metrictemporallogicwithcountingoperators

Inthissection,wedefineanextensionofMetricTemporalLogic(MTL)[4,16] extendedwithfirst-orderpredicates, para-metricintervals(intervalswhoseboundsaredefinedbyexpressionsoverparameters),andcountingoperators.

MetricTemporalLogicwithCounting(MTLC)formulasarebuiltwiththefollowinggrammar:

φ

:=

p

(

u

, . . . ,

u

)

| φ ∧ φ | ¬φ | φ

UI

φ

| φ

SI

φ

|

−

→

Ck<cu

φ

|

←

_C

−

k <cu

φ

I

:= [

cu

,

cu

] | (

cu

,

cu

] | [

cu

,

cu

)

| (

cu

,

cu

)

| [

cu

,

∞) | (

cu

,

∞)

cu

:=

c

|

f

(

cu

, . . . ,

cu

)

wherethetermsu aredefinedasbeforeandcu aretermsthatdonotcontainvariables.Thus,theboundsofintervalsused inMTLC arerigidandmaycontainparameters.Weassumeherethatthebackgroundfirst-ordertheorycontainsthetheory ofrealsandthatthetermscu haverealtype.

Intuitively,

−

→

Ck_<cu

φ

istrueifandonlyif

φ

holds atleastk timesintheinterval

[

0

,

cu

)

(andsimilarlyfor

←

C

−

k_<cu

φ

).The abbreviations FI

,

GI

,

PI

,

HI andtheir strict versionsare definedintheusual way. Moreover,forall logics definedinthis section, we abbreviate the intervals

[

0

,

a

]

,

[

0

,

a

)

,

[

a

,

∞)

,

(

a

,

∞)

,

[

a

,

a

]

, by respectively

≤

a,

<

a,

≥

a,

>

a,

=

a. Thus, for example,F₌pb isanabbreviationof F[p,p]b.

Let

σ

= 

M

,

τ

,

μ

.Wegivethesemanticsjustforthemetricoperators:

σ

,

t

|= φ

1UI

φ

2iff there exists t

≥

t

,

v

(

t

)

−

v

(

t

)

∈

M

(

I

),

σ

,

t

|= φ

2

and for all t

,

t

≤

t

<

t

,

σ

,

t

|= φ

1

Fig. 2. Graphical view of different cases in whichφholds in the future. t represents “the next point in the future in whichφholds”.

σ

,

t

|= φ

1SI

φ

2iff there exists t

≤

t

,

v

(

t

)

−

v

(

t

)

∈

M

(

I

),

σ

,

t

|= φ

2

and for all t

,

t

<

t

≤

t

,

σ

,

t

|= φ

1

σ

,

t

|=

−

→

C_<k_cu

(φ)

iff there exist t1

, . . . ,

tk

,

t

<

t1

<

t2

< . . . <

tk

,

v

(

tk

)

−

v

(

t

) <

M

(

cu

)

such that for all i

∈ [

1

,

k

],

σ

,

ti

|= φ

σ

,

t

|=

←

C

−

_<k_cu

(φ)

iff there exist t1

, . . . ,

tk

,

tk

<

tk−1

< . . . <

t1

<

t v

(

t

)

−

v

(

tk

) <

M

(

cu

)

such that for all i

∈ [

1

,

k

],

σ

,

ti

|= φ

where M

(

I

)

isthesetobtainedfromI bysubstitutingthetermsattheendpointswiththeir interpretation(thusitmaybe alsotheemptyset).

MTLC0,∞isthesubset ofMTLC wheretheintervalsinmetricoperatorsareintheform

[

0

,

a

]

,

(

0

,

a

]

,

[

0

,

a

)

,

(

0

,

a

)

,

[

a

,

∞)

,

(

a

,

∞)

.

WeconsiderEvent-Clockoperatorsasabbreviations:



I

φ

:= (¬φ)

UI

φ

I

φ

:= (¬φ)

SI

φ

4. LTLwitheventfreezingfunctions 4.1. Untilnextoccurrence

Before introducing the new operators, we observesome subtleties of the dense-time semantics. In the discrete-time setting, F

φ

and

(

¬φ)

U

φ

are equivalent.In otherwords, if

φ

is trueinthefuture,thereexists afirst pointinwhichit is true, while

φ

isfalse inall precedingpoints. Thisisnot thecaseinthe dense-timesetting,since,forexample,thethird trace ofFig.2satisfies F

φ

butnot

(

¬φ)

U

φ

:forevery timeinwhich

φ

holds,there existsaleftopen intervalinwhich

φ

holdsaswell.

Wecaninsteaduseanothervariantoftheuntiloperatordefinedas:

φ

1UC

φ

2

:= φ

1U

(φ

2

∨ (φ

1

∧ ˜

X

φ

2

))

Thus, with UC we are requiring that

φ

2 holds in a point or in every point of a right interval. In this case, we are guaranteedthatthereexistsaminimumpointthatsatisfiessuchacondition.Infact,sinceweareassumingfinitevariability,

F

φ

isequivalent to

(

¬φ)

UC

φ

= (¬φ)

U

(φ

∨ ˜

X

φ)

.In thenext sections,we willusethiscondition to characterizethenext pointinthefuturethatsatisfies

φ

.Inparticular,whenwesay“thenextpointinthefutureinwhich

φ

holds”,weactually meanthat

φ

holdsinthatpointorinarightleft-openinterval(seealsoFig.2).Similarly,forthepastcase.

Note that this is related to the issue of U in the dense time setting raised first by Bouajjani andLakhnech in [31] andlater byRaskin andSchobbensin[14],namely, that

φ

1U

φ

2 issatisfied onlyifthetimeinterval inwhich

φ

2 holdsis left-closed.In[31],thisissolvedbyconsidering

(φ

1

∨ φ

2

)

U

φ

2.However,thisdoesnotsolveourissueofcharacterizingthe first point inwhich

φ

2 holds. In[14], the issuewas solved atthe semantic level,by defining the U operator on timed state sequences thatarefineforthesubformulas, andquantifying overthetimeintervalsofthesequenceinsteadofover the points of the time domain. We instead choose a more classical approach to define the semantics, which seems to clarify betterwhatwe meanfor“thenext pointinwhich

φ

holds”.Oursemanticsisclosertotheonedefinedin[15] for

eventclocksinEvent-ClockTimedAutomataandforthecorrespondingquantifiersintheequally-expressivemonadiclogic. Differentlyfrom[15],however,oursolutiondoesnotrequiretheuseofanynonstandardrealnumber,whichisinsteadused in[15] tohandlethecaseinwhich

φ

holdsinaleft-openinterval.

4.2. Eventfreezingfunctions

Weextendthelogic withtwo binaryoperators, “atnext” u@F

˜

(φ)

and“atlast”u@P

˜

(φ)

,which takeininput atermu

andaformula

φ

andrepresentthevalueofu at thenextpointinthefuture,respectivelyatthelast pointinthepast,in which

φ

holds.Ifsuchpoint doesnot exist,weconsidera defaultvaluerepresentedby avariabledef_u@F˜(φ)or def_u@P˜(φ). Wealso useanif-then-else operatorite

(φ,

u

,

v

)

,extended tothetemporalcase, whichevaluates tou or v dependingon whether

φ

holdsornot.

ThesetofLTL withEventFreezingFunctions(LTL-EF)formulasisthereforedefinedasfollows:

φ

:=

p

(

u

, . . . ,

u

)

| φ ∧ φ | ¬φ | φ

U

φ

| φ

S

φ

|

X

φ

| ˜

X

φ

|

Y

φ

| ˜

Y

φ

u

:=

c

|

x

|

f

(

u

, . . . ,

u

)

|

u@F

˜

(φ)

|

u@P

˜

(φ)

|

ite

(φ,

u

,

u

)

ThesemanticsofLTL isextendedasfollows:

•

σ

(

t

)(

u@F

˜

(φ))

=

σ

(

t

)(

u

)

ifthereexistst

>

t suchthat,forallt,t

<

t

<

t,

σ

,

t

|= φ

and

σ

,

t

|= φ

;

σ

(

t

)(

u@F

˜

(φ))

=

σ

(

t

)(

u

)

ifthereexistst

≥

t suchthat,forallt,t

<

t

≤

t,

σ

,

t

|= φ

and

σ

,

t

|= ˜

X

φ

; otherwise,

σ

(

t

)(

u@F

˜

(φ))

=

σ

(

t

)(

def_u@˜F(φ)

)

•

σ

(

t

)(

u@P

˜

(φ))

=

σ

(

t

)(

u

)

ifthereexistst

<

t suchthat,forallt,t

<

t

<

t,

σ

,

t

|= φ

and

σ

,

t

|= φ

;

σ

(

t

)(

u@P

˜

(φ))

=

σ

(

t

)(

u

)

ifthereexistst

≤

t suchthat,forallt,t

<

t

≤

t,

σ

,

t

|= φ

and

σ

,

t

|= ˜

Y

φ

; otherwise,

σ

(

t

)(

u@P

˜

(φ))

=

σ

(

t

)(

def_u@P˜(φ)

)

•

σ

(

t

)(

ite

(φ,

u1

,

u2

))

=

σ

(

t

)(

u1

)

if

σ

,

t

|= φ

,else

σ

(

t

)(

ite

(φ,

u1

,

u2

))

=

σ

(

t

)(

u2

)

wheredef_u@F˜(φ)anddef_u@P˜(φ)areextravariablesaddedfortheevent-freezingfunctionsthatareusedtorepresentadefault valuewhenthereisnofuture/pastoccurrenceof

φ

.

The“if-then-else”operatorite canbeusedtodefinethenon-strictversion: u@F

(φ)

:=

ite

(φ,

u

,

u@F

˜

(φ))

u@P

(φ)

:=

ite

(φ,

u

,

u@P

˜

(φ)).

Wedefinethefollowingabbreviations:

u@F

˜

1

(φ)

:=

u@F

˜

(φ)

u@F

˜

i+1

(φ)

:=(

u@F

˜

(φ))

@F

˜

i

(φ)

for i

≥

1

u@P

˜

1

(φ)

:=

u@P

˜

(φ)

u@P

˜

i+1

(φ)

:=(

u@P

˜

(φ))

@P

˜

i

(φ)

for i

≥

1

Inprinciple,wecanalsodefinethefunctionnext asanabbreviation: next

(

u

)

=

u@F

˜

(

)

.Thiswouldhavethestandard meaningondiscretesteps,andadefaultvalueonotherpoints.

4.3. Extensionwithexplicittime(XLTL-EF)

Inthissection,weextendthelanguagewithanexplicitnotionoftimethatcanbeconstrainedusingtheeventfreezing functionsdefinedabove.Inparticular, weintroduce an explicitsymboltime, whichrepresentsthetime elapsedfromthe initialstate.Weallowtime tobecomparedwithconstantterms.

ThenewsetofLTL-EF formulaswithexplicittime(XLTL-EF)isdefinedasfollows:

φ

:=

p

(

u

, . . . ,

u

)

|

tu



cu

| φ ∧ φ | ¬φ | φ

U

φ

| φ

S

φ

|

X

φ

| ˜

X

φ

|

Y

φ

| ˜

Y

φ

u

:=

c

|

x

|

f

(

u

, . . . ,

u

)

|

u@F

˜

(φ)

|

u@P

˜

(φ)

|

ite

(φ,

u

,

u

)

cu

:=

c

|

f

(

cu

, . . . ,

cu

)

|

cu@F

˜

(φ)

|

cu@P

˜

(φ)

|

ite

(φ,

cu

,

cu

)

tu

:=

time

|

time@F

˜

(φ)

|

time@P

˜

(φ)

|

time@F

˜

(φ)

−

time

|

time

−

time@P

˜

(φ)

 := <|>|≤|≥|=| =

ThesemanticsofLTL-EF isextendedbysimplysetting

σ

(

t

)(

time

)

:=

v

(

t

)

.Moreover,wedefinetwo additional abbrevia-tions:time_until

(φ)

:=

time@F

˜

(φ)

−

time andtime_since

(φ)

:=

time

−

time@P

˜

(φ)

.

Notethatweassumethatthesignature



containstherealarithmeticoperatorsandthattheunderlyingtheorycontains thetheoryofreals.

4.4. Sensorexample

Consider a sensor with input y and output x and a Boolean flag correct that represents whether or not the value reported by the sensor is correct. Letus specify that the output x is always equal to the last correct input value with

G

(

x

=

y@P

(

correct

))

.Weassume thata failureispermanent: G

(

¬

correct

→

G

¬

correct

)

.Consideralsoa Booleanvariable

read that representsthe eventofreadingthevariable x.Letussaythat thereading happensperiodicallywithperiod p: p

>

0

∧

read

∧

G

(

read

→ 

₌pread

)

.Finally,letussaythatanalarma istrueifandonlyifthelasttworeadvaluesarethe same: G

(

a

↔

x@P

˜

(

read

)

=

x@P

˜

2

(

read

))

.

Wewouldliketoprovethat,giventheabovescenario,everypointinwhichthesensorisnotcorrectisfollowedwithin 2

∗

p byanalarm:

(

G

(

x

=

y@P

(

correct

))

∧

G

(

¬

correct

→

G

¬

correct

)

∧

p

>

0

∧

read

∧

G

(

read

→ 

₌pread

)

∧

G

(

a

↔

x@P

˜

(

read

)

=

x@P

˜

2

(

read

)))

→

G

(

¬

correct

→

F_≤2∗pa

)

Inthefollowing,weshowthatproblemsofthiskindcanbeindeedsolvedautomaticallywithSMT-basedtechniques.

5. FromMTLC0,∞toLTL-EF

Inthissection,weshowhowMTLC0,∞formulascanbeexpressedinXLTL-EF.

Thefollowingequivalencesshowthecoverageofthecaseswithboundedintervals(notethatweareusingglobal equiv-alences

≡

G sothatMTLC0,∞formulascanberewrittenrecursivelyintoXLTL-EF formulas):

φ

1U<p

φ

2

≡

G

φ

1U

φ

2

∧

time@F

(φ

2

)

−

time

<

p (1)

φ

1S<p

φ

2

≡

G

φ

1S

φ

2

∧

time

−

time@P

(φ

2

) <

p (2)

φ

1U≤p

φ

2

≡

G

φ

1U

φ

2

∧

(3)

(

¬φ

2U

φ

2

∧

time@F

(φ

2

)

−

time

≤

p

∨

¬φ

2UX

˜

φ

2

∧

time@F

(φ

2

)

−

time

<

p

)

φ

1S≤p

φ

2

≡

G

φ

1S

φ

2

∧

(4)

(

¬φ

2S

φ

2

∧

time

−

time@P

(φ

2

)

≤

p

∨

¬φ

2SY

˜

φ

2

∧

time

−

time@P

(φ

2

) <

p

)

φ

1U(0,p)

φ

2

≡

G

φ

1U

( ˜

X

φ

1U

φ

2

∧

time@F

˜

(φ

2

)

−

time

<

p

)

(5)

φ

1S(0,p)

φ

2

≡

G

φ

1S

( ˜

Y

φ

1S

φ

2

∧

time

−

time@P

˜

(φ

2

) <

p

)

(6)

φ

1U(0,p]

φ

2

≡

G

φ

1U

(( ˜

X

φ

1U

φ

2

)

∧

(7)

((( ˜

X

¬φ

2U

φ

2

)

∧ (

time@F

˜

(φ

2

)

−

time

≤

p

))

∨

(( ˜

X

¬φ

2UX

˜

φ

2

)

∧ (

time@F

˜

(φ

2

)

−

time

<

p

))))

φ

1S(0,p]

φ

2

≡

G

φ

1S

(( ˜

Y

φ

1S

φ

2

)

∧

(8)

((( ˜

Y

¬φ

2S

φ

2

)

∧ (

time

−

time@P

˜

(φ

2

)

≤

p

))

∨

(( ˜

Y

¬φ

2SY

˜

φ

2

)

∧ (

time

−

time@P

˜

(φ

2

) <

p

))))

−

→

_Ck <p

(φ)

≡

Gtime@F

˜

k

(φ)

−

time

<

p

∧ ˜

Fk

(φ)

(9)

←

−

C_<k_p

(φ)

≡

Gtime

−

time@P

˜

k

(φ) <

p

∧ ˜

Pk

(φ)

(10) Wecanreducetheremainingmetricoperatorstotheaboveoneswiththefollowingreduction:

φ

1U>p

φ

2

≡

G

(

p

=

0

∧ φ

1U =0

φ

2

)

∨

(

p

>

0

∧

G_≤p

(φ

1

∧ φ

1U =0

φ

2

))

(11)

φ

1S>p

φ

2

≡

G

(

p

=

0

∧ φ

1S =0

φ

2

)

∨

φ

1U≥p

φ

2

≡

G

(

p

=

0

∧ φ

1U

φ

2

)

∨

(

p

>

0

∧

G<p

φ

1

∧

G≤pP≤0

( ˜

H≤0

φ

1

∧ φ

1U

φ

2

))

(13)

φ

1S≥p

φ

2

≡

G

(

p

=

0

∧ φ

1S

φ

2

)

∨

(

p

>

0

∧

time

≥

p

∧

H<p

φ

1

∧

H≤pF≤0

( ˜

G≤0

φ

1

∧ φ

1S

φ

2

))

(14)

where

φ

1U =0

φ

2 and

φ

1S =0

φ

2 areusedhereasabbreviationsfor

φ

1UX

˜

(φ

1U

φ

2

)

and

φ

1SY

˜

(φ

1U

φ

2

)

,respectively.

Note, in particular, the need of adding P₌0

φ

in the case the time distance is p due to the super-dense semantics. In caseofdense time, thelast two equivalences can be simplifiedto

φ

1U≥p

φ

2

≡

GG<p

φ

1

∧

G≤p

φ

1U

φ

2 and

φ

1S≥p

φ

2

≡

G

H<p

φ

1

∧

H≤p

φ

1S

φ

2.

Theorem1.EveryMTLC0,∞formulacanberewrittenintoanequivalentXLTL-EFformula.

Proof. Itissufficienttoprovethatallaboveequivalencesarecorrect.Wefirstprovethefuturecases.Inthefollowing,M is

thefirst-orderstructureofthetrace

σ

andthusM

(

p

)

istheevaluationofp in

σ

.

Equivalence(1)

•

Case

φ

1U<p

φ

2

|=

G

φ

1Uφ2

∧

time@F(φ2

)

−

time

<

p.

If

σ

,

t

|= φ

1U<p

φ

2thenthereexistst

≥

t suchthatv

(

t

)

−

v

(

t

)

<

M

(

p

)

,

σ

,

t

|= φ

2,andforallt,t

≤

t

<

t,

σ

,

t

|= φ

1. Thus,

σ

,

t

|= φ

1U

φ

2.Moreover,thereexistst,t

≤

t

≤

t,

σ

,

t

|= φ

2

∨ ˜

X

φ

2,v

(

t

)

−

v

(

t

)

<

M

(

p

)

,andforallt,t

≤

t

<

t,

σ

,

t

|= ¬φ

2.Thus,

σ

,

t

|=

time@F

(φ

2

)

−

time

<

p.

•

Case

φ

1Uφ2

∧

time@F(φ2

)

−

time

<

p

|=

G

φ

1U<p

φ

2.

If

σ

,

t

|= φ

1U

φ

2, then there exists t, t

≤

t,

σ

,

t

|= φ

2

∨ ˜

X

φ

2, and for all t, t

≤

t

<

t,

σ

,

t

|= ¬φ

2. If

σ

,

t

|=

time@F

(φ

2

)

−

time

<

p,then v

(

t

)

−

v

(

t

)

<

M

(

p

)

.Thus,

σ

,

t

|= φ

1U<p

φ

2.

Equivalence(3)

•

Case

φ

1U≤p

φ

2

|=

G

φ

2

≡

G

φ

1Uφ2

∧ (¬φ

2Uφ2

∧

time@F(φ2

)

−

time

≤

p

∨ ¬φ

2UXφ

˜

2

∧

time@F(φ2

)

−

time

<

p).

If

σ

,

t

|= φ

1U≤p

φ

2 thenthereexistst

≥

t suchthatv

(

t

)

−

v

(

t

)

≤

M

(

p

)

,

σ

,

t

|= φ

2,andforallt,t

≤

t

<

t,

σ

,

t

|= φ

1. Thus,

σ

,

t

|= φ

1U

φ

2. Moreover, there exists t, t

≤

t

≤

t,

σ

,

t

|= φ

2

∨ ˜

X

φ

2, and forall t, t

≤

t

<

t,

σ

,

t

|= ¬φ

2. Also,either

σ

,

t

|= φ

2 andv

(

t

)

−

v

(

t

)

≤

M

(

p

)

,or

σ

,

t

|= ˜

X

φ

2 andv

(

t

)

−

v

(

t

)

<

M

(

p

)

.Thus,

σ

,

t

|= (φ

1

∧ ¬φ

2

)

U

φ

2

∧

time@F

(φ

2

)

−

time

≤

p

∨ (φ

1

∧ ¬φ

2

)

U

(φ

1

∧ ˜

X

φ

2

)

∧

time@F

(φ

2

)

−

time

<

p.

•

Case

φ

1Uφ2

∧ (¬φ

2Uφ2

∧

time@F(φ2

)

−

time

≤

p

∨ ¬φ

2UXφ

˜

2

∧

time@F(φ2

)

−

time

<

p)

|=

G

φ

1U≤p

φ

2.

If

σ

,

t

|= φ

1U

φ

2, then there exists t, t

≤

t,

σ

,

t

|= φ

2, and for all t, t

≤

t

<

t,

σ

,

t

|= φ

1. If

σ

,

t

|= ¬φ

2U

φ

2

∧

time@F

(φ

2

)

−

time

≤

p,thenthereexistst,t

≤

t

≤

t,suchthat

σ

,

t

|= φ

2,andforallt,t

≤

t

<

t,

σ

,

t

|= ¬φ

2 and

v

(

t

)

−

v

(

t

)

≤

M

(

p

)

.Since t

≤

t,

σ

,

t

|= φ

1U≤p

φ

2.Similarly, if

σ

,

t

|= ¬φ

2UX

˜

φ

2

∧

time@F

(φ

2

)

−

time

<

p, thenthere existst,t

≤

t

≤

t,

σ

,

t

|= ˜

X

φ

2,andforallt,t

≤

t

<

t,

σ

,

t

|= ¬φ

2 andv

(

t

)

−

v

(

t

)

≤

M

(

p

)

.Thus,

σ

,

t

|= φ

1U≤p

φ

2.

Equivalence(5)

•

Case

φ

1U(0,p)

φ

2

|=

G

φ

1U( ˜Xφ1Uφ2

∧

time@F(φ

˜

2

)

−

time

<

p).

If

σ

,

t

|= φ

1U<p

φ

2 then there exists t

<

t such that 0

<

v

(

t

)

−

v

(

t

)

<

M

(

p

)

,

σ

,

t

|= φ

2, andfor all t, t

≤

t

<

t,

σ

,

t

|= φ

1.Lett0 thegreatestpointsuchthatt

≤

t0 andv

(

t

)

=

v

(

t0

)

.Thus,forallt,t

≤

t

≤

t0,

σ

,

t

|= φ

1.Moreover, there exists t, t0

<

t

≤

t,

σ

,

t

|= φ

2, v

(

t

)

−

v

(

t0

)

<

M

(

p

)

, and for all t, t0

≤

t

<

t,

σ

,

t

|= ¬φ

2. Thus,

σ

,

t0

|=

˜

X

φ

1U

φ

2

∧

time@F

˜

(φ

2

)

−

time

<

p.Thus,

σ

,

t

|= φ

1U

( ˜

X

φ

1U

φ

2

∧

time@F

˜

(φ

2

)

−

time

<

p

)

.

•

Case

φ

1U( ˜Xφ1Uφ2

∧

time@F(φ

˜

2

)

−

time

<

p)

|=

G

φ

1U(0,p)

φ

2.

If

σ

,

t

|= φ

1U

( ˜

X

φ

1U

φ

2

∧

time@F

˜

(φ

2

)

−

time

<

p

)

,thenthereexistst,t

≤

t,

σ

,

t

|= ˜

X

φ

1U

φ

2

∧

time@F

˜

(φ

2

)

−

time

<

p

)

andforallt,t

≤

t

<

t,

σ

,

t

|= φ

1.Thus,thereexistst

>

t,suchthat

σ

,

t

|= φ

2,0

<

v

(

t

)

−

v

(

t

)

<

M

(

p

)

,andforall

t,t

<

t

<

t,

σ

,

t

|= φ

1.Thus

σ

,

t

|= φ

1U(0,p)

φ

2.

Equivalence(7)

•

Case

φ

1U(0,p]

φ

2

|=

G

φ

1U(( ˜Xφ1Uφ2

)

∧ ((( ˜

X

¬φ

2Uφ2

)

∧ (

time@F(φ

˜

2

)

−

time

≤

p))

∨ (( ˜

X

¬φ

2UXφ

˜

2

)

∧ (

time@F(φ

˜

2

)

−

time

<

p)))).

If

σ

,

t

|= φ

1U(0,p]

φ

2 then thereexists t

>

t such that 0

<

v

(

t

)

−

v

(

t

)

≤

M

(

p

)

,

σ

,

t

|= φ

2, andforall t,t

≤

t

<

t,

σ

,

t

|= φ

1.Lett0bethegreatestpointsuchthatt

≤

t0andv

(

t

)

=

v

(

t0

)

.Thus,forallt,t

≤

t

≤

t0,

σ

,

t

|= φ

1.Moreover,

σ

,

t0

|= ˜

X

φ

1U

φ

2. Thus, either

σ

,

t0

|= ˜

X

¬φ

2U

φ

2 or

σ

,

t0

|= ˜

X

¬φ

2UX

˜

φ

2. In the first case, there exists t, t0

<

t

≤

t,

σ

,

t

|= φ

2,andforallt,t0

≤

t

<

t,

σ

,

t

|= ¬φ

2.Sincet

≤

t,

σ

,

t0

|=

time@F

˜

(φ

2

)

−

time

≤

p.Similarly,inthesecond case,thereexistst,t0

<

t

≤

t,

σ

,

t

|= ˜

X

φ

2,andforallt,t0

≤

t

<

t,

σ

,

t

|= ¬φ

2.Sincet

≤

t,

σ

,

t0

|=

time@F

˜

(φ

2

)

−