模型檢驗(yàn)及其布爾可滿足問題的研究.pdf

1、中國(guó)科學(xué)院計(jì)算技術(shù)研究所博士學(xué)位論文模型檢驗(yàn)及其布爾可滿足問題的研究姓名：邵明申請(qǐng)學(xué)位級(jí)別：博士專業(yè)：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)指導(dǎo)教師：李曉維20050330醞0D璉黽lC王芰鏊GKlNGAN矜B00LEANSATlSFlABILITYpR0牯LEMMingShao(ComputerArchitecture)DirectedByProfXiaoweiLiAbstractlntheareaofhaj畦w8珊modelcheckingtheorigi

2、naldesignisabstracted氌sfinitestatetransitionsyste￡norKripkestructure)whilethepropertytobeverifiedisrepresented籍temporallogiclanguageIntNswaytheoriginaldesignwiltbesmoothlyveri一矗繾throughcheckingwhetherthemodelsatisfiesthe

3、propertyconsideredOnet酗omebottlenecktoprohibitthemethodologyofmodelcheckingfromapplyingtoindustrialappficafion拓thefactthatthesizeofthestatespaceisgrowingexponentiallywiththein娌easeof譙enumberofthestatevariablesThedifficul

4、tylyingbehindishowtore》resentthetransitionrelationshipofthestatespaceofmodeleffectivelyToalleviateorconquerthebottleneck，rese甜chemhaveproposedv黼ionsimportantapproaches，forinstances，theoptimizedvarianksofBirmryDecisionDia

5、grams《BDDs)，andtransformingtheverificationtaskintosolvingtheBooleanSa￡isfiability(SAT)problem。8swelI豁thevariousabstractionrefinementmethodsperformedontheoriginalmodel。Undersuchreseexchb懿kgrounds，thethegis勤Gu粥onthefollowi

6、ngkeyproblems：howtobuildacompactandefficienttransitionrelation；howtoefficientlyextractMinimalUnsatisfiabie《MU》subformula；theproblemofseasitivi夠姆theparametercalledstepnumberfortheSurveyPropagation《SP)algorithmAimingtothee

7、problems，thethesisobtainedthe姒lowingoriginalideasandcontributionsi疑臻strate銎for魄澈甄壤transitionrelationshipisproposedinsymbolicmodelcheckingIt稔weUknownthatacompactandefficienttransitioniscrlticalinimagecomputation。Therulepr

8、oposedforgroupingthepartitionedtransitionrelationshipisbasedonSOFllecertainfeatureofthesupportofeachtransitionrelationshippart。掣hemerit螽thisalgorithm法潲囊鬈挺黼揀鶉&velationsb2pistwofc連d。Outhe奄鞋毽hand，thismethodcaobuild8morecomp

9、acttransition，theexperimentsexhibitthatthereductionforthesizerangesfrom30％to10％。thesizeismeasuredbythenumberofthenodesintheBDDrep撇entingthetransitionrelationship，Ontheotherhand々thestepinimageComputationispartiMty糙dueedin