文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Institute for Logic, Complexity, and Deduction Systems
侵权投诉

Institute for Logic, Complexity, and Deduction Systems

Manipulation of Boolean functions has important applications in such fields as hardware verification, non-monotonic reasoning, and decision support. Most often, in such applications, the set of prime implicates/implicants of a large formula must be compute

Anti-LinksforBooleanFunctionManipulation

BernhardBeckertReinerH¨ahnleNeilV.Murray

InstituteforLogic,Complexity,

andDeductionSystems

UniversityofKarlsruhe,D-76128Karlsruhe

@ira.uka.de

doc.guandang.net /AnavaiRameshInstituteforProgramming&LogicsDepartmentofComputerScienceUniversityatAlbany,Albany,NY12222rameshag,nvm@cs.albany.edu

ManipulationofBooleanfunctionshasimportantapplicationsinsuch eldsashardwareveri cation,non-monotonicreasoning,anddecisionsupport.Mostoften,insuchapplications,thesetofprimeimplicates/implicantsofalargeformulamustbecomputed.

ManyalgorithmshavebeenproposedtocomputetheprimeimplicatesofpropositionalBooleanformu-las,e.g.[4,5].Mostofthemassumethattheinputisinconjunctive/disjunctivenormalform(CNF/DNF).Thebottleneckofsuchalgorithmsisusuallythelargenumberofsubsumed(i.e.non-minimal)disjunc-tive/conjunctivepathsthroughthegivenformula.Therefore,itiscrucialtoremoveasmuchredundancyofthiskindaspossible,beforeanyexplicitenumerationofprimeimplicates/implicantsstarts.Evenifsuchexplicitcomputationofprimeimplicates/implicantsisnotanimmediategoal,removinganyredundanciesduetosubsumeddisjunctive/conjunctivepathsisusuallyhighlydesirable.

Amongthemostsuccessfulmethodsusedtodealwiththistaskarebinarydecisiondiagrams(BDDs)[2,3].Itis,however,wellknownthatBDDmethodsdonotworkwellonsomeclassesofformulas,inparticular,whentheyareusedtocomputeprimeimplicants.AnotherrestrictionofBDDsisthatthey(atleasttheef cientversions)essentiallyproduceanXOR-ANDnormalform,butthisisnotalwayswhatisneeded.

Here,wepresentatechniquebasedonanti-linksforidentifyingandremovingsubsumedpaths,thatoperatesonformulasinnegationnormalform(NNF).1ItisnotanalternativetoBDDsandothermethodsforcomputingprimeimplicants,butisintendedtobeusedasasupplementarypre-processingstepthatenhancestheoverallperformanceofthesystem.

consistsofoccurrencesandofaliteralinanNNFformula.IftheAnanti-link

(largest)subformulasandofthatcontainand,respectively,aredisjunctivelyconnected,wecalladisjunctiveanti-link.Ifandareconjunctivelyconnected,thenwecallaconjunctiveanti-link.

Iftheformulacontainsadisjunctivepaththatissubsumedbyadistinctpath,thencontainsadisjunctiveoraconjunctiveanti-link.Unfortunately,theconverseisnottrue:thepresenceofanti-linksdoesnotimplythepresenceofsubsumedpaths.Thereis,however,alargeclassofanti-links,thatwecallredundant,thatisalwaysanindicatorforsubsumedpaths:Adisjunctiveanti-linkinisredundantifeitheroristheargumentofaconjunction.Inthatcasecertaindisjunctivepathsthroughandthatcontainoraresubsumedbyadisjunctivepathinthatcontainstheanti-link.

Example1Considertheformula

Thetwooccurrencesofformaredundantdisjunctiveanti-link.Thedisjunctivepathissubsumedbythepath(withliteralset),thatcontainstheanti-link.Thetwooccurrencesofarebothargumentsofdisjunctions,andthuscompriseanon-redundantanti-link.

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email