Logic Programming and Nonmonotonic Reasoning

ThesearetheproceedingsoftheSixthInternationalConferenceonLogicP- grammingandNonmonotonicReasoning (LPNMR2001). The conference was heldinViennafrom17thto19thofSeptember,2001. Itwascollocatedwiththe JointGerman/AustrianConferenceonArti?cialIntelligence(24thGerman/9th AustrianConferenceonArti?cialIntelligence),KI2001. LPNMR conferences aim to promote research in logic-based programming languages, database systems, nonmonotonic reasoning, and knowledge rep- sentation. LPNMR2001 was the sixth conference in the series. The previous meetingswereheldinWashington,DC,in1991,inLisbon,Portugal,in1993,in Lexington,Kentucky,in1995,inDagstuhl,Germany,in1997,andinElPaso, Texas,in1999. ThetechnicalprogramofLPNMR2001wascomprisedof?veinvitedtalks thatweregivenbyJur ¨ genDix,GeorgGottlob,PhokionKolaitis,MaurizioLe- erini,andChiakiSakama. Italsocontained23technicalpresentationsselected bytheprogramcommitteeduringarigorousreviewprocess. Finally,asapart ofthetechnicalprogram,theconferencefeaturedaspecialsessioncomprisedof ninepresentationsanddemonstrationsofimplementednonmonotonicreasoning systems. Allthesecontributionsareincludedintheproceedings. Many individuals workedfor the success of the conference. Special thanks areduetoallmembersoftheprogramcommitteeandtoadditionalreviewers fortheire?ortstoproducefairandthoroughevaluationsofsubmittedpapers. Furthermore, we would like to thank the members of the Knowledge Based SystemsGroupoftheViennaUniversityofTechnology,whichtookcareofthe localorganization. Weparticularlyappreciatedthenevertiringe?ortofElfriede Nedoma,secretarytothegroup. WewouldalsoliketothankGerdBrewkafor hissupportiveroleinarrangingthecollocationoftheconferencewithKI2001. Last,butnotleast,wethankthesponsoringinstitutionsfortheirgenerosity. September2001 ThomasEiter WolfgangFaber Miros lawTruszczynski ´ Conference Organization ProgramCo-chairs ThomasEiter(ViennaUniversityofTechnology,Austria) Miros lawTruszczynski ´ (UniversityofKentucky,USA) ProgramCommittee AlexanderBochman(HolonAcademicInstituteofTechnology,Israel) PieroBonatti(Universit` adegliStudiMilano/Crema,Italy) GerhardBrewka(UniversityofLeipzig,Germany) JamesDelgrande(SimonFraserUniversity,Canada) MarcDenecker(KatholiekeUniversiteitLeuven,Belgium) NormanFoo(UniversityofNewSouthWales,Australia) MichaelGelfond(TexasTechUniversity,USA) KatsumiInoue(KobeUniversity,Japan) AntonisKakas(UniversityofCyprus) NicolaLeone(Universit` adegliStudidellaCalabria,Italy) VladimirLifschitz(UniversityofTexasatAustin,USA) FangzhenLin(TheHongKongUniversityofScienceandTechnology,China) VictorMarek(UniversityofKentuckyatLexington,USA) ZhangMing-Yi(GuizhouAcademyofSciences,China) IlkkaNiemel¨ a(HelsinkiUniversityofTechnology,Finland) Lu´?sMonizPereira(UniversidadeNovadeLisboa,Portugal) MarcoSchaerf(Universitad ` iRoma“LaSapienza,”Italy) TorstenSchaub(UniversityofPotsdam,Germany) FrancescaToni(ImperialCollege,London,U. K. ) Li-YanYuan(UniversityofAlberta,Canada) Publicity Chair WolfgangFaber(ViennaUniversityofTechnology,Austria) Organization VII Additional Reviewers Jos´eAlferes MehmetOrgun CristinaBaroglio MauricePagnucco KrysiaBroda VivianaPatti MauriceBruynooghe NikolayPelov FrancescoBuccafurri GeraldPfeifer CarlosDam´asio FabrizioRiguzzi EmmanuelDeMot RiccardoRosati YannisDimopoulos GiulianaSabbatini EsraErdem FaribaSadri WolfgangFaber ChiakiSakama DayaGaur FrancescoScarcello JensHappe TommiSyrj¨anen TomiJanhunen AndreaTettamanzi JoohyungLee BertVanNu?elen NicolaLeone HelmutVeith ThomasLinke GerardVreeswijk ThomasLukasiewicz KewenWang PaoloMancarella Jia-HuaiYou CristinelMateis DongmoZhang RobMiller Sponsoring Institutions We would like to acknowledge ?nancial support for the conference from the EuropeanO?ceofAerospaceResearchandDevelopment(EOARD),underc- tractF61775-01-WF077,theAustrianComputerSociety(OCG),theEuropean Commission,theAustrianMinistryofTransport,Innovation&Technology,and Microsoft. Table of Contents Invited Papers AComputationalLogicApproachtoHeterogenousAgentSystems . . . . . . . . . . 1 J¨urgenDix DeclarativeInformationExtraction,WebCrawling, andRecursiveWrappingwithLixto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 RobertBaumgartner,SergioFlesca,andGeorgGottlob OntheComplexityofModelCheckingandInference inMinimalModels(ExtendedAbstract) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 LefterisM. KirousisandPhokionG. Kolaitis DataIntegrationNeedsReasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 MaurizioLenzerini NonmonotonicInductiveLogicProgramming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 ChiakiSakama Regular Papers StrongEquivalenceforLogicPrograms andDefaultTheories(MadeEasy). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 HudsonTurner OntheE?ectofDefaultNegationontheExpressiveness ofDisjunctiveRules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 TomiJanhunen OntheExpressibilityofStableLogicProgramming . . . . . . . . . . . . . . . . . . . . . . . 107 V. W. MarekandJ. B. Remmel OntheRelationshipbetweenDefeasibleLogic andWell-FoundedSemantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 GerhardBrewka AComparativeStudyofWell-FoundedSemantics forDisjunctiveLogicPrograms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 KewenWang ReasoningwithOpenLogicPrograms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 PieroA. Bonatti RepresentationofIncompleteKnowledgebyInduction ofDefaultTheories. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .