Inductive Logic Programming

Thisvolumecontainsoneinvitedand?fteensubmittedpaperspresentedatthe Tenth International Conference on Inductive Logic Programming (ILP2000). The?fteenacceptedpaperswereselectedbytheprogramcommitteefromthe 37paperssubmittedtotheconference. Eachpaperwascarefullyreviewedby threereferees. ILP2000washeldatImperialCollege,London,24-27July2000andwasin- grated with the First International Conference on Computational Logic (CL2000). With ILP's strong roots in computational logic, this was a na- ralmarriage. CL2000wasa?ve-dayextravaganza,incorporatingboththeSixth InternationalConferenceonRulesandObjectsinDatabases(DOOD2000)and theTenthInternationalWorkshoponLogic-basedProgramSynthesisandTra- formation(LOPSTR2000)andfeaturingeightinvitedspeakers,twelvetutorials, andsevena?liatedworkshops. RegistrantsforCL2000andILP2000couldmove freelybetweenthetwoevents,themaindistinctionbetweentheeventsbeings- arateconferenceproceedings. WewishtothankalltheauthorswhosubmittedtheirpaperstoILP2000; theprogramcommitteemembers,andotherreviewerswhodidathoroughjobin spiteofdemandingdeadlines;andourinvitedspeaker,DavidPage.Thanksalso toAlfredHofmann,andeveryoneelseatSpringerfortheirsmoothhandlingof theseproceedings. WewouldalsoliketothanktheorganisersofCL2000,whose cooperation brought the two events together: John Lloyd (Program Chair), Marek Sergot (Conference Chair), Frank Kriwaczek and Francesca Toni (- calOrganisers),FemkevanRaamsdonk(PublicityChair)andSandroEtalle (Workshop Chair). Finally, we are grateful to our sponsors for their ?nancial support. May2000 JamesCussens&AlanFrisch ProgramChairs ILP2000 ILP2000 Program Committee HenrikBostrom(UniversityofStockholm,Sweden) IvanBratko(UniversityofLjubljana,Slovenia) JamesCussens(UniversityofYork,UK) Shan-HweiNienhuys-Cheng(UniversityofRotterdam,Netherlands) WilliamCohen(WhizbangsLabs,USA) LucDeRaedt(UniversityofFreiburg,Germany) Sa?soD?zeroski(Jo?zefStefanInstitute,Ljubljana) PeterFlach(UniversityofBristol,UK) AlanFrisch(UniversityofYork,UK) KoichiFurukawa(UniversityofKeio,Japan) RoniKhardon(UniversityofEdinburgh,UK) Jorg-UweKietz(SwissLife,Switzerland) NadaLavra?c(Jo?zefStefanInstitute,Slovenia) JohnLloyd(AustralianNationalUniversity,Australia) StanMatwin(UniversityofOttawa,Canada) RaymondMooney(UniversityofTexas,USA) StephenMuggleton(UniversityofYork,UK) DavidPage(UniversityofWisconsin,USA) BernhardPfahringer(UniversityofWaikato,NewZealand) C'elineRouveirol(Universit'edeParis-Sud,France) ClaudeSammut(UniversityofNewSouthWales,Australia) ' Mich'eleSebag(EcolePolytechnique,France) AshwinSrinivasan(UniversityofOxford,UK) PrasadTadepalli(OregonStateUniversity,USA) StefanWrobel(UniversityofMagdeburg,Germany) AkihiroYamamoto(UniversityofHokkaido,Japan) Additional Referees ' ErickAlphonse(Universit'edeParis-Sud,France) LiviuBadea(NationalInstituteforResearchandDevelopmentinInformatics, Romania) DamjanDemsar(Jo?zefStefanInstitute,Slovenia) ElisabethGoncalves(Universit'edeParis-Sud,France) MarkoGrobelnik(Jo?zefStefanInstitute,Slovenia) ClaireKennedy(UniversityofBristol,UK) DanielKudenko(UniversityofYork,UK) JohanneMorin(UniversityofOttawa,Canada) TomonobuOzaki(KeioUniversity,Japan) EdwardRoss(UniversityofBristol,UK) LjupcoTodorovski(Jo?zefStefanInstitute,Slovenia) V'eroniqueVentos(Universit'edeParis-Sud,France) VIII ProgramCommitteeandReferees Sponsors of ILP2000 ILPNet2,TheEuropeanNetworkofExcellenceinInductiveLogicProgramming MLNet,TheEuropeanNetworkofExcellenceinMachineLearning CompulogNet,TheEuropeanNetworkofExcellenceinComputationalLogic Table of Contents IInvitedPaper ILP:JustDoIt...3 DavidPage II Contributed Papers ANewAlgorithmforLearningRangeRestrictedHornExpressions...21 MartaArias,RoniKhardon ARe?nementOperatorforDescriptionLogics...40 LiviuBadea,Shan-HweiNienhuys-Cheng ExecutingQueryPacksinILP ...60 HendrikBlockeel,LucDehaspe,BartDemoen,GerdaJanssens, JanRamon,HenkVandecasteele ALogicalDatabaseMiningQueryLanguage ...78 LucDeRaedt Induction of Recursive Theories in the Normal ILP Setting: Issues and Solutions ...93 FlorianaEsposito,DonatoMalerba,FrancescaA.Lisi ExtendingK-MeansClusteringtoFirst-OrderRepresentations...112 MathiasKirsten,StefanWrobel TheoryCompletionUsingInverseEntailment ...130 StephenH. Muggleton,ChristopherH. Bryant SolvingSelectionProblemsUsingPreferenceRelationBasedonBayesian Learning...147 TomofumiNakano,NobuhiroInuzuka ConcurrentExecutionofOptimalHypothesisSearchforInverse Entailment...165 HayatoOhwada,HiroyukiNishiyama,FumioMizoguchi UsingILPtoImprovePlanninginHierarchicalReinforcementLearning...174 MarkReid,MalcolmRyan X TableofContents TowardsLearninginCARIN-ALN...191 C'elineRouveirol,V'eroniqueVentos InverseEntailmentinNonmonotonicLogicPrograms...209 ChiakiSakama ANoteonTwoSimpleTransformationsforImprovingtheE?ciencyofan ILPSystem ...225 V'?torSantosCosta,AshwinSrinivasan,RuiCamacho SearchingtheSubsumptionLatticebyaGeneticAlgorithm ...243 AlirezaTamaddoni-Nezhad,StephenH. Muggleton NewConditionsfortheExistenceofLeastGeneralizationsunderRelative Subsumption...253 AkihiroYamamoto Author Index ...265 ILP:JustDoIt DavidPage Dept. ofBiostatisticsandMedicalInformatics andDept. ofComputerSciences UniversityofWisconsin 1300UniversityAve. ,Rm5795MedicalSciences Madison,WI53706 U. S. A. page@biostat. wisc. edu Abstract.Inductivelogicprogramming(ILP)isbuiltonafoundation laidbyresearchinotherareasofcomputationallogic. Butinspiteofthis strongfoundation,at10yearsofageILPnowfacesanumberofnewch- lengesbroughtonbyexcitingapplicationopportunities.