horn clauses and feature-structure logic principles and unification algorithms

《horn clauses and feature-structure logic principles and unification algorithms》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、HornClausesandFeature-StructureLogic:PrinciplesandUnicationAlgorithmsyStephenJ.HegnerUniversityofBergenDepartmentofInformaticsBergenHigh-TechnologyCenterN-5020Bergen,NorwayInternet:hegner@ii.uib.no(Revised:June1993)ThispaperappearsasReportNo.1,June1993,intheseriesReportsinLogic,Language,an

2、dInformation,publishedby:UniversityofOslo,DepartmentofLin-guistics,P.O.Box1102,N-0317Oslo,Norway.AnabbreviatedversionofthisreportappearsinthebookConstraints,LanguageandComputation,editedbyM.Rosner,C.J.Rupp,andR.Johnson,publishedbyAcademicPress,1994,pp.111-147.AbstractThedesirabilityofHorncl

3、ausesinlogicaldeductivesystemshaslongbeenrecog-nized.Thereasonsareatleastthreefold.Firstly,whileinferencealgorithmsforfulllogicsofanyreasonableextentaretypicallyintractable,forsystemsrestrictedtoHornclausesthepictureismuchbetter.(Forexample,inordinarypropositionallogic,whilethefullsatisabi

4、lityproblemisNP-complete,alinear-timealgorithmexistsforHornclauses.)Secondly,theknowledge-representationcapabilitiesofHornclauses,whileweakerthanthoseofthefulllogic,remainremarkablyrich;indeed,farricherthanthatofsimpleconjunctivelogicalone.Thirdly,Hornclausesdenethemaximalsubsetofafulllogi

5、cwhichhasthepropertyofadmittinggenericmodels,whichroughlymeansthatforanysetofHornclauses,thereisaleastmodeloftheclausesinthatset.ItisthepurposeofthispapertoinitiateaninvestigationofHornclauselogicforanextendedclassoffeaturestructures.Afterlayingthegroundworkforthiscontext,weprovidetwokeyres

6、ults.Intherst,weshowhowthepropertyofad-mittinggenericmodelscanbeextendedtofeaturestructurelogic,anddemonstratetheimportanceofthispropertyingeneralizingtheuseofordinaryfeaturestructuresinunication-basedformalisms.Oursecondcontributionisatractableunicationalgorithmforextendedfeaturestructu

7、resconstrainedbyHornclauses.Thisalgo-rithmisanintegrationofthetraditionalunicationalgorithmforfeaturestructuresandthelinear-timeinferencealgorithmforpropositionallogic.yCurrentaddress:DepartmentofComputerScienceandElectricalEngineering,VoteyBuilding,Uni