Alberto Pettorossi - Böcker

“Automatic Program Development” is a tribute to Robert Paige (1947-1999), our accomplished and respected colleague, and moreover our good friend, whose untimely passing was a loss to our academic and research community. We have collected the revised, updated versions of the papers published in his honor in the Higher-Order and Symbolic Computation Journal in the years 2003 and 2005. Among them there are two papers by Bob: (i) a retrospective view of his research lines, and (ii) a proposal for future studies in the area of the automatic program derivation. The book also includes some papers by members of the IFIP Working Group 2.1 of which Bob was an active member. All papers are related to some of the research interests of Bob and, in particular, to the transformational development of programs and their algorithmic derivation from formal specifications. “Automatic Program Development” offers a renewed stimulus for continuing and deepening Bob's research visions. A familiar touch is given to the book by some pictures kindly provided to us by his wife Nieba, the personal recollections of his brother Gary and some of his colleagues and friends.

In this book the author presents some techniques for exploring trees and graphs. He illustrates the linear search technique and the backtracking technique, and as instances of tree exploration methods he presents various algorithms for parsing subclasses of context-free languages. He also illustrates some tree and graph exploration and manipulation methods by presenting, among others, algorithms for visiting trees, evaluating Boolean expressions, proving propositional formulas, computing paths in graphs, and performing string matching.This book has been used for advanced undergraduate and graduate courses on automata and formal languages, and assumes some prior exposure to the basic notions in that area. Sample programs are presented in Java and Prolog.

In this book the author presents some techniques for exploring trees and graphs. He illustrates the linear search technique and the backtracking technique, and as instances of tree exploration methods he presents various algorithms for parsing subclasses of context-free languages. He also illustrates some tree and graph exploration and manipulation methods by presenting, among others, algorithms for visiting trees, evaluating Boolean expressions, proving propositional formulas, computing paths in graphs, and performing string matching.This book has been used for advanced undergraduate and graduate courses on automata and formal languages, and assumes some prior exposure to the basic notions in that area. Sample programs are presented in Java and Prolog.

Knowledge of automata theory and formal languages is crucial for understanding human-computer interaction, as well as for understanding the various processes that take place when manipulating knowledge if that knowledge is, indeed, expressed as sentences written in a suitably formalized language. In particular, it is at the basis of the theory of parsing, which plays an important role in language translation, compiler construction, and knowledge manipulation in general.Presenting basic notions and fundamental results, this concise textbook is structured on the basis of a correspondence that exists between classes of automata and classes of languages. That correspondence is established by the fact that the recognition and the manipulation of sentences in a given class of languages can be done by an automaton in the corresponding class of automata. Four central chapters center on: finite automata and regular languages; pushdown automata and context-free languages; linear bounded automata and context-sensitive languages; and Turing machines and type 0 languages.  The book also examines decidable and undecidable problems with emphasis on the case for context-free languages.Topics and features:Provides theorems, examples, and exercises to clarify automata-languages correspondencesPresents some fundamental techniques for parsing both regular and context-free languagesClassifies subclasses of decidable problems, avoiding focus on the theory of complexityExamines finite-automata minimalization and characterization of their behavior using regular expressionsIllustrates how to derive grammars of context-free languages in Chomsky and Greibach normal formsOffers supplementary material on counter machines, stack automata, and abstract language familiesThis highly useful, varied text/reference is suitable for undergraduate and graduatecourses on automata theory and formal languages, and assumes no prior exposure to these topics nor any training in mathematics or logic.Alberto Pettorossi is professor of theoretical computer science at the University of Rome Tor Vergata, Rome, Italy.

ThisvolumecontainsthepapersfromLOPSTR2001,the11thInternational WorkshoponLogic-basedProgramSynthesisandTransformation. Topicsof- teresttoLOPSTRcoverallaspectsoflogic-basedprogramdevelopmentand,in particular, speci?cation, synthesis, veri?cation, transformation, specialization, analysis,optimization,composition,reuse,component-basedsoftwaredevel- ment,andsoftwarearchitectures. LOPSTR 2001 took place in the Coral Beach Hotel in Paphos (Cyprus) fromNovember28-30,2001. PastLOPSTRworkshopswereheldinManchester, UK(1991,1992,1998),Louvain-la-Neuve,Belgium(1993),Pisa,Italy(1994), Arnhem,TheNetherlands(1995),Stockholm,Sweden(1996),Leuven,Belgium (1997),Venice,Italy(1999),andLondon,UK(2000). LOPSTR2001wasco-locatedwiththe17thInternationalConferenceonLo- 1 gicProgramming(ICLP2001) andthe7thInternationalConferenceonPrinci- 2 plesandPracticeofConstraintProgramming(CP2001) . TheLOPSTRc- munitypro?tedalotfromthescienti?cdiscussions,thelecturesoftheinvited speakers,andthevarioussessionsofICLPandCP. I would like to express my gratitude to all the authors of the submitted papersandalltheattendeesfortheircommitmentandcooperation.Amongthe submittedpapers,theProgramCommitteeselected13papersforpresentation. Aftertheworkshop,theauthorswereaskedtosubmitimprovedversionsoftheir paperswhichwerethenreviewedbytheProgramCommittee. The?nalversions havebeencollectedinthisvolume,whichalsoincludesthepaperbyourinvited speaker,NatarajanShankar(StanfordResearchInstitute,MenloPark,USA), onthegenerationofe?cientprogramsfromlogic. MywarmestthanksalsogotoallthemembersoftheProgramCommittee andtheadditionalreviewersfortheirdiligentworkandinvaluablehelp. Iwould liketothankFabioFioravanti(IASI-CNRofRome,Italy),MaurizioProietti (IASI-CNRofRome,Italy),andAntonisKakas(UniversityofCyprus,Cyprus), whoworkedwithmewithgreatenthusiasmanddedicationasmembersofthe OrganizingCommittee. Thepre-proceedingsofLOPSTR2001wereprintedbytheIASIInstituteof theNationalResearchCouncilofRome,Italy,andtheDepartmentofComputer ScienceoftheUniversityofCyprusinNicosia. IalsothankSpringerforaccepting topublishthese?nalproceedingsintheLNCSseries. TheLOPSTR2001home pageis:http://www. iasi. rm. cnr. it/"adp/lopstr01cfp. html. April2002 AlbertoPettorossi 1 Codognet,Ph. ,editor,LogicProgramming-ICLP2001,LectureNotesinComputer Science 2237,Springer-Verlag,2001.2 Walsh,T. ,editor,PrinciplesandPracticeofConstraintProgramming-CP2001, LectureNotesinComputerScience 2239,Springer-Verlag,2001. ProgramChair AlbertoPettorossi Universit'adegliStudidiRoma'TorVergata',Italy ProgramCommittee DavidBasin Albert-Ludwigs-Universit..atFreiburg,Germany AntonioBrogi Universit'adiPisa,Italy MauriceBruynooghe KatholiekeUniversiteitLeuven,Belgium NicolettaCocco Universit'aCa'FoscaridiVenezia,Italy MireilleDucass'e IRISA/INSA,France SandroEtalle TwenteUniversity&CWI,TheNetherlands JohnGallagher UniversityofBristol,UK RobertGluc .. k WasedaUniversity,Japan MichaelHanus Christian-Albrechts-Universit..atzuKiel,Germany ManuelHermenegildo UniversidadPolit'ecnicadeMadrid,Spain PatriciaHill UniversityofLeeds,UK Kung-KiuLau UniversityofManchester,UK MichaelLeuschel UniversityofSouthampton,UK TorbenMogensen UniversityofCopenhagen,Denmark AlbertoPettorossi Universit'adegliStudidiRoma'TorVergata',Italy I. V. Ramakrishnan StateUniversityofNewYorkatStonyBrook,USA DonSannella UniversityofEdinburgh,UK ZoltanSomogyi UniversityofMelbourne,Australia AdditionalReferees Jos'eAlferes StefanGruner SabinaRossi AnnalisaBossi PaulJackson FaustoSpoto Lu'?sFernandoCastro FrancisKlay MathieuTuruani AlessandraDiPierro GiridharPemmasani WimVanhoof YifeiDong MaurizioProietti FabioFioravanti Germ'anPuebla SponsoringInstitutions TheAssociationforLogicProgramming TheCOLOGNet TheInternationalFederationforComputationalLogic TheIASIInstituteofCNR(Italy) Universit'adegliStudidiRoma'TorVergata'(Italy) TableofContents InvitedSpeaker Static Analysis for Safe Destructive Updates in a Functional Language ...1 NatarajanShankar(SRIInternational,MenloPark,USA) ProgramTransformationandEquivalence A Transformation Technique for Datalog Programs Based on Non-deterministic Constructs...25 PetrosPotikas,PanosRondogiannis(UniversityofAthens,Greece), ManolisGergatsoulis(InstituteofInformatics&Telecommunications, AghiaParaskeviAttikis,Greece) On Deforesting Parameters of Accumulating Maps ...46 KazuhikoKakehi,RobertGluck, .. YoshihikoFutamura(Waseda University,Tokyo,Japan) Equivalence in Answer Set Programming...57 MauricioOsorio,JuanA. Navarro,Jos'eArrazola(Universidaddelas Am'ericas,Puebla,M'exico) ProgramVeri?caion Proof Theory, Transformations, and Logic Programming for Debugging Security Protocols...76 GiorgioDelzanno(UniversityofGenova,Italy),SandroEtalle(CWI andUniversityofTwente,TheNetherlands) Abstract Conjunctive Partial Deduction Using Regular Types and Its Application to Model Checking ...

This volume contains lectures and papers delivered at Meta92, the Third International Workshop on Metaprogramming inLogic, held in Uppsala, Sweden,June 1992. The topicscovered include foundations of metaprogramming in logic,proposals for metaprogramming languages, techniques forknowledgerepresentation and belief systems, and programtransformation and analysis in logic. Particular topics include belief revision systems,intensionaldeduction, belief systems and metaprogramming,principles of partial deduction, termination in logicprograms, semantics of the "vanilla" metainterpreter, acomplete resolution method for metaprogramming, semanticsof"demo", hierarchical metalogics, the naming relation inmetalevel systems, modules, reflective agents, compileroptimizations, metalogic and object-oriented facilities,parallel logic languages, the use of metaprogramming forlegal reasoning, representing objects and inheritance,transformation of normal programs, negation in automaticallygenerated logic programs, reordering of literals indeductive databases, abstract interpretations, andinterarguments in constraint logic programs.