Andrei Voronkov – författare

Handbook of Automated Reasoning

Handbook of Automated Reasoning - Vol 2

This book constitutes the refereed proceedings of the 12th International Andrei P. Ershov Informatics Conference, PSI 2019, held in Novosibirsk, Russia, in July 2019.The 18 full papers and 3 short papers presented in this volume were carefully reviewed and selected from 70 submissions. The papers cover various topics related to the Mathematics of Computing, Information Systems, Formal Languages, dependable and fault-tolerant Systems and Network, Automata Theory,  and much more.

This book constitutes the refereed proceedings of the 12th International Andrei P. Ershov Informatics Conference, PSI 2019, held in Novosibirsk, Russia, in July 2019.The 18 full papers and 3 short papers presented in this volume were carefully reviewed and selected from 70 submissions. The papers cover various topics related to the Mathematics of Computing, Information Systems, Formal Languages, dependable and fault-tolerant Systems and Network, Automata Theory,  and much more.

This book constitutes the refereed proceedings of the 10th International Andrei Ershov Informatics Conference, PSI 2015, held in Kazan and Innopolis, Russia, in August 2015. The 2 invited and 23 full papers presented in this volume were carefully reviewed and selected from 56 submissions. The papers cover various topics related to the foundations of program and system development and analysis, programming methodology and software engineering and information technologies.

This book constitutes the refereed proceedings of the 11th International Andrei P. Ershov Informatics Conference, PSI 2017, held in Moscow, Russia, in June 2017.  The 31 full papers presented in this volume were carefully reviewed and selected from 57 submissions. The papers cover various topics related to the foundations of program and system development and analysis, programming methodology and software engineering and information technologies.

This book constitutes the refereed proceedings of the 11th International Andrei P. Ershov Informatics Conference, PSI 2017, held in Moscow, Russia, in June 2017.

 

The 31 full papers presented in this volume were carefully reviewed and selected from 57 submissions. The papers cover various topics related to the foundations of program and system development and analysis, programming methodology and software engineering and information technologies.

ThisvolumecontainsthepaperspresentedattheNinthInternationalC- ferenceonLogicforProgramming,Arti?cialIntelligence,andReasoning(LPAR 2002),heldonOctober14-18,2002,attheUniversityofTbilisi(Georgia),- getherwiththeThirdInternationalWorkshoponImplementationofLogics. Therewere68submissions,ofwhicheightbelongedtothespecialsubmission categoryofexperimentalpapers,intendedtodescribeimplementationsorc- parisonsofsystems,orexperimentswithsystems. Eachsubmissionwasreviewed byatleastthreeprogramcommitteemembersandanelectronicprogramc- mitteemeetingwasheldviatheInternet. Thenumberofsubmissionsandshort reviewingperiodcausedalargeamountofwork,andweareverygratefultothe other22PCmembersfortheire?ciencyandforthequalityoftheirreviewsand discussions. Finally,thecommitteedecidedtoaccept30papers. Theprogramme alsoincludesthreeinvitedlecturesandapostersession. Apartfromtheprogrammecomittee,wewouldalsoliketothanktheother people who made LPAR 2002 possible: the additional referees, and the local arrangementschairsKhimuriRhukia,KotePhakadze,GelaChankvetadze,and JemalAntidze. TheInternet-basedsubmissionsoftwareandtheprogramcommitteedisc- sionsoftwarewereprovidedbythesecondco-chair.August2002 MatthiasBaaz AndreiVoronkov ConferenceOrganization ProgramChairs MatthiasBaaz(TechnischeUniversit..atWien) AndreiVoronkov(UniversityofManchester) ProgramCommittee ElviraAlbert(UniversidadPolitecnicadeValencia) FranzBaader(TechnischeUniversit..atDresden) MauriceBruynooghe(KatholiekeUniversiteitLeuven) PatrickCousot(ENSParis) MaartendeRijke(UniversityofAmsterdam) HaraldGanzinger(Max-PlanckInstitut,Saarbruc ..ken) JeanGoubault-Larrecq(ENSdeCachan) MikiHermann(EcolePolytechnique) MatejaJamnik(UniversityofCambridge) NeilJones(KobenhavnsUniversitet) DeepakKapur(UniversityofNewMexico) MaurizioLenzerini(Universit'adiRoma"LaSapienza") GiorgioLevi(Universit'adiPisa) LeonidLibkin(UniversityofToronto) RobertNieuwenhuis(TechnicalUniversityofCatalonia) LeszekPacholski(WroclawskiUniwersytet) MichelParigot(Universit'eParis7) PavelPudlak(MathematicalInstitute,Prague) CarstenSchuermann(YaleUniversity) J..orgSiekmann(DFKISaarbruc ..ken) WolfgangThomas(RWTHAachen) MichaelZakharyaschev(King'sCollege) LocalOrganization KhimuriRhukia KotePhakadze GelaChankvetadze JemalAntidze VIII ConferenceOrganization ListofReferees GianlucaAmato CarlosAreces M.Arenas OferArieli RobertoBarbuti ChristophBenzmueller MartaBilkova BrunoBlanchet AlexandreBoisseau AhmedBouajjani DmitriChubarov PabloCordero VeroniqueCortier AgostinoDovier RachidEchahed MorenoFalaschi C'esarFerri OlivierGasquet BernhardGramlich Jos'eManuelG'omez PhilippedeGroote RainerHaehnle JiriHanika JuanHeguiabehere JoseHernandez-Orallo ThomasHillenbrand JoeHurd EmilJerabek ValentinJijkoun KonstantinKorovin G. Lakemeyer DominiqueLarchey-Wendling OlivierLaurent StefanLeue LuigiLiquori ChristofLoeding CarstenLutz ChristopherLynch PatrickMaier PaoloMancarella FlorenceMaraninchi MaartenMarx Jesus ' Medina EricaMelis AntoineMin'e RalfM..oller PaulinDeNaurois HansdeNivelle MichaelNorrish ManuelOjeda-Aciego NikolayPelov GuyPerrier ReinhardPichler ChristopherPollett Germ'anPuebla Jean-PierreRessayre ChristianRetor'e AlexandreRiazanov MichalRossler PaulRozi'ere NikitaSakhanenko UlrikeSattler StefanSchlobach ManfredSchmidt-Schauss KonradSlind Anni-YasminTurhan ChristianUrban WimVanhoof YdeVenema So?eVerbaeten UweWaldmann KlausWeich ClausPeterWirth StefanWoehrle ConferenceOrganization IX ConferencesprecedingLPAR2001 RCLP'90,Irkutsk,SovietUnion RCLP'91,Leningrad,SovietUnion,aboardtheship"MichailLomonosov" LPAR'92,St. Petersburg,Russia,aboardtheship"MichailLomonosov" LPAR'93,St. Petersburg,Russia LPAR'94,Kiev,Ukraine,aboardtheship"MarshalKoshevoi" LPAR'99,Tbilisi,RepublicofGeorgia LPAR2000,ReunionIsland,France LPAR2001,Havana,Cuba TableofContents ImprovingOn-DemandStrategyAnnotations ...1 M. Alpuente,S. Escobar,B. Gramlich,S. Lucas First-OrderLogicasaConstraintProgrammingLanguage...19 K. R. Apt,C. F. M. Vermeulen MaintenanceofFormalSoftwareDevelopmentsby Strati?edVeri?cation...36 SergeAutexier,DieterHutter ANoteonUniversalMeasuresforWeakImplicit ComputationalComplexity ...53 ArnoldBeckmann ExtendingCompositionalMessageSequenceGraphs...68 BenediktBollig,MartinLeucker,PhilippLucas SearchingforInvariantsUsingTemporalResolution ...86 JamesBrotherston,AnatoliDegtyarev,MichaelFisher, AlexeiLisitsa ProofPlanningforFeatureInteractions:APreliminaryReport...102 ClaudioCastellini,AlanSmaill AnExtensionofBDI withFunctional CTL DependenciesandComponents...115 MehdiDastani,LeendertvanderTorre BindingLogic:ProofsandModels ...130 GillesDowek,Th'er'eseHardin,ClaudeKirchner DirectedAutomatedTheoremProving...145 StefanEdelkamp,PeterLeven AFrameworkforSplittingBDIAgents...160 XiaocongFan,JohnYen OntheComplexityofDisjunctionandExplicitDe?nability PropertiesinSomeIntermediateLogics...175 MauroFerrari,CamilloFiorentini,GuidoFiorino UsingBDDswithCombinationsofTheories ...190 PascalFontaine,E. PascalGribomont XII TableofContents OnExpressiveDescriptionLogicswithCompositionofRolesin NumberRestrictions...202 FabioGrandi QueryOptimizationofDisjunctiveDatabaseswithConstraints throughBindingPropagation ...216 GianluigiGreco,SergioGreco,IrinaTrubtsyna,EsterZumpano ANon-commutativeExtensionofMELL...231 AlessioGuglielmi,LutzStrassburger ProceduralSemanticsforFuzzyDisjunctivePrograms...247 Du?sanGuller PushdownSpeci?cations...262 OrnaKupferman,NirPiterman,MosheY. Vardi TheoremProvingwithSequenceVariablesandFlexible AritySymbols...

ThisvolumecontainsthepaperspresentedattheTenthInternationalConference on Logic for Programming, Arti?cial Intelligence, and Reasoning (LPAR 2003), heldonSeptember22-26,2003,inAlmaty,Kazakhstan,togetherwiththeFourth International Workshop on Implementation of Logics. There were 65 submissions, of which 8 belonged to the special submission category of experimental papers, intended to describe implementations or c- parisons of systems, or experiments with systems. Each submission was reviewed by at least three program committee members and an electronic program c- mitteemeetingwasheldviatheInternet.Weareverygratefultothe32program committee members for their e?orts and for the quality of their reviews and d- cussions. Finally, the committee decided to accept 27 papers. The program also included ?ve invited talks, by Franz Baader, Serikzhan Badaev, Dexter Kozen, Sergei Goncharov, and Thomas Wilke. Apart from the program committee, we would also like to thank the other people who have made LPAR 2003 possible: the external reviewers and the local organizers Serikzhan Badaev and Anna Romina.The Internet-based submission software and the program-committee disc- sion software were provided by the second co-chair.

This volume contains the papers presented at the 11th International Conference on Logic for Programming, Arti?cial Intelligence, and Reasoning (LPAR), held from March 14 to 18, 2005, in Montevideo, Uruguay, together with the 5th - ternational Workshop on the Implementation of Logics (organized by Stephan Schulz and Boris Konev) and the Workshop on Analytic Proof Systems (or- nized by Matthias Baaz). The call for papers attracted 77 paper submissions, each of which was - viewed by at least three expert reviewers. The ?nal decisions on the papers were taken during an electronic Program Committee meeting held on the Internet. The Internet-based submission, reviewing, and discussion software EasyChair, provided by the second PC co-chair, supported each stage of the reviewing p- cess. But the most important work was, of course, done by the 34 PC members and their external reviewers, who provided high-quality reviews. After intense discussions to resolve con?icts among the reviewers, the Program Committee decided to accept 33 papers. The conference program also included 4 invited talks, by Jurgen ..Giesl, Al- ander Leitsch, Helmut Seidl, and Igor Walukiewicz, which are documented by short or extended abstracts in these proceedings. In addition, Mart' ?n Abadi held a tutorial on Reasoning About Security Protocols, and Ian Horrocks on Description Logic Reasoning.

This volume containsthe full papers presentedat the 12th InternationalConf- ence on Logic for Programming, Arti?cial Intelligence, and Reasoning (LPAR), held 2-6 December 2006,in MontegoBay,Jamaica.The callfor papersattracted 108 full paper submissions, each of which were reviewed by at least three - viewers. The Program Committee accepted the 46 papers that appear in these proceedings. The conference program also included 4 invited talks, by Tom Ball of Microsoft Research, Doug Lenat of Cycorp, Roberto Nieuwenhuis of the U- versidad Polit' ecnica de Cataluna " , and Allen Van Gelder of the University of California at Santa Cruz. Papers or abstracts for the invited talks are in these proceedings. In addition to the main program, the conference o?ered a short paper track, which attracted 13 submissions, of which 12 were accepted, and the Workshop on Emperically Successful Higher Order Logic (ESHOL). Thanks go to: the authors (of both accepted and rejected papers); the P- gramCommitteeandtheirreviewers;theinvitedspeakers;ChristophBenzmuller .. , John Harrison, and Carsten Schur .. mann for organizing ESHOL; Celia Alleyne- Ebanks for administering the conference in Jamaica; the Honorable Minister Phillip Paulwell of the Ministry of Commerce, Science and Technology for op- ing the conference (and Daphne Simmonds for introducing us to the minister); the Mona Institute of Applied Sciences at the University of the West Indies for their support; Microsoft Research for sponsorship of student regsitrations; the Kurt Godel .. Society for taking registrations; and EasyChair for hosting the review process.

This volumecontains the papers presentedatthe SeventhInternationalC- ference on Logicfor Programmingand Automated Reasoning (LPAR 2000)held onReunionIsland,France,6-10November2000,followedbythe ReunionWo- shop on Implementation of Logic. Sixty-?ve papers were submitted to LPAR 2000 of which twenty-six papers were accepted. Submissions by the program committee members were not - lowed. There was a special category of experimental papers intended to describe implementations of systems, to report experiments with implemented systems, orto compareimplementedsystems.Eachof thesubmissionswasreviewedbyat least three program committee members and an electronic program committee meeting was held via the Internet. In addition to the refereed papers, this volume contains full papers by two of the four invited speakers, Georg Gottlob and Micha. el Rusinowitch, along with an extended abstract of Bruno Courcelle's invited lecture and an abstract of Erich Gr. adel's invited lecture. WewouldliketothankthemanypeoplewhohavemadeLPAR2000possible.We are grateful to the following groups and individuals: the program and or- nizing committees; the additional referees; the local arrangements chair Teodor Knapik; PascalManoury, who was in chargeof accommodation; Konstantin - rovin,whomaintainedthe programcommittee Webpage;andBillMcCune,who implemented the program committee management software.

This volume contains the papers presented at the Eighth International C- ference on Logic for Programming, Arti?cial Intelligence and Reasoning (LPAR 2001), held on December 3-7, 2001, at the University of Havana (Cuba), together with the Second International Workshop on Implementation of Logics. There were 112 submissions, of which 19 belonged to the special subm- sion category of experimental papers, intended to describe implementations or comparisons of systems, or experiments with systems. Each submission was - viewed by at least three program committee members and an electronic program committee meeting was held via the Internet. The high number of submissions caused a large amount of work, and we are very grateful to the other 31 PC members for their e?ciency and for the quality of their reviews and discussions. Finally, the committee decided to accept 40papers in the theoretical ca- gory, and 9 experimental papers. In addition to the refereed papers, this volume contains an extended abstract of the invited talk by Frank Wolter. Two other invited lectures were given by Matthias Baaz and Manuel Hermenegildo. Apart from the program committee, we would also like to thank the other people who made LPAR 2001 possible: the additional referees; the Local Arran- ` gements Chair Luciano Garc´?a; Andr´es Navarro and Oscar Guell, ¨ who ran the internet-based submission software and the program committee discussion so- ware at the LSI Department lab in Barcelona; and Bill McCune, whose program committee management software was used.

The First CADE in the Third Millennium This volume contains the papers presented at the Eighteenth International C- ference on Automated Deduction (CADE-18) held on July 27–30th, 2002, at the University of Copenhagen as part of the Federated Logic Conference (FLoC 2002). Despite a large number of deduction-related conferences springing into existence at the end of the last millennium, the CADE conferences continue to be the major forum for the presentation of new research in all aspects of automated deduction. CADE-18 was sponsored by the Association for Auto- ted Reasoning, CADE Inc., the Department of Computer Science at Chalmers University, the Gesellschaft fur ¨ Informatik, Safelogic AB, and the University of Koblenz-Landau. There were 70 submissions, including 60 regular papers and 10 system - scriptions. Each submission was reviewed by at least ?ve program committee members and an electronic program committee meeting was held via the Int- net. The committee decided to accept 27 regular papers and 9 system descr- tions. One paper switched its category after refereeing, thus the total number of system descriptions in this volume is 10. In addition to the refereed papers, this volume contains an extended abstract of the CADE invited talk by Ian Horrocks, the joint CADE/CAV invited talk by Sharad Malik, and the joint CADE-TABLEAUX invited talk by Matthias Baaz. One more invited lecture was given by Daniel Jackson.

The First CADE in the Third Millennium This volume contains the papers presented at the Eighteenth International C- ference on Automated Deduction (CADE-18) held on July 27–30th, 2002, at the University of Copenhagen as part of the Federated Logic Conference (FLoC 2002). Despite a large number of deduction-related conferences springing into existence at the end of the last millennium, the CADE conferences continue to be the major forum for the presentation of new research in all aspects of automated deduction. CADE-18 was sponsored by the Association for Auto- ted Reasoning, CADE Inc., the Department of Computer Science at Chalmers University, the Gesellschaft fur ¨ Informatik, Safelogic AB, and the University of Koblenz-Landau. There were 70 submissions, including 60 regular papers and 10 system - scriptions. Each submission was reviewed by at least ?ve program committee members and an electronic program committee meeting was held via the Int- net. The committee decided to accept 27 regular papers and 9 system descr- tions. One paper switched its category after refereeing, thus the total number of system descriptions in this volume is 10. In addition to the refereed papers, this volume contains an extended abstract of the CADE invited talk by Ian Horrocks, the joint CADE/CAV invited talk by Sharad Malik, and the joint CADE-TABLEAUX invited talk by Matthias Baaz. One more invited lecture was given by Daniel Jackson.

This volume contains the papers presented at the Eighth International C- ference on Logic for Programming, Arti?cial Intelligence and Reasoning (LPAR 2001), held on December 3-7, 2001, at the University of Havana (Cuba), together with the Second International Workshop on Implementation of Logics. There were 112 submissions, of which 19 belonged to the special subm- sion category of experimental papers, intended to describe implementations or comparisons of systems, or experiments with systems. Each submission was - viewed by at least three program committee members and an electronic program committee meeting was held via the Internet. The high number of submissions caused a large amount of work, and we are very grateful to the other 31 PC members for their e?ciency and for the quality of their reviews and discussions. Finally, the committee decided to accept 40papers in the theoretical ca- gory, and 9 experimental papers. In addition to the refereed papers, this volume contains an extended abstract of the invited talk by Frank Wolter. Two other invited lectures were given by Matthias Baaz and Manuel Hermenegildo. Apart from the program committee, we would also like to thank the other people who made LPAR 2001 possible: the additional referees; the Local Arran- ` gements Chair Luciano Garc´?a; Andr´es Navarro and Oscar Guell, ¨ who ran the internet-based submission software and the program committee discussion so- ware at the LSI Department lab in Barcelona; and Bill McCune, whose program committee management software was used.

This volume contains the papers presented at the Sixth International Conference on Logic for Programming and Automated Reasoning (LPAR''99), held in Tbilisi, Georgia, September 6-10, 1999, and hosted by the University of Tbilisi. Forty-four papers were submitted to LPAR''99. Each of the submissions was reviewed by three program committee members and an electronic program com­ mittee meeting was held via the Internet. Twenty-three papers were accepted. We would like to thank the many people who have made LPAR''99 possible. We are grateful to the following groups and individuals: to the program committee and the additional referees for reviewing the papers in a very short time, to the organizing committee, and to the local organizers of the INTAS workshop in Tbilisi in April 1994 (Khimuri Rukhaia, Konstantin Pkhakadze, and Gela Chankvetadze). And last but not least, we would like to thank Konstantin - rovin, who maintained the program committee Web page; Uwe Waldmann, who supplied macros for these proceedings and helped us to install some programs for the electronic management of the program committee work; and Bill McCune, who implemented these programs.

This book constitutes the refereed proceedings of the 13th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2006, held in Phnom Penh, Cambodia in November 2006. The 38 revised full papers presented together with one invited talk were carefully reviewed and selected from 96 submissions.

This volume contains the proceedings of two Russianconferences on logic programming, held in 1990 in Irkutskand in 1991 in St. Petersburg. The aim of the conferenceswas to bring together researchers from the Russian and theinternational logic programming communities. Topics coveredin the volume include: logic programming, automated theoremproving, non-monotonic reasoning, applications ofmathematical logic to computer science, deductivedatabases,implementation of declarative concepts, and programming innon-classical logics.This is the first volume to represent activity in the fieldof logic programming in the countries of the former SovietUnion.

This volume contains the proceedings of LPAR '92, theinternational conference on logic programming and automatedreasoning held in St. Petersburg in July 1992. The aim ofthe conference was to bring together researchers from theRussian and the international logic programming and theoremproving communities.The topics of interest covered by papers inthe volumeinclude automated theorem proving, non-monotonic reasoning,applications of mathematical logic to computer science,deductive databases, implementation of declarative concepts,and programming in non-classical logics.LPAR '92 is the successor of the First and Second RussianConferences on Logic Programming held in 1990 and 1991,respectively, the proceedings of which were publishedinLNAI Vol. 592.

LPAR is an international conference series aimed at bringingtogether researchers interested in logic programming andautomated reasoning. The research in logic programming grewout of the research in automated reasoning in the early1970s. Later, the implementation techniques known from logicprogramming were used in implementing theorem provingsystems. Results from both fields applied to deductivedatabases.This volume contains the proceedings of LPAR '93, which wasorganized by the Russian Association for Logic Programming.The volume contains 35 contributed papers selected from 84submissions, together with an invited paper by Peter Wegnerentitled "Reasoning versus modeling in computer science".

This book constitutes the thoroughly refereed and revised post-workshop proceedings of two international meetings devoted to deductive databases and logic programming.The technical papers presenting original research results were carefully reviewed and selected for inclusion in the present book, together with several survey articles summarizing the state of the art in the area. Thus, the book is the ultimate reference for anybody interested in the theory and application of deductive databases and logic programming.