!!!!!!!Realization Problem for Formal Concept Analysis

《!!!!!!!Realization Problem for Formal Concept Analysis 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

RealizationProblemforFormalConceptAnalysis?N.V.ShilovLavren'evav.,6,Novosibirsk630090,Russiashilov@iis.nsk.suAbstract.FormalConceptAnalysis(FCA)isanapproachtoknowledgeengineering,representation,andanalysis.A`standard'FCA-work owstartswithsome`experimental'data,classiesobjects"andtheirat-tributes"inthedata,representsrelationsbetweenobjectsandattributesbyanumberofcross-tables(matrices),couplescompatiblesetsofobjectsandattributesintoconcepts,andbuildsanumberofconceptlattices.Incontrast,FCArealizationproblemstartswith`fragments'ofsomecross-tablesandconceptlatticesandtrytogeneratedatathatmatchthesefragmentsofcross-tablesandconceptlatticessimultaneously.Thepa-perdenesformallytheFCArealizationproblemandprovesthatitisdecidable.Itisdonebyreductionoftheproblemtotheconsistencyprob-lemfordescriptionlogicALBO.ButitisstillanopenquestionwhetherFCA-realizationproblemhavebettercomplexityboundthanALBOhas.1IntroductionFormalConceptAnalysis(FCA)byR.WilleandB.Ganter[2]isanalgebraicframeworkforknowledgeengineering,representation,andanalysis.Ittakessome`experimental'data,classiesobjects"andtheirattributes"inthedata.ThenmathematicalpartofFCAtakesmatricesthatspecifyrelationbetweenobjectsandattributesasaninputandndscorresponding`naturalclusters'(sets)ofattributesand`naturalclusters'(sets)ofobjects.Everypairofcorresponding`natural'setsofobjectsandattributesformsaformalconcept1.Thesetoffor-malconceptsobeysthemathematicalaxiomsdeningalattice,andiscalledaconceptlattice.LetusillustratebasicFCAnotionsbythefollowingexample.AssumethatsomeComputerScienceDepartmenthas1FullProfessor(F),1AssociateProfes-sor(A),1Lecture(L),2Tutors(T1andT2),and1ResearchProgrammer(R).CoursesprovidedbythedepartmentareProgrammingLanguages(PL),Oper-atingSystems(OS),DataBases(DB),andFormalMethods(FM).Researchrangethesametopics.Sampledataaboutstateachingandresearchprolearepresentedinthetables1.?Thisresearchissupportedinpartsby(a)byjointgrantRFBR05-01-04003-a-DFGprojectCOMO,GZ:436RUS113/829/0-1,(b)byIntegrationGrantn.14SiberiaBranch,RussianAcademyofScience.1ForadistinctionwithDescriptionLogic,weuseacombinedterm`formalconcept'intheFCAcontext. TeachingPLOSDBFMAIResearchPLOSDBFMAIFxxxFxxAxxxAxxLxxxLxxT1xxxPxT2xxxTable1.SamplestuTeachingandResearchproleBothtablesarematricesorcross-tables.Thesematricesestablishbinaryre-lationsbetweencorrespondingobjectsandattributes.Objectsareteachingandresearchstamembers:ObjTeaching=fF,A,L,T1,T2g,ObjResearch=fF,A,L,Rg.Attributesareteachingandresearchtopics:AtrTeaching=AtrResearch=fPL,OS,DB,FM,AIg.Everytriplethatconsistsofobjects,attributesandacross-tableiscalledformalcontext.Forexample,(fF,A,L,T1,T2g,fPL,OS,DB,FM,AIg,Teaching)aswellas(fF,A,L,Pg,fPL,OS,DB,FM,AIg,Research)areformalcontexts(thatwereferbynamesoftheirmatrices).InTeachingformalcontexttwoobjectsAandLsharetwocommonattributesOSandDB.Moreover,thereisnoothersharedattributefortheseobjects,butOSandDBonly.InFCAtermsthisconnectionbetweenasetofobjectsfA,LgandasetofattributesfOS,DBgiswrittenintheformfA,Lg"Teaching=fOS,DBg.Ontheoppositeside,AandLaretheonlyobjectsthatshareattributesOSandDB.InFCAtermsthisconnectionbetweenasetofattributesfOS,DBgandasetofobjectsfA,LgiswrittenintheformfOS,DBg#Teaching=fA,Lg.ObservethatasetoftwoobjectsfA;LgandasetoftwoattributesfOS;DBgcorrespondtoeachotheranddeneeachotheruniquelyinthecontextTeaching.So,inTeachingcontextfA,Lgisanexampleofa`naturalcluster'ofobjectssincethisclusterisuniquelydenedbyacorresponding`naturalcluster'ofsharedattributesfOS;DBg.InFCAterms,apair(fA,Lg,fOS,BDg)iscalledformalconceptinaformalcontextTeaching.Incontrast,apair(fA,Lg,fOS,BDg)isnotaformalconceptinthesecondformalcontextResearch,sincefA,Lg"Research=fOSg6=fOS,DBgandfOS,DBg#Research=;6=fA,Lg.NowwearereadytointroduceFCArealizationproblematinformallevel.Thistimewearegivensomeconstrainsforcross-tablesandformalconceptsexpressedinset-theoreticandFCAterms.Thenweareaskedtogeneratecross-tablesthatmatchallgivenconstrains(orrefuteapossibilitytogeneratethesecross-tables).Thefollowingsta-hiringproblemcouldillustrateFCArealizationproblem.LetusassumethatanotherComputerScienceDepartmentwouldliketohirenewsta,namely:1FullProfessor(F),1AssociateProfessor(A),1Lecture(L),2Tutors(T1andT2),and1ResearchProgrammer(R).TeachingandresearchproleofnewstamustcoverProgrammingLanguages(PL),OperatingSystems(OS),DataBases(DB),FormalMethods(FM).Butduetodepartmentpolicytherearesomerequirements: TeachingResearchPositionPLOSDBFMAIPLOSDBFMAIFALT1T2PBxxxxxxxDxxxxxxxGxxxxxxxHxxxxxxxxxKxxxxxxLxxxxxxxxxMxxxNxxxxxxTable2.Summaryofsampleapplicants1.FullProfessorandAssociateProfessortogethermustcoverallteachingsub-jects.2.LecturermustbeabletoteachsomesubjectinsteadofFullProfessorandsomesubjectinsteadofAssociateProfessor.3.Tutorstogethermustcoverallteachingsubjects.4.EverytutormustbeabletoteachasubjectafterFullProfessor.5.Fullprofessor,Associateprofessor,andLecturermustconductresearchinsomeresearchareaswithinsubject(s)theyteach.6.ResearchProgrammermustsupportresearchofFullProfessor.Assumealsothateightpeoplehaveappliedforthesevacantpositions:Beanka(B),Donald(D),Greta(G),Huan(H),Kevin(K),Leonora(L),Monica(M),andNorman(N).Summaryoftheirapplicationsispresentedinthetable2.(Itusesthesamenotationastable1.)Aparticularexampleofthesta-hiringproblemis:whetheritispossibletoselectvepeopleamongeightapplicantstollvacantpositionsandtomeetsixaboverequirementssimultaneously?Fortunately,thisproblemcanbeencodedeasilyasthefollowinginstanceoftheFCA-realizationproblem.1.Splittable2ontothreeformalcontextsTeaching,Research,andPosition.Presentcross-tablesoftheseformalcontextsrowbyrowasfollows:{B"Teaching=fPL,OS,DBg,B"Research=fPL,OSg,B"Position=fF,Ag;{D"Teaching=.......,D"Research=.......,D"Position=.......;{................................2.LetU,V,X,Y1,Y2,andZbevariablesforapplicantstobeappointedasFullProfessor,AssociateProfessor,Lecture,Tutor1andTutor2,andResearchProgrammer:{fU,V,X,Y1,Y2,ZgfB,D,G,H,K,L,M,Ng,{F2U"Position,A2V"Position,L2X"Position,T2Y"Position,T2Y"Position,P2Z"Position.11223.FormulatepositionrequirementsinFCAtermsusingvariablesU,V,X1,X2,Y,andZinsteadofpositionnamesF,A,L,T1,T2,andP: {fUg"Teaching[fVg"Teaching=fPL,OS,DB,FM,AIg,{fXg"TeachingfUg"Teaching6=;,fXg"TeachingfVg"Teaching6=;,{................................4.Find`values'forvariablesU,V,X,Y1,Y2,andZthatmeetallaboveconstrainssimultaneously,orrefuteexistenceofthesevalues.Fortunately,FCArealizationproblemisdecidableduetoareductiontosatis-abilityproblemforadescriptionlogicALBO[4].Itimpliesthataparticularinstanceofstu-hiringproblemaswellasanyotherinstanceofthisproblemcanbesolvedautomaticallybysometableaualgorithm.AreductioncanbedonebyintegratingFCAconstructsintoDescriptionLogic(DL)[5].ForeveryparticulardescriptionlogicLletL/FCAbeanexten-sionofLbyFCAoperations`"'and`#'.Paper[5]hasprovedthatL/FCAcanbeexpressedinL(:;){anothervariantofLthatisclosedwithrespecttorolecomplementandinverse.Thepaperisorganizedasfollows.Thenextsection2introducesbasicnotionsandsomefactsrelatedtoFormalConceptAnalysis.IntegrationofFCAintoDLissketchedinthesection3.FormalizationofFCA-realizationproblemanditsreductiontoALBO-satisabilityarepresentedinthelastsection4.2FoundationsofFCABasicFormalConceptAnalysis(FCA)denitionsbelowfollowmonograph[2],butweusealittlebitdierentnotation.Denition1.Aformalcontextisatriple(O;A;B)whereOandAaresetsof`objects'and`attributes'respectively,andBOAisabinaryrelationconnectingobjectsandattributes.Forexample,everyterminologicalinterpretation(D;I)denesafamilyofformalcontexts(D;D;I(R))indexedbyrolesymbolsand/orroletermsR.Usuallyformalcontextsarerepresentedascross-tables.Across-tableforaformalcontext(O;A;B)isamatrix,whererowscorrespondtoobject,columns{toattributes;foranyobjectsandattributet,if(s;t)2Bthenacross`x'islocatedinaposition(s;t)ofthematrix.Seetable1foranexample.Twomajoralgebraicoperationsforformalcontextsareupperandlowerderivations.Theyareusedtodeneanotionofaformalconcept.Denition2.Let(O;A;B)beaformalcontext.{ForeverysetofobjectsXOitsupperderivationX"isasetofattributesft2A:foreverys2O;ifs2Xthen(s;t)2Bg,i.e.thecollectionofallattributesthatallobjectsinXhavesimultaneously.{ForeverysetofattributesYAitslowerderivationY#isasetofobjectsfs2O:foreveryt2A;ift2Ythen(s;t)2Bg,i.e.thecollectionofallobjectsthathavesimultaneouslyallattributesinY. {Aformalconceptisanypair(Ex;In)suchthatExO,InA,andEx"=In,In#=Ex;componentsExandInoftheformalconcept(Ex;In)arecalleditsextentandintentrespectively.Theabovedenitionisgivenforaxedsinglecontextwhenonecanuseasuperscriptnotation`"'and`#'todenoteupperandlowerderivativeoperationsforanimplicitbinaryrelation.ButinthecasewhenwehaveafamilyofformalcontextsKj=(Oj;Aj;Bj),j2JitmakessensetoattachanexplicitreferenceKj,orBj,orindexjtothesuperscripts,forexample:`"Kj',`#Bj'or`"j'.Denition3.ForeveryformalcontextK=(O;A;B){letFC(K)bethesetofallformalconceptsoverK,>Kbeaformalconcept(O;O"),and?beaformalconcept(A#;A);K{letKbethefollowingbinaryrelationFC(K):(Ex0;In0)(Ex00;In00)iEx0Ex00and/or2In00In0;K{letsupKbethefollowingoperationonsubsetsofFC(K):supf(Ex;In)2FC(K):j2Jg=(([Ex)"#;In);Kjjj2Jjj2Jj{letinfKbethefollowingoperationonsubsetsofFC(K):inff(Ex;In)2FC(K):j2Jg=(Ex;([In)#").Kjjj2Jjj2JjThefollowingfactisapartoftheBasicTheoremonConceptLattices[2].Fact1ForanyformalcontextKanalgebraicsystem(FC(K);K;>K;?K;supK;infK)isacompletelattice.Thedenitionbelowmakessenseduetotheabovetheorem.Denition4.ForeveryformalcontextKletconceptlatticeCL(K)bethefol-lowingcompletelattice(FC(K);K;>K;?K;supK;infK).3IntegratingFCAoperationsintoDLTherearemanydescriptionlogics,butwedeneinbriefonlysomeofthem.Pleasereferacomprehensivehandbook[1]forfulldetails.AttributeLanguagewithComplements(ALC)[3]isaparticularexampleofdescriptionlogic.Insimplewords,ALCadoptsrolesymbolsastheonlyroleterms,conceptsymbols{aselementaryconceptterms,andpermits`Boolean'constructs`:',`t',`u',universalandexistentialrestrictions`8'and`9'astheonlyconceptconstructs.Aformalsyntaxdenitionfollows.Denition5.ALCisadescriptionlogicwhichonlyroletermsarerolesymbolsRSandconcepttermsaredenedbythefollowingcontext-freegrammar:CALC::=CSj>j?j(:CALC)j(CALCtCALC)j(CALCuCALC)j(8RS:CALC)j(9RS:CALC)2Thesetwoconditionsareequivalenteachother. wheremetavariablesCSandRSrepresentanyconceptandrolesymbols,respec-tively.SemanticsofALCisdenedinthestandardwayinterminologicalinter-pretations[1].ManydescriptionlogicscanbedenedasextensionsofALCbyconceptandroleconstructs.Letusrepresentacollectionofconceptandroleconstructsbyasequenceofconceptconstructsfollowedbyasequenceofroleconstructsseparatedbyadelimiter&3.So,ageneralpatternforacollectionisC&R,whereCstaysforasequenceofconceptconstructs,andRstaysforasequenceofroleconstructs.ForanycollectionofthiskindletALC(C&R)bea`closure'ofALCthatadmitsallconceptandroleconstructsinC&R.Denition6.AvariantofDLisadescriptionlogicLwithsyntaxthat{containsallconceptandrolesymbolsCSandRS,{isclosedunderconceptconstructs`:',`t',`u',`8'and`9'.Letusremarkthat`variant'isnotaconventionalterm.Weintroduceitfortech-nicalconvenience,sinceconventionalDLglossarydoesnotprovideanequivalentterm.Letusalsoremarkthatfromtheviewpointoftheabovedenition,ALCisthesmallestvariantofDL.Denition7.LetLbeavariantofDLandC&Rbeacollectionofconceptand/orroleconstructs.ThenletL(C&R)bethesmallestvariantofDLthatincludesLandisclosedunderallconstructsinC&R.Forexample,ALC(:;)isanextensionofALCwhereanyrolesymbolcanbenegatedand/orinverted.AnotherimportantexampleisAttributeLanguagewithBooleanalgebrasonconceptsandroleswithObjectsymbolsALBO[4].ThisdescriptionlogiccanbedenedasALC(OS&?;:;),where`OS'representsasetofsingletonconcepttermconstructs`fag'foreveryobjectsymbola2OS(thatarecallednominals4),and`?'representstworoletermconstructs{domain`'andrange`'restrictions.Fact2SatisabilityandconsistencyproblemsaredecidableforALBOandthereexistatableauproceduresthatsolvethem.But(unfortunately)bothproblemsarehardtosolve:theyarecompleteintheclassofnon-deterministicexponentialtimecomputationsNExp-Time.Pleaserefer[4]fordetails.Denition8.LetLbeavariantofDL.ThenletL/FCAbeaclosureofLwithrespecttotwonewformulaconstructorsfortheupperandlowerderivatives.Syntaxofthesetwoconstructsfollows:foreveryroletermRandeveryconcepttermXlet(X"R)and(X#R)beconcepttermstoo.Theyarereadas`upperderivativeofXwithrespecttoR'and,respectively,as`lowerderivativeofXwithrespecttoR'.Foreveryterminologicalinterpretation(D;I)let3RecallthatDLdoesnotuseconjunctionsymbol`&',butintersection`u'.Wedropoutthedelimiter`&'whenconcept/roleconstructsareimplicit.4Duetomodallogictradition.Theyarecalledconstantsnprogramlogictradition. {I(X"R)=ft:foreverys2D;ifs2I(X)then(s;t)2I(R)g({i.e.theupperderivationofI(X)inaformalcontext(D;D;I(R)));{I(X#R)=fs:foreveryt2D;ift2I(X)then(s;t)2I(R)g({i.e.thelowerderivationofI(X)inaformalcontext(D;D;I(R))).Thedenitionstates,thatforeveryDLvariantL,L/FCAissimplyL(";#).Inparticular,ALC/FCAisanextensionofALCwherebothderivativeconstructorsareallowed.ThefollowingfacthasbeenprovedinProposition1in[5].Fact31.LetLbeavariantofDL.ForeveryroleandconcepttermswithinLthefollowingconceptsofL/FCAandL(:;)areequivalent:(a):(X"R)and9:R:X,(b)X"Rand8:R::X,(c):(X#R)and9:R:X,(d)X#Rand58:R::X.2.L/FCAcanbeexpressedinL(:;)withlinearcomplexity,i.e.everycon-ceptXinL/FCAisequivalenttosomeconceptYinL(:;)thatcanbeconstructedinlineartime.Inparticular,ALC/FCAisexpressibleinALC(:;),andALBO/FCAisex-pressivelyequivalenttoALBOitself.ThedecidabilityofALBO(seeFact2)impliesthenextcorollary.Corollary1.ForanyfragmentLofALBOthesatisabilityandconsistencyproblemsforL/FCAaredecidable.4FCARealizationProblemLetusdeneanewalgorithmicproblemforFormalConceptAnalysiswhichwecallFCArealizationproblem.Itcanbedenedinformallyasfollows.Letusassumethatisanite`collection'ofset-theoretic(in)equalitieswrittenintermsofuninterpretedsymbolsforindividualobjectsandattributes,forsetsofobjectsandattributes,forformalcontextswithaidofset-theoreticoperations,upperandlowerderivative.Thequestionis:cananysetofformalcontextsrealizethis`collection'?Formaldenitionsfollows.Inthesedenitionsweassumethat{isaxedsetofobjectconstants,{isaxedsetofattributeconstants,{isaxedalphabetofformalcontextnames,{isaxedalphabetofnamesforsetsofobjects,{isaxedalphabetofnamesforsetsofattributes,5Letusremarkthat`operator'8:R::Xhasbeenalreadyknowinmodal,program,anddescriptionlogiccommunityas`windowoperator'[4]. {andisaxedalphabetofnamesforformalcontexts.Denition9.FCA-expressioncanbeofoneoftwotypes:eitherofOS-type(object-settype)orofAS-type(attribute-settype).FCA-expressionsandtheirtypesaredenedbymutualrecursionasfollows.Object-settypeexpressions:{EverynitesubsetofisanexpressionofOS-type.{EverynameinisanexpressionofOS-type.{Foreveryname!2,objectsetO!isanexpressionofOS-type.{Foreveryexpression"ofAS-typeandeverycontextname!2,lowerderivative"#!isanexpressionofOS-type.{Everyset-theoreticexpressionconstructedfromanyexpressionsofOS-typebymeansofunion`[',intersection`'andset-dierence`n',isalsoanexpressionofOS-type.Attribute-settypeexpressions:{EverynitesubsetofattributesisanexpressionofAS-type.{EverynameinisanexpressionofAS-type.{Foreveryname!2,attributesetA!isanexpressionofAS-type.{Foreveryexpression"ofOS-typeandeverycontextname!2,upperderivative""!isanexpressionofAS-type.{Everyset-theoreticexpressionconstructedfromanyexpressionsofAS-typebymeansofunion`[',intersection`'andset-dierence`n',isalsoanexpressionofAS-type.Denition10.AFCA-sentencehasonofthefollowingforms:{o2",whereo2isanyobject,"isanyexpressionofOS-type;{a2",wherea2isanyattribute,"isanyexpressionofAS-type;{"0"00,where"0and"00areanyFCA-expressionsofonetype;{("0;"00)FC(!)where"0isanyexpressionofOS-type,"00isanyexpressionofAS-type,and!2isanycontextname.AFCA-system(ofsentences)isanyBooleancombinationofFCA-sentences.Denition11.Avaluationisamappingthatassigns{aset()toeveryname2,{aset()toeveryname2{aformalcontext(!)=(O(!);A(!);B(!))toeveryname!2,insuchawaythatthefollowingconditionshold:{forsetofobjects[!2O(!);{forsetofattributes[!2A(!);{foreveryname2,()[!2O(!);{foreveryname2,()[!2A(!).LetusextendvaluationsonFCA-expressionsinthefollowingnaturalway. Denition12.Object-settypeexpressions:{(S)=SforeverynitesubsetSof.{("#!)=(("))#(!)foreveryAS-typeexpression"andname!2.Attribute-settypeexpressions:{(S)=SforeverynitesubsetSof.{(""!)=(("))"(!)foreveryOS-typeexpression"andname!2.BothFCAtypes:("0"00)=("0)("00),("0["00)=("0)[("00),("0n"00)=("0)n("00).ThefollowingpropositioniseasytoprovebyinductiononstructureofFCA-Expressions.Proposition1.Foreveryvaluation,foreveryOS-typeandAS-typeFCA-expressionsandrespectively()[!2O(!),and()[!2A(!).ThispropositionleadstoopportunitytoextendvaluationsontoFCA-sentences.Denition13.EveryevaluationassignsBooleanvalue`true'or`false'toFCA-sentencesasfollows:1.(o2")=trueifo2(");otherwise(o2")=false;2.(a2")=trueifa2(");otherwise(a2")=false;3.("0"00)=trueif("0)("00);otherwise("0"00)=false;4.(("0;"00)FC(!))=trueif(("0);("00)isaformalconceptinaformalcontext(!);otherwise(("0;"00)FC(!))=false.WearereadytodenesatisabilityforFCA-systemsandFCArealizationprob-lem.Denition14.ForeveryevaluationandeveryFCA-system(ofsentences)let()beaBooleanvalue`true'or`false'computedaccordingtothestandardrulesfromvaluesofFCA-sentences.AnFCA-systemissaidtobesatisableifthereexistsanevaluationsuchthat()=true.FCArealizationproblemisanalgorithmicproblemtocheckforinputFCA-systemwhetheritissatisableornot.Proposition2.FCArealizationproblemisdecidable.Proof.LetbeaninputFCA-system.SinceisaBooleancombinationofFCA-sentences,itcanbetransformedtoequivalentsystembutinadisjunctiveWVnormalformi2:::(j2:::(i;j))whereall(i;j)areVFCA-sentencesortheirnega-tions.Henceissatisableianyconjunction(j2:::(i;j))issatisable.SowemayassumethatisaconjunctionofFCA-sentencesortheirnegations.ButFCArealizationforasystemofthiskindiseasytoreducetoconsistencyofALBOknowledgebase,thatisaknowndecidableproblem(Fact2).Avariantofreductionispresentedbelow. Letalphabetofobjectsymbolsconsistsofallelementsin[,LetalphabetofconceptsymbolsconsistsofallO!andA!forall!2.LetalphabetofrolesymbolsconsistsofallB!forall!2.ObservethatinthissyntaxeveryFCA-expressioncanbeconsideredasaconceptterm6.TheeveryFCA-sentenceoritsnegationcanbeconvertedtoequivalentterminologicalorassertionalsentencesasfollows:{o2"7!o:(t!2O!)u";:(o2")7!o:(t!2O!)u(:");{a2"7!a:(t!2A!)u";:(a2")7!a:(t!2A!)u(:");:{"0"007!"0v"00;:("0"00)7!x:("0u:("00)),where`x'isfreshobjectsymbol;::{("0;"00)FC(!)7!("0vO;"00vA;("0)"B!=:"00);("00)#B!=:"0).!!InthiswaywecanconvertanyconjunctionofFCA-sentencesandtheirnega-tionstosomeALBO/FCAknowledgebasewhichequivalentwithrespecttosatisability.ButALBO/FCAisALBO(";#)whichinturnisexpressibleinALBO(:;)=ALBO.ButALBO-consistencyproblemisdecidable(seeFact2).Itnishestheproof.Unfortunately,ourdecisionprocedure(thatissketchedintheproofofpropo-sition2)isextremelyinecientandimpractical:wereducetheproblemtoex-ponentialnumberofinstancesofALBO-satisabilityproblem,whichisknowntobeNExp-Time-complete[4].References1.BaaderF.,D.Calvanese,D.NardiD.McGuinness,andP.Patel-Schneider,editors.TheDescriptionLogicHandbook:Theory,ImplementationandApplications.Cam-bridgeUniversityPress,2003.2.GanterB.,WilleR.FormalConceptAnalysis.MathematicalFoundations.SpringerVerlag,1996.3.Schmidt-SchauM.,andSmolkaG.Attributiveconceptdescriptionswithcomple-ments.J.ArticialIntelligence,Vol.48,1991,pp.1-26.4.SchmidtR.A.,TishkovskyD.UsingTableautoDecideExpressiveDescriptionLogicswithRoleNegation.TheSemanticWeb.Proceedingsof6thInternationalSemanticWebConferenceand2ndAsianSemanticWebConference.SpringerLectureNotesinComputerScience,v.4825,2007,p.438-451.5.ShilovN.V.GaraninaN.O.,AnureevI.S.CombiningTwoFormalismforReasoningaboutConcepts.Proceedingsofthe2007InternationalWorkshoponDescriptionLogics(DL2007),BrixenItaly,2007.CEURWorkshopProceedingsv.250.p.459-466.6Itissucienttoreplace`',`['and`n'by`u',`t'and`u:'.