Lecture Notes in Computer Science 7265 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany MadhuSudan MicrosoftResearch,Cambridge,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum MaxPlanckInstituteforInformatics,Saarbruecken,Germany Esra Erdem Joohyung Lee Yuliya Lierler David Pearce (Eds.) Correct Reasoning Essays on Logic-Based AI in Honor of Vladimir Lifschitz 1 3 VolumeEditors EsraErdem SabanciUniversity FacultyofEngineeringandNaturalSciences Orhanli,Tuzla34956,Istanbul,Turkey E-mail:[email protected] JoohyungLee ArizonaStateUniversity SchoolofComputing,InformaticsandDecisionSystemsEngineering P.O.Box878809,Tempe,AZ85287,USA E-mail:[email protected] YuliyaLierler UniversityofKentucky DepartmentofComputerScience 329RoseStreet,Lexington,KY40506,USA E-mail:[email protected] DavidPearce PolitechnicalUniversityofMadrid DepartmentofArtificialIntelligence CampusdeMontegancedo,28660BoadilladelMonte,Madrid,Spain E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-642-30742-3 e-ISBN978-3-642-30743-0 DOI10.1007/978-3-642-30743-0 SpringerHeidelbergDordrechtLondonNewYork LibraryofCongressControlNumber:2012938501 CRSubjectClassification(1998):F.4.1,I.2,F.3,I.2.3,D.2.4,F.4 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©Springer-VerlagBerlinHeidelberg2012 Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply, evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelaws andregulationsandthereforefreeforgeneraluse. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Vladimir Lifschitz Preface Vladimir Lifschitz was born in Moscow, Russia, on May 30, 1947. The present volumeisaFestschriftinhishonortocelebratethe65thbirthdayofanoutstand- ing scholar of computer science, logic and artificial intelligence. It comprises 44 contributions by no less than 87 authors. They include many of Vladimir’s stu- dents, colleagues, co-authors and friends. Their topics cover many of the scien- tific areas where Vladimir has made a lasting and profound contribution: logic programming,circumscription,defaultlogic,actiontheory,planning,causalrea- soning and of course answer set programming. OnapproachingscholarstocontributetothisFestschrift,wereceivedanover- whelming,positiveresponse.ItbecameclearthatVladimirisadmired,likedand heldinesteemthroughoutthescientificcommunitytheworldover.Theenthusi- asm with which authors responded to our request was delightful and infectious. It became clear that we could have produced several volumes of this size, and only time and practicalconcernspreventedus fromdoing so.We heartily thank allthe contributorsfor their fine efforts,andwe apologizesincerely to the many colleaguesthat we werenotable to approach.We areespecially gratefulto Jack MinkerforcontributingapersonalpieceonVladimir’slifeandwork.Thereader will also find a collection of personal reminiscences on Vladimir Lifschitz as teacher, as lived by his students. Our warm thanks also go to Springer for their support of this initiative and the editorial process. We shall not dwell further here on the scientific achievements of Vladimir Lifschitz the scholar, since they are visible time and again in the pages that follow. For Vladimir Lifschitz, colleague and friend, we close by wishing you a very happy 65th birthday! We are sure we speak on behalf of all the present contributorsinwishingyoumanymoreyearsinthebusinessofcorrectreasoning. March 2012 Esra Erdem Joohyung Lee Yuliya Lierler David Pearce Table of Contents To Vladimir Lifschitz on His 65th Birthday.......................... 1 Jack Minker Vladimir Lifschitz — A Youth at 65................................ 14 Neelakantan Kartha, Esra Erdem, Joohyung Lee, Paolo Ferraris, Wanwan Ren, Yuliya Lierler, Fangkai Yang, and Albert Rondan A “Conservative” Approach to Extending Answer Set Programming with Non-Herbrand Functions ..................................... 24 Marcello Balduccini The Inverse Lambda Calculus Algorithm for Typed First Order Logic Lambda Calculus and Its Application to Translating English to FOL ... 40 Chitta Baral, Marcos Alvarez Gonzalez, and Aaron Gottesman ParameterizedSplitting: A Simple Modification-Based Approach....... 57 Ringo Baumann, Gerhard Brewka, Wolfgang Dvoˇra´k, and Stefan Woltran From Primal Infon Logic with Individual Variables to Datalog ......... 72 Nikolaj Bjørner, Guido de Caso, and Yuri Gurevich Here and There Among Logics for Logic Programming................ 87 Alexander Bochman Causal Logic Programming........................................ 102 Pedro Cabalar On the Interaction of Existential Rules and Equality Constraints in Ontology Querying............................................... 117 Andrea Cal`ı, Georg Gottlob, Giorgio Orsi, and Andreas Pieris Extending Action Language C+ by Formalizing Composite Actions..... 134 Xiaoping Chen, Guoqiang Jin, and Fangkai Yang Strong Equivalence of RASP Programs ............................. 149 Stefania Costantini, Andrea Formisano, and David Pearce Considerations on Belief Revision in an Action Theory................ 164 James Delgrande Approximation Fixpoint Theory and the Semantics of Logic and Answers Set Programs............................................ 178 Marc Denecker, Maurice Bruynooghe, and Joost Vennekens X Table of Contents Privacy Preservation Using Multi-context Systems and Default Logic ... 195 Ju¨rgen Dix, Wolfgang Faber, and V.S. Subrahmanian Simulating Production Rules Using ACTHEX ....................... 211 Thomas Eiter, Cristina Feier, and Michael Fink Applications of Action Languages in Cognitive Robotics .............. 229 Esra Erdem and Volkan Patoglu The Intelligent Grounder of DLV................................... 247 Wolfgang Faber, Nicola Leone, and Simona Perri Bi-state Logic ................................................... 265 Luis Farin˜as del Cerro, David Pearce, and Agust´ın Valverde An Equational Approach to Logic Programming ..................... 279 Dov M. Gabbay Gearing Up for Effective ASP Planning ............................. 296 Martin Gebser, Roland Kaufmann, and Torsten Schaub Toward Question Answering in Travel Domains ...................... 311 Yana Todorova and Michael Gelfond Algorithms for Solving Satisfiability Problems with Qualitative Preferences...................................................... 327 Enrico Giunchiglia and Marco Maratea Oscillating Behavior of Logic Programs ............................. 345 Katsumi Inoue and Chiaki Sakama Applying Visible Strong Equivalence in Answer-Set Program Transformations ................................................. 363 Tomi Janhunen and Ilkka Niemela¨ From Turner’s Logic of Universal Causation to the Logic of GK........ 380 Jianmin Ji and Fangzhen Lin Lifschitz and Circumscription...................................... 386 Neelakantan Kartha Towards Formalizing Non-monotonic Reasoning in Physics: Logical ApproachBased on PhysicalInduction and Its Relation to Kolmogorov Complexity ..................................................... 390 Vladik Kreinovich Reformulating Action Language C+ in Answer Set Programming....... 405 Joohyung Lee The Truth about Defaults......................................... 422 Hector J. Levesque and Gerhard Lakemeyer Table of Contents XI Parsing Combinatory Categorial Grammar via Planning in Answer Set Programming.................................................... 436 Yuliya Lierler and Peter Schu¨ller Declarative Distributed Computing................................. 454 Jorge Lobo, Jiefei Ma, Alessandra Russo, and Franck Le Disjunctive Programs with Set Constraints.......................... 471 Victor W. Marek and Jeffrey B. Remmel The G¨odel-Tarski Translations of Intuitionistic Propositional Formulas........................................................ 487 Grigori Mints Stepwise Debugging of Description-Logic Programs................... 492 Johannes Oetsch, Jo¨rg Pu¨hrer, and Hans Tompits Answer Set Programming and Planning with Knowledge and World-Altering Actions in Multiple Agent Domains .................. 509 Enrico Pontelli, Tran Cao Son, Chitta Baral, and Gregory Gelfond A Language for Default Reasoning about Actions .................... 527 Hannes Strass and Michael Thielscher Connecting First-Order ASP and the Logic FO(ID) through Reducts ... 543 Miroslaw Truszczynski A New Incarnation of Action Language H........................... 560 Sandeep Chintabathina and Richard Watson Well-Supported Semantics for Logic Programs with Generalized Rules........................................................... 576 Jia-Huai You, Yi-Dong Shen, and Kewen Wang Author Index.................................................. 593 To Vladimir Lifschitz on His 65th Birthday JackMinker DepartmentofComputerScienceand InstituteforAdvancedComputerStudies, UniversityofMaryland, CollegePark,Maryland20742 1 Introduction IamhonoredtohavebeeninvitedbytheeditorsofthisFestschrifttowriteanarticlein honorofVladimirLifschitzontheoccasionofhis65thbirthday.InthisarticleIdescribe some of the major contributions that Vladimir has made in his exceptional career. I providebackgroundmaterialaboutVladimirintheFormerSovietUnion(FSU),where hewasborn;discusshisbeginningyearsintheUnitedStates(US);howIbecameaware ofhisresearch;hisworkonstablemodelswithMichaelGelfond,andsomeofmywork in related areas; and describe some of the many contributions Vladimir has made in formalizingadhocapproachesinartificialintelligencetoaformalbasisoflogic-based analysis. 2 VladimirLifschitzinthe SovietUnion Vladimir Lifschitz was born in Moscow in the Former Union of Soviet Socialist Re- publics (USSR) on May 30, 1947 to Jewish parents. His family moved to Leningrad whenhewasfive.TheUSSRhadalonghistoryofdiscriminationagainsttheirJewish citizensnotonlybyUSSRcitizens,butbythestateasawhole.Thisbecameespecially severeundertheregimeofJosephStalinwho,in1922,wonthemostpowerfulpostin theUSSR, generalsecretaryoftheparty.His reignlasteduntilMarch5,1953.Under Stalin,thousandsUSSRcitizenshadbeenbrutallykilledbyordersofthestatewithout legalprocess,andmillionsincarceratedwithoutdueprocess. FollowingthedeathofStalin,subsequentgeneralsecretariesofthepartywereless brutal. However state anti-Semitism still existed. Jewish students were discriminated againstandwerepreventedfromattendingthebestuniversities.Vladimirwastoogood ascholartobedeniedentrytooneofthebestuniversitiesintheUSSR,andwasaccepted to Leningrad State University in 1963. In fact, he was a kind of ”child prodigy”: he learnedcalculusonhisown,andauditedadvancedcollegecourses,whenhewasinhigh school.Attheageof19,hepresentedhisoriginalresearchattheInternationalCongress of Mathematicians in Moscow, and he published nine more papers on mathematical logicduringthenextthreeyears.FatewouldhaveitthatMichaelGelfond,alsoenrolled at the same time and bothmajoredin mathematics.Theytook manycoursestogether andbecamefriendsforever. Whilestillanundergraduatestudent,Vladimirmetacharmingandintelligentyoung woman, Elena Donskaya at a holiday resort for writers and their families where they E.Erdemetal.(Eds.):CorrectReasoning,LNCS7265,pp.1–13,2012. (cid:2)c Springer-VerlagBerlinHeidelberg2012 2 J.Minker spentsometimeduringwinterbreak.ElenawasalsoastudentatLeningradUniversity and studied English literature. Vladimir’s father was a famous playwrightwho wrote underthe name AlexanderVolodin.His motherhad a degree in chemistry.Elena and Vladimirwere marriedwhenVladimir was20 yearsold.Theyhavea son Alexander, andagranddaughterSonya. As a high schoolstudent, Vladimir attended seminars and discussions of the logic group at the famous Steklov Mathematical Institute in Leningrad. The Steklov Insti- tute was known for its work in mathematical logic and mechanical theorem proving. In 1968, under the direction of the famous logician Nikolai Alexandrovich Shanin, Vladimir completed and defended his thesis, ”Constructive Counterparts of Go¨del’s Completeness Theorem.” In spite of anti-Semitism, he was able to find eventually a reallygoodpositionataresearchinstituteoftheAcademyofSciencesinLeningrad. ElenarecallstheirdecisiontoemigratefromtheUSSRasfollows Themainreasonwhywe decidedtoemigratewasourgeneraldisgustforthe totalitarian Soviet system, our desire to live as free people. There were two choicesthere:eithertorepeatslavishlytheliesoftheofficialpropagandaorto become outspokendissidents and to spend years in prisonsand labor camps. We didn’t like either option, and this is why we chose the difficult path of emigration. In1974,VladimirandElenaappliedforanexitvisaandbecamerefuseniks.Arefusenik isgenerallyaJewishpersonintheUSSRwhowasdeniedanexitvisa.Accordingtothe UniversalDeclarationofHumanRightspassedbytheUnitedNationsonDecember10, 1948,everyindividualhastherighttoleavetheircountry.VladimirandElenareceived theirexitvisain1976andimmigratedtotheUS.Atthetimetheyapplied,Vladimirwas employed. When someone in the USSR applied for an exit visa, they were generally dismissed from their job. However, Vladimir decided to leave on his own terms and resigned.Hedidnotwanttocausetroubleforthosewhohadhiredhim.Hisboss,Boris Pittel,eventuallyimmigratedtotheUSwhereVladimirwroteseveralpaperswithhim. 3 VladimirLifschitz’s Early Yearsinthe United States After Vladimir arrived in the US in 1976, he was fortunate to find a temporary posi- tion at Stanford University working with Patrick Suppeson computer-aidedlearning. In1977hefoundatwoyearpositionatBrighamYoungUniversityintheMathematics Department as an assistant professor. In 1979 he found a tenure track position as an assistantprofessorintheMathematicsDepartmentattheUniversityofTexas,ElPaso (UTEP).ShortlyafterVladimirwasatUTEP,hewasinstrumentalinattractingMichael to UTEP. As with many universities at that time, UTEP had a computer science pro- gram as part of its mathematics departmentand decided to upgrade the programto a Departmentof Computer Science. Michael and Vladimir contributed to developinga PlanofOrganizationforthenewdepartmentandwereamongitsfirstmembers. Since Vladimir was in a computer science department, he decided to broaden his knowledge in computers. While he was at UTEP, he enrolled in a summer course in computerscienceandartificialintelligence(AI)offeredatStanfordUniversity.Oneof