Contents lists available atScienceDirect
Science
of
Computer
Programming
www.elsevier.com/locate/scico
Adaptability
checking
in
complex
systems
Emanuela Merelli
a,∗
, Nicola Paoletti
b, Luca Tesei
aaSchoolofScienceandTechnology,ComputerScienceDivision,UniversityofCamerino,Via delBastione 1,62032,Camerino,Italy bDepartmentofComputerScience,UniversityofOxford,ParksRoad,OX1 3QD,Oxford,UK
a
r
t
i
c
l
e
i
n
f
o
a
b
s
t
r
a
c
t
Articlehistory:
Received17February2013
Receivedinrevisedform16December2014 Accepted26March2015
Availableonline1April2015 Keywords: Adaptivesystems Statemachine Adaptabilityrelations Adaptabilitychecking S[B]model
A hierarchical approach for modelling the adaptability features of complex systems is introduced. It is based on a structural level S, describing the adaptation dynamics of the system, and a behavioural level B accounting for thedescription ofthe admissible dynamicsofthesystem.Moreover,aunifiedsystem,called S[B],isdefinedbycouplingS and B.Theadaptation semanticsissuchthat the S level imposesstructural constraints on the B level, which has to adapt whenever it no longer can satisfy them. In this context,weintroduceweakand strong adaptability,i.e.theability ofasystemtoadapt forsomeevolutionpathsorforallpossibleevolutions,respectively.Weprovidearelational characterisationforthesetwonotionsandweshowthatadaptabilitychecking,i.e.deciding if a system is weakly orstrongly adaptable, can be reduced to aCTL model checking problem. Weapply themodel and thetheoretical resultstothe casestudyofamotion controllerofautonomoustransportvehicles.
©2015TheAuthors.PublishedbyElsevierB.V.Thisisanopenaccessarticleunderthe CCBY-NC-NDlicense(http://creativecommons.org/licenses/by-nc-nd/4.0/).
1. Introduction
Self-adaptivesystemsareparticularsystemsabletomodifytheirownbehaviouraccordingtotheircurrentconfiguration andtheperceptionoftheenvironment inwhichtheyoperate.Theydevelopnewstrategiesinordertofulfilan objective, properlyrespondtochangesoftheenvironmentalconditionsor,moregenerally,maintaindesiredconditions.
Fromabroadviewpoint,self-adaptivenessisanintrinsicpropertyofcomplexnaturalsystems.Self-adaptationisaprocess drivingboth theevolutionandthe developmentoflivingorganismsthatadapttheir featuresandchangetheirphenotype inorder tosurvive to thecurrenthabitat, toachieve higher levelsof fitnessandto appropriately react to external stim-uli.
Nowadays, software systems are increasingly resembling complex systems; thismotivates the development of meth-ods forenabling softwareself-adaptiveness.Similarly to naturalsystems,“Self-adaptive software evaluates its own behaviour and changes behaviour when the evaluation indicates that it is not accomplishing what the software is intended to do, or when bet-ter functionality or performance is possible”[35].Self-adaptivesoftwarefindsapplicationinfieldslikeautonomiccomputing, service-oriented architectures,pervasive service ecosystems,mobile networks, multi-agent systems, and ultra-large-scale softwaresystems[25],characterisedby distributed,autonomous,interacting,heterogeneous,conflictingandevolvable sub-systems.
Inthiswork, wedevelop aformal hierarchicalmodelforself-adaptivesystems,wheretwo fundamental levelsare de-fined:the
behavioural level B,
whichdescribestheadmissibledynamicsofthesystem;andthestructural level S,
accounting*
Correspondingauthor.E-mailaddresses:emanuela.merelli@unicam.it(E. Merelli),nicola.paoletti@cs.ox.ac.uk(N. Paoletti),luca.tesei@unicam.it(L. Tesei). http://dx.doi.org/10.1016/j.scico.2015.03.004
0167-6423/©2015TheAuthors.PublishedbyElsevierB.V.ThisisanopenaccessarticleundertheCCBY-NC-NDlicense (http://creativecommons.org/licenses/by-nc-nd/4.0/).
fortheinvariantfeaturesofthesystemthatregulatethebehaviourofthesystem.Moreprecisely,bothlevelsaremodelled asstatemachines, buteachstate ofthe S level isassociatedwitha setof
constraints,
i.e.logicalformulasoverobservable variablesofthe B level.An
S state
inthestructurallevelrepresentsarelativelypersistentsituation,asteadyregionfortheB level,
identifiedby thesetof B states satisfyingtheconstraints.Therefore S is ahigher order structure whose
statescanbeinterpretedassets of B states, andwhosetransitionscanbeviewedasmappingsamongsetsof B states. Thecoupledmodelwillbereferred toasS
[
B]
,inordertohighlightthetwobasiclevelsthatcomposethesystem.The S
[
B]
modelis broadlyinspired bya previous work ofsome ofthe authors,a spatial bio-inspired processalgebra calledShape
Calculus[3,4],whereprocessesarecharacterisedbyareactivebehaviour B and byashapeS that
imposesaset ofgeometricalconstraintsontheirinteractionsandoccupancyinthethree-dimensionalEuclideanspace.Here,instead,the computationalapproachisshiftedinamoregeneralcontext,where S and B are coupledbyahierarchicalrelationdefined onthestructuralconstraintsofthe S level andthestatespaceofthe B level.The adaptationsemanticscan bebriefly described asfollows.Consider an S
[
B]
system, letq be
thecurrentstateof Band assumethat it satisfiesthe constraintsofthe current S state. The adaptation istriggered whenever
q cannot
evolve because thereis nonext B state that satisfiesthe current S constraints. Duringadaptation, the S[
B]
systemattempts to evolve towardsa newB state thatsatisfiesa new S state, chosen amongthesuccessorsofthecurrentone. InthisphaseB is nomoreconstrainedby S. Adaptationterminatessuccessfullywhen B ends upin astate thatfulfils thenewglobal situationrepresentedbyoneoftheadmissible S states.
Afirstgeneralintroductionofthe
S
[
B]
modelwasgivenin[38]and[39]bytheauthors.Inthiswork,weprovideseveral noveltiesandimprovements,mostofthem devotedtotheadaptability checking problem,
i.e.theautomatic checkingofthe adaptationcapabilitiesofagivenS
[
B]
system.Inparticular,wedefinethenotionofweak adaptability,
possessedbyanS
[
B]
systemthatisabletoadaptalongsomeofallitspossibleevolutionpaths.
Strong adaptability requires
thattheS
[
B]
system isabletoadaptalongallitspossibleevolutionpaths.Weformulatethenotionsofweakandstrongadaptabilityasrelations betweenthestatesofB and S and
alsoinlogicalform,asComputationTreeLogic(CTL)formulasoverthegivensemantics ofanS
[
B]
system.Then,weformallyprovetheequivalencebetweentherelationalandthelogicalformulationofstrongand weakadaptability(Theorems 1 and 2),showingthattheadaptabilitycheckingproblemcanbereducedtoaclassicalmodel checkingproblem. Wealsodiscussthecomputationalcomplexity ofourapproach.Theeffectivenessofthe S[
B]
approach for self-adaptivesystems is demonstratedusing acase studyinthe context ofadaptive softwaresystems, a modelfora motion controllerofautonomoustransport vehicles inasmart airport.The samecasestudyisusedforexemplifying the notionsofweakandstrongadaptabilityandtheadaptabilitycheckingproblem.The paper is organised as follows. Section 2 introduces the formalism and the syntax of the S
[
B]
model. Section 3illustrates theapplicationofthemodeltotheexampleofadaptivemotioncontroller.InSection4we givetheoperational semantics of an S
[
B]
systemby means ofa flattened transitionsystem. In Section 5 we formalisetherelations of weak andstrongadaptation,whichweequivalentlycharacteriseasCTLformulasinSection6.Relatedworksincludingadaptation featuresof S[
B]
,andconclusionsaregiveninSection7.Finally,proofsarepresentedinAppendix A.2. Aformalhierarchicalmodelforadaptivesystems
Inthe S
[
B]
approach,amodelencapsulatesboththebehavioural(B)andthestructural(S)levelofanadaptivesystem. The behavioural level is classically described as a finite state machine of the form B= (
Q,
q0,
→B
)
where Q is a setof B states, q0 initial B state and
→B
transition relation.The structurallevel ismodelled asa finite state machine S=
(
R,
r0,
O,
→S
,
L)
where R is a set of S states, r0 is theinitial S state,O
isan observation function,→S
isa transitionrelationand
L is
astatelabellingfunction.ThefunctionL labels
eachS state
withaformularepresentingasetofconstraints over anobservation of
the B states. Thereforean S state r can bedirectly mapped tothe setof B states satisfying L(
r)
. Through thismapping, S can beviewedasasecond-order structure
S= (
R⊆
2Q,
r0,
O,
→S
⊆
R×
R)
whereeach S state risidentifiedwithitscorrespondingsetof
B states.
An S[
B]
systemistheresultofcouplingthetwolevelsS and B through
the observation function
O
andan evaluationfunction[[·]]
, that maps each S state to the set of B states meeting the constraints.The S
[
B]
adaptation is achievedby switchingfroman S state to another S state where a differentsetof constraints holds. During adaptationthe B machine is no moreregulated by the structurallevel,except foran adaptation invariant, calledadaptation invariant,
thatmustbefulfilledbythesystemwhileadapting.Thesystemadaptsbyfollowinganytrajectory thatispresentatthe B level thatdoesnotviolatetheinvariantcondition,whichcanbeusedasasafetyconditionifsome activitiesoftheB level
mustbeavoidedduringadaptation.Inordertorealiseournotionof S
[
B]
adaptiveness,theremustbesomeinformationflowingbothfromB to S and vice versa. Inparticular,theinformationfrom B to S is modelled hereasa setofvariables A= {
a1,
. . . ,
an}calledobservables
of the S on the B level. Thevaluesof thesevariablesmustalways be
derivable from
theinformationcontainedin the Bstates.Thismakesourapproachblack-box-oriented,thatistosay,
S has
notthefullknowledgeofB,
butonlysomederived information.Fig. 1. AdaptationloopinanS[B]system.Ateachstep,S observesB anddecideifthereisaneedtochangestate.Theloopcloseswiththeselectionof eligiblenextstatesB ofB,i.e.thosethatsatisfythecurrentconstraintsorthosethatsatisfythecurrentadaptationinvariant.
Incontrol-theoreticterms,asillustratedinFig. 1,theadaptationmodelofan
S
[
B]
systemcanbeviewedasaclosed-loop systemwhere B is theplantand S is the controller.Letq and
r be thecurrentstatesof B and S. B outputs thevector1B
=
Post(
q)
ofthe statesreachablefromq with
a single transition,i.e.an elementq
i of B issuch thatq
→B
qi andeachstate is unique:
i=jqi=
qj.Since S can only observesome features of B states, the observerO
will provide S with avectorofobservationsmadeoverthevaluesofthevariablescharacterising eachstateinB:o
=
iO(
qi)
.S will checktheobservablesprovidedbyo withrespecttoitscurrentstate
r.
Ifitsconstraintsaresatisfied,S will
remain inthesamestateandS[
B]
willproceedinsteady mode.
Otherwise,S will
performatransitiontoanewr state
forcingtheS
[
B]
systemtoenteranadaptation mode.
Hereweassumethattheupdatedr is
computedwithafunctionCheck that
takes thecurrentS state andobservations.ThefeedbackloopcloseswiththeselectionoftheeligiblenextstatesB outputtedtoB, i.e.thosestatesthatsatisfythecurrentconstraintsof
r or
thosethat satisfythecurrentadaptationinvariant. ThesetBisobtainedbyapplyingtheevaluationfunction
[[·]]
toeithertheconstraintsofr or
theinvariant. Intheadaptationmode the outputis calculatedusing thewhole B machine without constraintsexceptthe adaptationinvariant, to make B freetoexplore thestatespace. Inturn, B updates its currentstate
q by
selectingone oftheeligiblestatesprovidedinB.The conceptsofobservationfunctionO
andevaluationfunction[[·]]
areformalised inDefinition 1andDefinition 2.2.1. Language for constraints
Theconstraints characterisingthe statesofan S level are expressedusingformulas ofamany-sorted firstorderlogic. Moreprecisely,thedefinitionofan
S level
includesthedefinitionofamany-sortedsignaturecontainingsomefunction symbols,somepredicatesymbolsandsomesortsD1
,
. . . ,
D
k.-termsand
-formulasareconstructedinthestandardway [24].Inaddition,a particularset ofsortedvariables, whichwe callobservables, mustbe fixed. Sucha setis oftheform
A
= {
a1:D
j1,
. . . ,
an:Djn}
,where ji∈ {
1,
. . . ,
k}
foralli
=
1,
. . . ,
n. Then,constraintscanbeexpressedas-formulas
ψ
such thatthevariablesthatoccurfreeinψ
,denotedbyfree(ψ)
,area(possiblyempty)subsetofA. Thissetwillbedenotedby(,
A
)
= {ψ | ψ
is a-formula
∧
free(ψ)
⊆
A}
.We also impose that a particular structure M is fixed for the evaluation of
-formulas. M consists ofk non-empty
domains M
(
D1),
. . . ,
M
(
Dk)
, ascarriersets forsorts,together withinterpretations forall function andpredicatesymbolsof
.Toobtainthefullsemanticevaluationofformulasin
(,
A
)
wewilltakethevaluesforthefreevariablesinA from
anobservationfunction.
Definition1
(Observation function).
LetQ
betheuniversesetofallstatesofmachinespossiblyrepresenting B levels. Letbeamany-sortedsignature,let A
= {
a1:D
j1,
. . . ,
an:Djn}
beasetofobservablesandletM be
astructurefortheevaluation of-formulas.An
observation function
O
,AM on
,A and M is apartialfunction
O
,AM :
Q
→ (
A→
D
)
where(i)
D =
n
i=1M(
Dji)
and(ii)foranystateq
∈
Q
,ifO
,MA(
q)
=⊥
thenO
,A
M
(
q)(
ai:D
ji)
∈
M(
Dji)
,foralli
=
1,
. . . ,
n.Foralighternotation,wewilluse
O
insteadofO
,MAwhen,
A and M are
clearfromthecontext.Notethattheuseoftheuniverseofstatesasdomainmakesthedefinitionoftheobservationfunctionindependentfrom aparticularstate machinerepresentingabehaviourallevel B. Notealsothatwedonotrequiretheobservationfunctionto beinjective.Thismeansthatsomedifferentstatescangivethesamevaluestotheobservables.Inthiscase,thedifference amongthestatesisnotvisibleto S through theobservation,butitisinternalto B.
Tocompletethemachineryforcheckingwhetherasetofconstraintsissatisfiedornot,wedefinethesatisfactionrelation inthenaturalway.
Definition2
(Satisfaction
relation). LetO
,MAbeanobservationfunction.Astateq
∈
Q
satisfies a formulaψ
∈ (,
A
)
, writ-tenq
| ψ
,iffO
,MA(
q)
=⊥
andψ
istrue,accordingtothestandardsemanticsofmany-sortedfirstorderlogic,withrespect tothestructureM and
bysubstitutinginψ
everyoccurrenceofthefreesortedvariablea
i:Dji withO
,MA(
q)(
ai:D
ji)
.Wealsodefineanevaluationfunction
[[·]]
: (,
A
)
→
2Qmappingaformulaψ
∈ (,
A
)
tothesetofstates[[ψ]]
=
{
q∈
Q
|
q| ψ}
,i.e.thosesatisfyingψ
.A setofconstraintsisformally expressedbya formula
ψ
∈ (,
A
)
thatis theconjunctionofalltheformulas repre-sentingeachconstraintintheset.Thesetofconstraintsissatisfiedifandonlyifthecorrespondingformulaistrueinthe fixedstructure M and observationO
,MA.Example1.Letusconsiderasetofobservablesandassociatedsorts:
A
= {
velocity: R,
congestion: B}
Consider alsoasignature
= {R,
B,
==,
>,
<,
0,
5}
whereR
andB
are thesortsindicatingthedomainsofrealnumbers andboolean,respectively;==
isthe equalitypredicateinterpreted asthe identityrelationineach domain;>
and<
are theusualgreater-thanandless-thanpredicatesoverR
;andtheconstants0 and5 aretherealnumbers0 and5.Apossible formulaψ
inthelanguage(,
A
)
iscongestion
⇒
velocity<
5∧ ¬
congestion⇒
velocity>
0whosesatisfactiondependsontheparticularvaluesofthevariables,whichwillbedifferentindifferentstates.
InthecontextofAutonomousTransportVehicles(seeSection 3),thisformulacanbethoughttorepresentasetoftwo constraints,oneimposingthat“incaseofcongestion, thevelocityofthevehiclemustbelowerthan5”andtheotherthat “innormaltrafficconditions,thevelocitymustbegreaterthan 0”.
2.2. Coupling S and B
Letusnowformally definethebehaviourallevel B and thestructurallevel S separately. Afterwards,the S
[
B]
modelis definedasthecombinationofthetwo.Definition3
(Behavioural level).
ThebehaviourallevelofasystemisatupleB
= (
Q,
q0,
→B
)
,where•
Q⊆
Q
isafinite set
ofstatesandq
0∈
Q is theinitialstate;and• →B⊆
Q×
Q is thetransitionrelation.Definition4
(Structural level).
ThestructurallevelofasystemisatupleS= (
R,
r0,
O
,MA,
→S
,
L
)
,where•
R is afinitesetofstatesandr
0∈
R is theinitialstate;•
O
,AM isanobservationfunctiononasignature
,asetofobservablesA and astructure
M;
• →S
⊆
R× (,
A
)
×
R is afinitetransitionrelation,labelledwithaformulacalledinvariant;
and•
L:
R→ (,
A
)
isafunctionlabellingeachstatewithaformularepresentinga set of constraints.
Letusnowgiveanintuitionoftheadaptationsemantics.Letthecurrent
S state
ber
iandsupposer
iψ
−→S
rjforsome rj.Assumethatthebehaviourisinasteadystate(i.e.notadapting)
q
iandthereforeq
i|
L(
ri)
.IftheB state
canmove,butall B transitions qi→B
qjaresuchthatq
j|
L(
ri)
,thenthesystemcanstartadaptingtothetargetS state r
j.Inthisphase,the B level isnomoreconstrained, butduring adaptationtheinvariantψ
mustbemet.Adaptationendswhenthebehaviour reachesastateq
ksuchthatq
k|
L(
rj)
.Wewanttoremarkthatthemodelsupportsthenon-deterministicchoicebetweenadaptations,i.e.thesystemcanadapt to everytarget state
r
j reachablewithatransitionr
iψ
−→S
rj fromthecurrentr
i state.The non-determinismcanbe bothexternal—thatisdifferenttargetstatescanbereachedbysatisfyingdifferentinvariants—andinternal—thatisdifferenttarget statescanbereachedsatisfyingthesameinvariantcondition.
Definition5
(S
[
B]
system). AnS
[
B]
system is thecombinationofabehaviourallevel B= (
Q,
q0,
→B
)
andastructurallevelS
= (
R,
r0,
O
,MA,
→S
,
L)
suchthatforallq
∈
Q ,O
,A
M
(
q)
=⊥
.Moreover,inanyS[
B]
systemtheinitialB state
mustsatisfyFig. 2. Aschemaofstatesandtransitionsstartingfromagenericstate(r,v,c,0,0).Weletr=r.Moreover,thetransitionstowardsthestates(r,v+ 1,c,0,0)or(r,v+1,¬c,0,0)arenotpresentwheneverv=2,whilethetransitionstowardsthestates (r,v−1,c,0,0)or(r,v+1,¬c,0,0)arenot presentwheneverv=0.
3. Casestudy:adaptivemotioncontrollerofAutonomousTransportVehicles
In thissection, we illustrate the features of our approach by means ofan exampleadapted from[29]: a model ofa motioncontrollerof
Autonomous Transport Vehicles (ATVs) in
asmartairport.ATVs are responsible forthe transport of passengers betweenstopovers likepassenger entrances, check-in desks, de-parturegates,andplane parkingpositions.Intheairportthereare twotypesofroadsthattheATVscan use:mainroads andsecondary roads,the latteronesusedduring traffic peaks.ATVscan travel atdifferentspeed inanyroad,preferably not atthemaximumspeed onsecondary roads,asthey arenarrowerthan themain ones.Forsimplicity,we modelonly thesubcomponentofATVsthatcontrolsthevehiclespeedandtheswitchingbetweenmainandsecondaryroads.The S
[
B]
approachwill beused tospecifyandimplementtheadaptation featuresof thiscontrollerincaseoftraffic congestionor blockages.
3.1. Behavioural level
ThebehaviouralleveldescribesallthecapabilitiesoftheATVcontroller,i.e.alltheactionsthatthesystemisabletodo inanunconstrainedscenario.Wesuppose thateachATVcontrollerhasthepossibilitytoperceivethecurrentsituationof trafficcongestionorblockagebyusingasensororbycommunicatingwithaglobalmonitoringsystemsoftheairport.The ATVcontrollermay,basedonthisperception,decidewhichactiontoexecute.
The usual wayof abstractly specifying a behaviour ofthis kind is a two-phase cycle: in the first phase there is the
perception of theglobalenvironment,onlyrelativelytothecurrentcongestionsituation;inthesecondphase,alocal
action
canbeexecuted,correspondingtochangeeitherthevehiclevelocityortheroadtodrive.
Toformalisethebehaviourallevel B we considerthefollowingsetofobservablevariablesandassociatedsorts:
•
r: {
M (main),
S (secondary)
}
,thecurrentroad;•
v: {
0 (slow),
1 (medium),
2 (high)}
,thecurrentvelocityofthevehicle;•
c: {
true (congestion),
false (no congestion)}
,abooleanvariableindicating thecurrentknowledgeoftheATVcontroller aboutthetrafficcongestion;•
p: {
true (perception),
false (no perception)}
,abooleanvariableindicatingwhetherornottheATVcontrolleriscurrently perceivingthecongestionsituation,i.e.itisinthefirstphaseofitscycle;and•
a: {
true (action),
false (no action)}
,abooleanvariableindicatingwhetherornottheATVcontrolleriscurrentlyexecuting anaction,i.e.itisinthesecondphaseofitscycle.Hereafter,each state
q of
the B level willbe identifiedbythevaluesoftheobservables,q
= (
r,
v,
c,
p,
a)
.Wewill denote thebooleanvaluetrue with
theinteger1 andthebooleanvaluefalse with
theinteger0.Fig. 2 contains a schemarepresentingthe portionof thestate machine, corresponding tothe B level, starting froma genericstate
(
r,
v
,
c,
0,
0)
,i.e.astate inwhichthecontrollerisatthebeginningofoneiterationofits cycle.Thetwo out-goingtransitionsnon-deterministicallymodeltheperceptionofthesamecongestionsituationknownatthelastperception (state(
r,
v,
c,
1,
0)
)orofthe new(negated)situation(state(
r,
v
,
¬
c,
1,
0)
).Inanycase, thesystemproceedsto theaction phase (states(
r,
v
,
c,
0,
1)
or(
r,
v,
¬
c,
0,
1)
) where it can decide to changeroad or to change velocity ending up in an updatedstate,readytostartanotherperception–actioniteration.Fig. 3. Twopossiblestructurallevels,S0(a)andS1(b),forthemotioncontrollerexample.Theymodeltheadaptationlogicbetweentwomodesofoperation,
r0(normal,blue)andr1(fallback,red).(Forinterpretationofthereferencestocolourinthisfigurelegend,thereaderisreferredtothewebversionofthis
article.)
3.2. Structural level
The structurallevel can be used to give an abstract,constraint-based, specification of thepossible ways (the various statesin S) inwhichthesystemcanfunctiontogetherwiththeadmissibleadaptations amongthem(thetransitionsinS).
Inthiscasestudyweshowhowtoimplement,asan S
[
B]
system,apolicyofthesmartairportthatrequirestheadaptation ofthe behavioursofthe vehiclesduring theirfunctioning. Weassume thatsome oftheATVsintheairport areequipped withadaptabilitycapabilitiesinordertoimplement, asan example,thefollowingpolicy:“wheneverthere is congestion, the
adaptive ATV will have to switch as soon as possible to a secondary road and to limit the velocity to the maximum value 1; on the contrary, whenever there is not congestion, the adaptive ATV will have to use a main road at any velocity”.ThispolicyclearlyidentifiestwomodesofoperationsoftheadaptiveATVs,whichareactivatedbydifferent environmen-talconditions:
•
a normal mode of operation, occurring when there is no traffic congestion and such that the main road is driven (r==
M); and•
afallbackmode,occurringwhencongestionoccurs;inthiscasetheATVhastobeinthesecondaryroad(r==
S) and itcannotdriveatthemaximumvelocity(v iseither0 or1).These twomodesare modelledby twodifferent S states, asshowninFig. 3(a).The constraintcharacterising thenormal mode(state
r
0)isthedisjunctionofthedescriptionofthemode(¬
c∧
r==
M) withthepossibilityfortheATVcontrollerto perceive theoccurrence ofa congestionwhenin themode (c
∧
r==
M∧
p). Notethat without thelatter disjunctive termit wouldnotbe possibleforthesystemto perceivethe differentvalueofthe variablec because
thatwouldviolate the constraintdescribing the mode (¬
c∧
r==
M), puttingthe perception state out ofthe normalmode. Thisaccording to the semantics of S[
B]
(see Section 4). The fallback mode (state r1) is also described, for the same reasons, by thedisjunction ofthe mode description (c
∧
r==
S∧
v<
2) andthe possibilityfor thesystem toperceive¬
c when in the mode(¬
c∧
r==
S∧
v<
2∧
p).Theinvariantconditionsonthetransitionsbetween
r
0andr
1areneededtoavoidtheperceptionofavalueofc different
fromthatofthemodetowhichthesystemisadaptingto.Forinstance,whenadaptingfrom
r
0tor
1thetargetsteadystateisoneinwhichthereiscongestion. Duringtheadaptationweneedtoensurethat,wheneverthereisperception,onlythe value
c can
be perceived,rulingouttheother possibility(duetonon-determinism)ofperceiving¬
c. Thisisexpressedby theinvariant(
p∧
c)
∨¬
p that, infact,correspondstoforcingtheS
[
B]
systemtoignorepossiblechangesintheenvironment during adaptation.Withouttheseinvariants(seeFig. 3(b)),thesystemcouldfallina livelockduring theadaptationphase, asitisshowninSection5.1.Fig. 4 shows thefull B level where theblue boxencloses thestates satisfyingtheconstraints of
r
0,andthe red boxthosesatisfyingtheconstraintsof
r
1.4. OperationalsemanticsoftheflatS
[
B]
systemWe give the operational semantics of an S
[
B]
system asa transition systemresulting from the flattening of the be-haviouralandthestructurallevels.WeobtainaLabelledTransitionSystem(LTS)overstatesoftheform(
q,
r,
ρ
)
,where:•
q∈
Q and r∈
R are theactiveB state
and S state, respectively;and•
ρ
keepsthetarget S state thatmustbereachedduringadaptationandtheinvariantthatmustbefulfilledduringthis phase. Thereforeρ
iseitherempty (noadaptation isoccurring),ora singleton{(ψ,
r)
}
,withψ
∈ (,
A
)
aformula andr
∈
R an S state.Definition6
(Flat S
[
B]
system). Consideran S[
B]
system.ThecorrespondingflatS
[
B]
systemistheLTSF(
S[
B])
= (
F,
f
0,
−→
r∪
r,ψ,rFig. 4. Thebehaviouralstatemachinefor themotioncontrolexample.Eachstateislabelledwiththedifferent evaluationoftheobservable variables
(r,v,c,p,a),i.e.(road,velocity,congestion,perception,action).ColouredareasareusedtorepresentthestatesoftheS levelsofFig. 3(a)and 3(b),which identifystableregionsintheB level.Thesearer0(normalmode,bluebox)andr1(fallback/congestionmode,redbox).(Forinterpretationofthereferences
tocolourinthisfigurelegend,thereaderisreferredtothewebversionofthisarticle.)
•
F=
Q×
R× ({(ψ,
r)
| ∃
r∈
R.
r
−→S
ψ r}
∪ {∅})
isthesetofstates;•
f0= (
q0,
r0,
∅)
istheinitialstate;•
−→⊆
rF
×
F , withr
∈
R, isafamilyoftransitionrelationsbetweennon-adaptingstates,i.e.,bothsatisfyingL
(
r)
;•
r,ψ,r−−−−→⊆
F×
F , withr
,
r∈
R andψ
∈ (,
A
)
,isafamilyoftransitionrelations betweenadapting states,wherethe adaptationisdeterminedbythe S transition r−→S
ψ r;and•
thepairsin−→
r andin−−−−→
r,ψ,r areallandonlythosederivableusingtherulesinTable 1. LetusdiscusstheruleslistedinTable 1characterisingtheflattenedtransitionalsemantics:•
Rule Steady describesthe steady(i.e. non-adapting)behaviour of thesystem. Ifthe systemisnot adapting anda Bstate
q can
performa transitionto aq
thatsatisfiesthecurrentconstraints L(
r)
,thentheflat systemcan performa non-adaptingtransition−→
r oftheform(
q,
r,
∅)
−→ (
r q,
r,
∅)
.•
Rule AdaptStart regulatesthestartingofanadaptationphase.Adaptationoccurswhen allof thenext B states do notsatisfy the current S state constraints—i.e.
∀
q.(
q→B
q⇒
q|
L(
r))
—andtheB machine
isnotitselfdeadlocked(q→B
q).Inthiscase,foreachS transition r
−→S
ψ ran adapta-tiontowardsthetargetstater
,undertheinvariantψ
,canstart.Theflatsystemperformsanadaptingtransition−−−−→
r,ψ,r oftheform(
q,
r,
∅)
−−−−→ (
r,ψ,r q,
r,
{(ψ,
r)
})
.•
Rule Adapt can be usedonly during an adaptation phase.It handles the casein which,after thecurrent transition, the systemkeepsadapting because a steadyconfiguration cannot be reached(∀
q.(
q→B
q⇒
q|
L(
r))
). In this situation,sincethesystemstill mustadapt(q|
L(
r)
),ifthe B machine isnotdeadlockedandtheinvariantcan still be satisfied(q→B
q andq| ψ
),the ruleallows atransitionofthe form(
q,
r,
{(ψ,
r)
})
−−−−→ (
r,ψ,r q,
r,
{(ψ,
r)
})
. Note thatduringadaptationthebehaviourisnotregulatedbytheS states
constraints.Notealsothatthesemanticsdoesnot assurethatastate wherethetarget S state constraintsholdiseventually reached.Twodifferentformulationsofsuch adaptabilityrequirementsaregiveninSection5.Table 1
OperationalsemanticsoftheflatS[B]system.
Steady q| L(r) q→Bq q| L(r) (q,r,∅)−→ (r q,r,∅) AdaptStart ∀q.(q→Bq ⇒q| L(r)) q| L(r) q→Bq r ψ −→Sr q| L(r) q| ψ (q,r,∅)−−−−→ (r,ψ,r q,r,{(ψ,r)}) Adapt ∀q.(q→Bq ⇒q| L(r)) q| ψ q| L(r) q→Bq q| ψ (q,r,{(ψ,r)})−−−−→ (r,ψ,r q,r,{(ψ,r)}) AdaptEnd q| ψ q| L(r) q→Bq q| L(r) (q,r,{(ψ,r)})−−−−→ (r,ψ,r q,r,∅) AdaptStartEnd ∀q.(q→Bq ⇒q| L(r)) q| L(r) q→Bq r ψ −→Sr q| L(r) (q,r,∅)−−−−→ (r,ψ,r q,r,∅)
•
Alsorule AdaptEnd canonlybeappliedduringanadaptationphaseandithandlesthecaseinwhich,afterthecurrent transition, theadaptationmustendbecauseasteadyconfigurationhasbeenreached(q|
L(
r)
).Itallowsatransitionr,ψ,r
−−−−→
fromanadaptingstate(
q,
r,
{(ψ,
r)
})
tothesteady(non-adapting)state(
q,
r,
∅)
.•
Rule AdaptStartEnd handles the special case in which an adaptation phase must start from a steady situation—∀
q.(
q→B
q⇒
q|
L(
r)
—but then, after just one move of the B level, another steady region of the S level is reached(q|
L(
r)
).Inthiscasetheinvariantψ
associatedtothe S transition isignoredandthesystemgoesdirectly intoanothersteadystate.Notethatthisruleisalternativetotherule AdaptStart inwhichtheinitialsituationisthe same, but the steady region is not reached after one B transition. The flat system performs an adapting transitionr,ψ,r
−−−−→
oftheform(
q,
r,
∅)
−−−−→ (
r,ψ,r q,
r,
∅)
.Therefore,asuccessfuladaptationoccurswhenrules AdaptEnd or AdaptStartEnd canbeapplied,i.e.whenatransition fromanadaptingtoasteadystateisfired.
Letusnowstatesome propertiesofthegivenflatsemantics.Inthefollowing,givenanytransitionrelation
→
andany states,
bys
→
andby s we mean,asusual, thatthereexistsa state s suchthat s→
s andthat thereexistsnostates suchthat
s
→
s, respectively.Moreover, by→
+ we indicateafinite,non-empty,sequence of→
steps;moreformally, there existsn
∈ N,
n>
0 suchthat s=
s0→
s1→ · · ·
sn−1→
sn. Finally,by→
k,k
≥
0,we indicatek consecutive
steps oftherelation
→
:s
=
s0→
s1→ · · ·
sk−1→
sk.Ifk
=
0,thens
→
0sisequivalenttosaythatthereistheemptysequenceofsteps
s,
andthuss
=
s. Thisisalwayspossible,eveniftherelation→
isnotreflexive.Proposition1
(Properties of flat semantics). Let
F(
S[
B])
= (
F,
f
0,
−
→ ∪
rr,ψ,r
−−−→)
be a flat S[
B]
system. All the following statements hold:(i) If
a steady transition can be performed, then adaptation cannot start:
∀(
q,
r,
∅)
∈
F.
(
q,
r,
∅)
→ (
−
r q,
r,
∅)
⇒ (
q,
r,
∅)
−−−→
r,ψ,r (ii) Ifadaptation can start, then no steady transition is possible:
∀(
q,
r,
∅)
∈
F.
(
q,
r,
∅)
−−−→ (
r,ψ,r q,
r,
{(ψ,
r)
})
⇒ (
q,
r,
∅)
−
→
r (iii) Duringadaptation no steady transition is possible:
∀(
q,
r,
{(ψ,
r)
})
∈
F.
(
q,
r,
{(ψ,
r)
})
−
→
r(iv) The
non-adapting and the adapting transition relations are disjoint:
∀
r,
r∈
R,
∀ψ ∈ (,
A
).
−
→ ∩
r−−−→= ∅
r,ψ,r(v) In
case of a successful adaptation, the adaptation phase ends as soon as possible, i.e. as soon as the target steady state can be
reached with a single transition.(vi) Given
any q
∈
Q and r∈
R, then every infinite path πinF(
S[
B])
starting in a state(
q,
r,
∅)
such that q|
L(
r)
is of one of the following kinds:(1) adaptation always succeeds; the path alternates between steady transitions and adaptation paths:
π
= (
q=
q0,
r=
r0,
∅)(
r0−→)
m0(
−−−−−→)
r0,ψ0,r1 n0· · ·
· · · (
qi,
ri,
∅)(
ri−
→)
mi(
−−−−−→)
ri,ψi,ri+1 ni(
q i+1,
ri+1,
∅) · · ·
(2) adaptation lasts forever; the path has a prefix in which steady transitions and adaptation paths alternate, but then one adaptation path never stops:
π
= (
q=
q0,
r=
r0,
∅)(
r0−→)
m0(
−−−−−→)
r0,ψ0,r1 n0· · ·
· · · (
qi,
ri,
∅)(
ri−
→)
mi(
ri,ψi,ri+1−−−−−→)
ni(
q i+1,
ri+1,
∅) · · ·
· · · (
qk,
rk,
∅)
rk,ψk,rk+1−−−−−−→ (
qk+1,
rk,
{ψ
k,
rk+1})
rk,ψk,rk+1−−−−−−→ (
qk+2,
rk,
{ψ
k,
rk+1})
rk,ψk,rk+1−−−−−−→ · · ·
where k
≥
0 andfor each i,
0≤
i<
k, either mi=
1∧
ni=
0 orm
i=
0∧
ni>
0.(vii) Let
π
∈
F(
S[
B])
be an infinite path starting in a state(
q,
r,
∅)
such that q|
L(
r)
. Then, in every position i of the path such thatπ
[
i]
= (
qi,
ri,
∅)
, it holds qi|
L(
ri)
.Proof. See AppendixA.1
2
4.1. Termination
In an S
[
B]
system, deadlockscannot be compatiblewithadaptability. Indeed,we see adaptabilityasthe propertyfor whichasystemcontinuously operates
understable,allowedmodes(steadystates),bypossiblyperformingadaptationpaths acrossmodes.Intheflatsemanticsdeadlocksoccurringatadaptingstates,e.g.whentheadaptationinvariantcannotbemet,areclearly conflictingwiththeconceptofadaptability.Instead,deadlocksatsteadystatesaremoresubtletointerpret,sincetheymay occurundertwodifferentconditions:
•
fromthecurrentstate,anytransitionleadtoastateviolatingthecurrentconstraints,and,atthesametime,adaptation cannotstartbecausenoneofthenextB states
meetanyoftheadaptationinvariantsandanyofthetargetconstraints. Inotherwords,theflatsemanticsterminateseveniftheB level
canproceed.Evidently,thisviolatesadaptability.•
the B level cannot progress atall. Weconsider thissituationasa bad deadlock state inthebehavioural model. Con-versely,everyB state
indicatingagood termination should
havethechancetoprogressandthereforemustbemodelled, asusualinthiscase,withanidlingself-loop.Wecapturetherequirementforwhichtheflat S
[
B]
mustnotterminatethroughtheProgress(
q,
r)
predicate: Progress(
q,
r)
⇐⇒ (
q,
r,
∅)
−
→ ∨ (
r q,
r,
∅)
r,ψ,r
−−−→
4.2. Flat semantics of the motion control exampleTheflatsemanticsofthetwosystems
S
0[
B]
andS
1[
B]
implementingtheATVmotioncontrollercasestudyaredepictedinFigs. 5 and 6,respectively.
Notably,the samebehaviourallevel B possesses differentadaptation capabilitiesdepending onthestructure S that is considered. Indeed,in
F(
S0[
B])
every adaptation pathleads to a target S state. Onthe other hand,inF(
S1[
B])
alwaysthereexistsanadaptationpathleading toatargetstableregion,butitmaycontaincyclesofadaptingstates,thus leading topossiblyinfiniteadaptationpaths.
Inother words,thebehaviourallevel
B is
abletosuccessfullyadaptunderthestructurallevel S0,forall possible
adapta-tion paths. RecallingthedefinitionsintroducedinSection1,S
0[
B]
isstrongly adaptable.
Conversely,B is
abletosuccessfullyadaptunderS1 onlyfor
some adaptation paths,
i.e.thefiniteones. Therefore,S1[
B]
isweakly adaptable.
Thesetwodifferentkindsofadaptabilityareformalised inSection5.
5. Adaptabilityproperties
ThetransitionalsemanticsintroducedinSection4doesnotguaranteethatanadaptationphasecanalwaysstartorthat, oncestarted, it alwaysends up inastate satisfyingthe constraintsofthetarget S state. In thissectionwe wantto give someformaltoolstoanalyseagivensystemw.r.t.thesekindofproperties.Asafirststep,wecharacterisetwoadaptability notionsby meansoftwo relationsoverthe setof B states andthesetof S states, namelya
weak adaptation relation
R
wanda strong adaptation relation
R
s.Then, wecharacterise the sameadaptabilitynotions logicallyandweprove that theycanbemodelcheckedbyusingproperformulaeofatemporallogic.
Informally,astate
q of
B is weakly adaptable to astater of
S if itsatisfiestheconstraintsimposedbyr and
someofits successorsareeitherweakly adaptabletothesamer or
thereisanadaptationphaseoftheflatsystemthat,fromq,
reaches astateq
thatisweakly adaptabletoanotherS state r.Inotherwords,werequirethatstatessatisfyingL
(
r)
areinrelationFig. 5. The flat semantics of the system S0[B]. Here, every adaptation path leads to a target S-state.
with
r and
that from“border”states,thatisto saythosethatcanstart anadaptationphase forleavingr,
thereisalways at leastonewayto safelyreachanothersteadysituation inanother S state r.Asexplained inSection 4.1, theProgress predicateisused toruleout steadyconfigurationsina stateofbad termination. Weformally definethisrelationusinga co-inductivestyleasitisusuallydone,forinstance,forbisimulationrelations.Fig. 6. TheflatsemanticsofthesystemS1[B].Inthiscase,thereareadaptationpathsleadingtoatargetstableregion,butalsoinfiniteadaptationpaths
duetocycles(seee.g.theadaptationpathfromr0tor1(M,2,1,0,1)→ (S,2,1,0,0)→ (S,2,0,1,0)→ (S,2,0,0,1)→ (M,2,0,0,0)→ (M,2,1,1,0)→ (M,2,1,0,1)).
Definition7 (Weak adaptation). Given an S
[
B]
system, a binary relationR
⊆
Q×
R is a weak adaptation if and only ifwhenever
q
R
r we
have:(i) q
|
L(
r)
andProgress(
q,
r)
,and
(iii) if
(
q,
r,
∅)
−−−−→
r,ψ,r for someψ
∈ (,
A
)
and r∈
R then there exist q∈
Q,
ψ
∈ (,
A
)
andr∈
R such that(
q,
r,
∅)
−−−−→
r,ψ,r +(
q,
r,
∅)
andq
R
r.Wesaythatastate
q
∈
Q is weakly adaptable to astater
∈
R, writtenq
|w
r, ifandonlyifthereisaweakadaptationrelationR
suchthat(
q,
r)
isinR
.Atthelevelofthewholesystem,wesaythat
S
[
B]
isweakly adaptable if
theinitialB state q
0isweakly adaptabletotheinitial
S state r
0.Proposition2(Union of weak adaptation relations). Given an S
[
B]
system, ifR
1andR
2are weak adaptation relations, thenR
1∪
R
2is a weak adaptation relation.
Proof. See AppendixA.2
2
Definition8
(Weak adaptability).
Givenan S[
B]
system,theunionofallweakadaptationrelationsamongthestatesQ andR of S
[
B]
isdenotedbyR
w andistheweak adaptability relation
ofS
[
B]
.Lemma1
(Propagation of weak adaptation relation). Consider an S
[
B]
system and let q and r be such that q|w
r. Then there exists inF(
S[
B])
an infinite pathπ
= (
q=
q0,
r=
r0,
∅)(
−→)
r0 m0(
−−−−−→)
r0,ψ0,r1 n0· · ·
· · · (
qi,
ri,
∅)(
ri−
→)
mi(
−−−−−→)
ri,ψi,ri+1 ni(
q i+1,
ri+1,
∅) · · ·
such that∀
i≥
0.
q
i|wri∧ ((
mi=
1∧
ni=
0)
∨ (
mi=
0∧
ni>
0))
.Proof. See AppendixA.3
2
Weakadaptabilityguaranteesthatthereisalwaysatleastonewayforacertainstateofan S
[
B]
systemtoadapt,thatis tosaytocontinuetoevolveinaconsistentwayw.r.t.thestructuralconstraintsoftheS level.
Astrongerpropertythatcould beusefultoknowabouttheadaptabilityofasystemiswhatwecallstrong adaptability.
A B state q is strongly adaptable toan S state r if itsatisfiestheconstraintsimposedby
r and
allitssuccessorsq
areeitherstrongly adaptabletothesamer
ortheyarealwaysthestartingpointofasuccessfuladaptationphasetowardsstates
q
thatarestrongly adaptabletootherS states. Again,bad deadlocksare excluded fromthe relations.Thistime we requirethat all the“border” statesare safe doorstoothersteadysituations,whateverpathistakenfromthem.
Definition9
(Strong adaptation).
Givenan S[
B]
system, a binary relationR
⊆
Q×
R is a strong adaptation if and onlyifwhenever
q
R
r we have:(i) q
|
L(
r)
andProgress(
q,
r)
,and
(ii) forall
q
∈
Q , if(
q,
r,
∅)
−→ (
r q,
r,
∅)
thenq
R
r, and(iii) alladaptationpathsstartingfrom
(
q,
r,
∅)
arefiniteandendupinastate(
q,
r,
∅)
suchthatq
R
r
.We say that a state q
∈
Q is strongly adaptable to a state r∈
R, written q|s
r, if andonly ifthere is a strong adaptation relationR
suchthat(
q,
r)
isinR
.Atthelevelofthewholesystem,wesaythat
B is strongly adaptable to S if
theinitial B state q0 isstrongly adaptabletotheinitial S state r0.
Proposition3
(Union of strong adaptation relations). Given an
S[
B]
system, ifR
1 andR
2 are strong adaptation relations, thenR
1∪
R
2is a strong adaptation relation.Proof. Asinthecaseofweakadaptationrelations.
2
Definition10 (Strong adaptability). Givenan S
[
B]
system, theunionofall strongadaptationrelations amongthe states Qand
R of S
[
B]
isdenotedbyR
sandisthestrong adaptability relation
ofS[
B]
.Intheremainderofthepaperwewillalternativelysaythatan S
[
B]
systemisweakly (strongly)adaptable,inthesense that B is weakly (strongly) adaptableto S. Itis straightforwardto seethat strongadaptabilityimpliesweak adaptability, sincethestrongversionoftherelationrequiresthateveryadaptationpathreachesatargetS state,
whiletheweakversion justrequiresthatatleastoneadaptationpathreachesatarget S state.Proposition4
(Strong adaptation implies weak adaptation). Consider an S
[
B]
system and let q and r be such that q|s
r. Then, it holds q|w
r.Proof. See AppendixA.4
2
Giventheflatsemantics
F(
S[
B])
= (
F,
f
0,
−→ ∪
r r,ψ,r−−−−→)
ofan S[
B]
system, wewilldenote,inthefollowing,thesetof reachable statesfroma certainstate f∈
F as the reflexiveandtransitive closurePost∗(
f)
of theoperator Post(
s)
= {
s∈
F|
(
s,
s)
∈
−→ ∪
r−−−−→}
r,ψ,r .Lemma2
(Propagation of strong adaptation relation). Consider an S
[
B]
system and let q and r be such that q|s
r. Then, every state(
q,
r,
∅)
∈
Post∗((
q,
r,
∅))
is such that q|s
r.Proof. See AppendixA.5
2
Thefollowingpropositiongivesaprecisecandidaterelationforcheckingifasystemisstrongly adaptable:sucha candi-dateisdeterminedbythesteadystatesoftheflatsemanticsthatarereachablefromtheinitialstate.
Proposition5
(Construction of strong adaptation relation). Given an
S[
B]
system, letF(
S[
B])
= (
F,
f
0,
−
→ ∪
rr,ψ,r
−−−→)
be its flat semantics. Then S[
B]
is strongly adaptable if and only ifR
= {(
q,
r)
∈
Q×
R| (
q,
r,
∅)
∈
Post∗(
f0)
}
is a strong adaptation relation.Proof. See AppendixA.6
2
5.1. Adaptation relations in the motion controller example
Inthefollowingwe willshowthat inthe ATVmotioncontrollercasestudy S0
[
B]
isstrongly adaptable(andthusalsoweakly adaptable)and
S
1[
B]
isweakly adaptable,butnotstrongly adaptable.Inordertoverifythat S0
[
B]
isstrongly adaptable, weneedtoprovethatq
0|s
r0,byfindingastrongadaptationrelationR
s.t.(
q0,
r0)
∈
R
.NotethatinF(
S0[
B])
,everystateisreachablefromtheinitialstate(
0,
r0,
∅)
.ThereforebyProposition 5,weconsidertherelation
R
= {(
q,
r)
|
q
∈
Q,
r∈
R,
(
q,
r,
∅)
∈
F}
,where F is thesetofflatstatesofF(
S0[
B])
.Itiseasytoverifythat
∀(
q,
r)
∈
R.
q
|
L(
r)
;andthatProgress(
q,
r)
holdsforanyofsuchstates,becausetherearenodeadlockstates intheflatsemantics.Thereforecondition (i)ofthedefinitionofstrongadaptationisalwaystrueandhasnottobefurther checked.Clearly,(
q0,
r0)
∈
R
.Finally,itcanbeshownthatrequirements(ii)and(iii)ofDefinition 9holdforeachelementof
R
.Weshowtheprooffor
((
M,
0,
0,
0,
0),
r0)
and((
M,
0,
1,
1,
0),
r0)
.Theotherpairscanbeprovedanalogously.• ((
M,
0,
0,
0,
0),
r0)
(ii)((
M,
0,
0,
0,
0),
r0,
∅)
r0−−→ ((
M,
0,
0,
1,
0),
r0,
∅)
and((
M,
0,
0,
1,
0),
r0)
∈
R
;((
M,
0,
0,
0,
0),
r0,
∅)
−−→ ((
r0 M,
0,
1,
1,
0),
r0,
∅)
and((
M,
0,
1,
1,
0),
r0)
∈
R
(iii)((
M,
0,
0,
0,
0),
r0,
∅)
r,ψ,r−−−−→
• ((
M,
0,
1,
1,
0),
r0)
(ii)((
M,
0,
1,
1,
0),
r0,
∅)
−→
r(iii) thereisonlyoneadaptationpathfrom
((
M,
0,
1,
1,
0),
r0,
∅)
leadingtotheflatstate((
S,
0,
1,
0,
0),
r1,
∅)
(throughtheB state
(
M,
0,
1,
0,
1)
),and((
S,
0,
1,
0,
0),
r1)
∈
R
.On the other hand, we demonstrate that S1
[
B]
is weakly adaptable by finding a weak adaptation relationR
s.t.(
q0,
r0)
∈
R
.WetakeasR
thefollowingrelation:{((
M,
0,
0,
0,
0),
r0), ((
S,
0,
1,
0,
0),
r1), ((
M,
0,
1,
1,
0),
r0), ((
S,
0,
0,
1,
0),
r1)
}
Similarly to S0
[
B]
,(
q0,
r0)
∈
R
andfor all(
q,
r)
∈
R
, q|
L(
r)
and Progress(
q,
r)
both holds. Thus, we need to check requirements(ii)and(iii)ofDefinition 7toprovethatR
isaweakadaptationrelation.Weobservethatpairs
((
M,
0,
0,
0,
0),
r0)
and((
S,
0,
1,
0,
0),
r1)
meetrequirements(ii)and(iii),thelatterbeingtriviallyverified since they do not admit adaptation transitions.Pairs
((
M,
0,
1,
1,
0),
r0)
and((
S,
0,
0,
1,
0),
r1)
also comply withtheweak adaptation definition,sincethey can bothreach,in afinite numberofadaptationsteps, flatstates thatmap to elementsin
R
,i.e.((
S,
0,
1,
0,
0),
r1)
and((
M,
0,
0,
0,
0),
r0)
,respectively.However,notethat