PROBABILISTIC DESCRIPTION LOGICS FOR THE SEMANTIC

INFSYSRESEARCHREPORTInstitutf¨urInformationssystemeABWissensbasierteSystemeTechnischeUniversit¨atWienFavoritenstraße9-11A-1040Wien,AustriaTel:[phone]Fax:[e-mail]¨URINFORMATIONSSYSTEMEARBEITSBEREICHWISSENSBASIERTESYSTEMEPROBABILISTICDESCRIPTIONLOGICSFORTHESEMANTICWEBTHOMASLUKASIEWICZINFSYSRESEARCHREPORT1843-06-05MARCH2007INFSYSRESEARCHREPORTINFSYSRESEARCHREPORT1843-06-05,MARCH2007PROBABILISTICDESCRIPTIONLOGICSFORTHESEMANTICWEBMARCH15,2007ThomasLukasiewicz1Abstract.Theworkinthispaperisdirectedtowardssophisticatedformalismsforreasoningun-derprobabilisticuncertaintyinontologiesintheSemanticWeb.OntologiesplayacentralroleinthedevelopmentoftheSemanticWeb,sincetheyprovideaprecisedefinitionofsharedtermsinwebresources.TheyareexpressedinthestandardizedwebontologylanguageOWL,whichcon-sistsofthethreeincreasinglyexpressivesublanguagesOWLLite,OWLDL,andOWLFull.ThesublanguagesOWLLiteandOWLDLhaveaformalsemanticsandareasoningsupportthroughamappingtotheexpressivedescriptionlogicsSHIF(D)andSHOIN(D),respectively.Inthispaper,wepresenttheexpressiveprobabilisticdescriptionlogicsP-SHIF(D)andP-SHOIN(D),whichareprobabilisticextensionsofthesedescriptionlogics.Theyallowforexpressingrichter-minologicalprobabilisticknowledgeaboutconceptsandrolesaswellasassertionalprobabilisticknowledgeaboutinstancesofconceptsandroles.Theyaresemanticallybasedonthenotionofprobabilisticlexicographicentailmentfromprobabilisticdefaultreasoning,whichnaturallyinter-pretsthisterminologicalandassertionalprobabilisticknowledgeasknowledgeaboutrandomandconcreteinstances,respectively.Asanimportantadditionalfeature,theyalsoallowforexpressingterminologicaldefaultknowledge,whichissemanticallyinterpretedasinLehmann’slexicographicentailmentindefaultreasoningfromconditionalknowledgebases.Wethenpresentsoundandcom-pletealgorithmsforthemainreasoningproblemsinthenewprobabilisticdescriptionlogics,whicharebasedonreductionstoreasoningintheirclassicalcounterparts,andtosolvinglinearoptimiza-tionproblems.Inparticular,thisshowstheimportantresultthatreasoninginthenewprobabilis-ticdescriptionlogicsisdecidable/computable.Furthermore,wealsoanalyzethecomputationalcomplexityofthemainreasoningproblemsinthenewprobabilisticdescriptionlogicsinthegen-eralaswellasrestrictedcases.1DipartimentodiInformaticaeSistemistica,Universit`adiRoma“LaSapienza”,ViaSalaria113,I-00198Rome,Italy;e-mail:[e-mail]¨urInformationssysteme,TechnischeUniversit¨atWien,Favoriten-straße9-11,A-1040Vienna,Austria;e-mail:[e-mail]:Thispaperisasignificantlyextendedandrevisedversionofapaperthatappearedin:ProceedingsJELIA-2002,volume2424ofLNCS,pp.86–97.Springer,2002[30].ThisworkwassupportedbyaHeisenbergProfessorshipoftheGermanResearchFoundation(DFG).IamverygratefultoRosalbaGiugnoforhercontributionstotheJELIA-2002abstractofthispaper.Copyrightc2007bytheauthorsINFSYSRR1843-06-05IContents1Introduction12MotivatingExamples33TheDescriptionLogicsSHIF(D)andSHOIN(D)53.1Syntax..............................................53.2Semantics............................................64TheProbabilisticDescriptionLogicsP-SHIF(D)andP-SHOIN(D)74.1Syntax..............................................84.2Semantics............................................104.2.1MotivationandKeyIdeas...............................104.2.2Preliminaries......................................114.2.3Consistency.......................................124.2.4LexicographicEntailment...............................135Algorithms155.1ProblemStatements.......................................155.2ConsistencyandTightLexicographicEntailment.......................165.3SatisfiabilityandTightLogicalEntailment...........................176Complexity196.1ComplexityClassesandPreviousResults...........................196.2TheDescriptionLogicDL-Lite.................................206.3ComplexityResults.......................................207RelatedWork227.1ProbabilisticDescriptionLogicsandWebOntologyLanguages................227.2ConditionalKnowledgeBasesandDefaultsinDescriptionLogics..............237.3PossibilisticandFuzzyDescriptionLogics...........................248Conclusion24INFSYSRR1843-06-0511IntroductionTheSemanticWebinitiative[8,23]aimsatanextensionofthecurrentWorldWideWebbystandardsandtechnologiesthathelpmachinestounderstandtheinformationontheWebsothattheycansupportricherdiscovery,dataintegration,navigation,andautomationoftasks.ThemainideasbehindtheSemanticWebaretoaddamachine-readablemeaningtoWebpagestouseontologiesforaprecisedefinitionofsharedtermsinWebresources,tomakeuseofknowledgerepresentationtechnologyforautomatedreasoningfromWebresources,andtoapplycooperativeagenttechnologyforprocessingtheinformationoftheWeb.TheSemanticWebconsistsofseveralhierarchicallayers,wheretheOntologylayer,intheformoftheOWLWebOntologyLanguage[75](recommendedbytheW3C),iscurrentlythehighestlayerofsufficientmaturity.ThelanguageOWLconsistsofthethreeincreasinglyexpressivesublanguagesOWL