ebook img

Relations and Kleene Algebra in Computer Science: 9th International Conference on Relational Methods in Computer Science and 4th International Workshop on Applications of Kleene Algebra, RelMiCS/AKA 2006, Manchester, UK, August 29–September 2, 2006. Proce PDF

442 Pages·2006·4.12 MB·English
Save to my drive
Quick download
Download
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

Preview Relations and Kleene Algebra in Computer Science: 9th International Conference on Relational Methods in Computer Science and 4th International Workshop on Applications of Kleene Algebra, RelMiCS/AKA 2006, Manchester, UK, August 29–September 2, 2006. Proce

Lecture Notes in Computer Science 4136 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Renate A. Schmidt (Ed.) Relations and Kleene Algebra in Computer Science 9th International Conference on Relational Methods in Computer Science and 4th InternationalWorkshop onApplications of KleeneAlgebra, RelMiCS/AKA 2006 Manchester, UK,August/September, 2006 Proceedings 1 3 VolumeEditor RenateA.Schmidt UniversityofManchester SchoolofComputerScience OxfordRd,ManchesterM139PL,UK E-mail:[email protected] LibraryofCongressControlNumber:2006931478 CRSubjectClassification(1998):F.4,I.1,I.2.3,D.2.4 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-540-37873-1SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-37873-0SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com ©Springer-VerlagBerlinHeidelberg2006 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:11828563 06/3142 543210 Preface This volume contains the joint proceedings of the 9th International Conference on Relational Methods in Computer Science (RelMiCS-9) and the 4th Interna- tionalWorkshoponApplicationsofKleeneAlgebra(AKA2006).Thejointevent was hosted by the School of Computer Science at the University of Manchester, UK, from August 29 to September 2, 2006. RelMiCS/AKA is the main forum fortherelationalcalculusasaconceptualandmethodologicaltoolandfortopics relatedtoKleenealgebras.Withinthisgeneraltheme,theconferenceseriesisde- votedto the theory of relationalgebras,Kleene algebrasand relatedformalisms as well as to their diverse applications in software engineering, databases and artificial intelligence. This year, special focus was on formal methods, logics of programs and links with neighboring disciplines. This diversity is reflected by the contributions to this volume. TheProgrammeCommittee selected25technicalcontributionsoutof44ini- tial submissions from 14 countries. Each paper was refereed by at least three reviewerson its originality,technical soundness, quality of presentationand rel- evance to the conference. The programme included three invited lectures by distinguished experts in the area: “Weak Kleene Algebra and Computation Trees” by Ernie Cohen (Microsoft, USA), “Finite Symmetric Integral Relation Algebras with no 3-Cycles” by Roger Maddux (Iowa State University, USA), and “Computations and Relational Bundles” by Jeff Sanders (Oxford, UK). In addition,forthefirsttime,aPhDprogrammewasco-organizedbyGeorgStruth. It included the invited tutorials “Foundations of Relation Algebra and Kleene Algebra”byPeterJipsen(ChapmanUniversity,USA),and“RelationalMethods for ProgramRefinement” by John Derrick (Sheffield University, UK). As in previousyears,the RelMiCS Conference andthe AKAWorkshopwere co-organizedbecause of their considerable overlap. Previous RelMiCS meetings were held in 1994 at Dagstuhl, Germany, in 1995 at Parati, Brazil, in 1997 at Hammamet, Tunisia, in 1998 at Warsaw, Poland, in 1999 at Qu´ebec, Canada, in 2001 at Oisterwijk, The Netherlands, in 2003 at Malente, Germany and in 2005 at St.Catharines, Canada. The AKA Workshophas been held jointly with RelMiCS since 2003, after an initial Dagstuhl Seminar in 2001. I would like to thank the many people without whom the meeting would not have been possible. First, I would like to thank all authors who submitted papers,allparticipantsof the conferenceas well asthe invited keynotespeakers and the invited tutorial speakers for their contributions. I am very grateful to the members of the Programme Committee and the external referees for care- fully reviewing and selecting the papers. I thank my colleagues on the Steering Committee for their advice and the support for the changes introduced for this year’s event. Special thanks go to the members of the local organization team in the School of Computer Science at the University of Manchester for all their VI Preface help: the staff in the ACSO office, especially Bryony Quick and Iain Hart, the staff of the finance office, and the technical staff, as well as Zhen Li and David Robinson. Moreover, I am extremely grateful to Georg Struth for his tremen- dous amountof effort—as ProgrammeChair he helped with every aspect of the planning and organization of RelMiCS/AKA 2006 and the PhD Programme. Finally, it is my pleasure to acknowledge the generous support by: the UK En- gineering and Physical Sciences Research Council (grant EP/D079926/1), the London Mathematical Society, the British Logic Colloquium, the University of Manchester(President’sFund), andthe SchoolofComputerScience,University of Manchester. Manchester, June 2006 Renate Schmidt General Chair RelMiCS/AKA 2006 Organization Conference Chairs Renate Schmidt (UK, General Chair) Georg Struth (UK, ProgramChair) Steering Committee RudolfBerghammer(Germany,Chair) Gunther Schmidt (Germany) Jules Desharnais (Canada) Renate Schmidt (UK) Ali Jaoua (Qatar) Harrie de Swart (Netherlands) Bernhard M¨oller (Germany) Michael Winter (Canada) Ewa Orlowska (Poland) Program Committee Roland Backhouse (UK) Zhiming Liu (China) Rudolf Berghammer (Germany) Bernhard M¨oller (Germany) St´ephane Demri (France) Damian Niwinski (Poland) Jules Desharnais (Canada) Ewa Orlowska (Poland) Zolt´an E´sik (Hungary, Spain) Alban Ponse (Netherlands) Marcelo Fr´ıas (Argentina) Ingrid Rewitzky (South Africa) Hitoshi Furusawa (Japan) Ildiko´ Sain (Hungary) St´ephane Gaubert (France) Holger Schlingloff (Germany) Steven Givant (USA) Gunther Schmidt (Germany) Valentin Goranko (South Africa) Renate Schmidt (UK) Martin Henson (UK) Giuseppe Scollo (Italy) Ali Jaoua (Qatar) Georg Struth (UK) Peter Jipsen (USA) Michael Winter (Canada) Wolfram Kahl (Canada) Harrie de Swart (Netherlands) Yasuo Kawahara(Japan) External Referees Balder ten Cate Wim Hesselink Zhao Liang Alexander Fronk Peter H¨ofner Kamal Lodaya Marian Gheorghe Britta Kehden Maarten Marx VIII Organization Sun Meng Andrea Schalk Thomas Triebsees Szabolcs Mikulas Nikolay V. Shilov Jeff Sanders Venkat Murali Kim Solin Liang Zhao Ian Pratt-Hartmann Dmitry Tishkovsky Local Organization Renate Schmidt (Local OrganizationChair) Bryony Cook, Iain Hart (Registration, Secretarial Support) Zhen Li (Webpages) David Robinson (Local Organization) Sponsoring Institutions British Logic Colloquium Engineering and Physical Sciences Research Council London Mathematical Society University of Manchester Table of Contents Weak Kleene Algebra and Computation Trees ........................ 1 Ernie Cohen Finite Symmetric Integral Relation Algebras with No 3-Cycles.......... 2 Roger D. Maddux Computations and Relational Bundles ............................... 30 J.W. Sanders An Axiomatization of Arrays for Kleene Algebra with Tests ............ 63 Kamal Aboul-Hosn Local Variable Scoping and Kleene Algebra with Tests................. 78 Kamal Aboul-Hosn, Dexter Kozen Computing and Visualizing Lattices of Subgroups Using Relation Algebra and RelView ............................................ 91 Rudolf Berghammer On the Complexity of the Equational Theory of Relational Action Algebras......................................................... 106 Wojciech Buszkowski Demonic Algebra with Domain ..................................... 120 Jean-Lou De Carufel, Jules Desharnais Topological Representation of Contact Lattices ....................... 135 Ivo Du¨ntsch, Wendy MacCaull, Dimiter Vakarelov, Michael Winter Betweenness and Comparability Obtained from Binary Relations........ 148 Ivo Du¨ntsch, Alasdair Urquhart Relational Representation Theorems for General Lattices with Negations ....................................................... 162 Wojciech Dzik, Ewa Orlowska, Clint van Alten Monotonicity Analysis Can Speed Up Verification..................... 177 Marcelo F. Frias, Rodolfo Gamarra, Gabriela Steren, Lorena Bourg X Table of Contents Max-Plus Convex Geometry........................................ 192 St´ephane Gaubert, Ricardo Katz Lazy Semiring Neighbours and Some Applications..................... 207 Peter H¨ofner, Bernhard Mo¨ller Omega Algebra, Demonic Refinement Algebra and Commands.......... 222 Peter H¨ofner, Bernhard Mo¨ller, Kim Solin Semigroupoid Interfaces for Relation-Algebraic Programming in Haskell........................................................ 235 Wolfram Kahl On the Cardinality of Relations..................................... 251 Yasuo Kawahara Evaluating Sets of Search Points Using Relational Algebra ............. 266 Britta Kehden Algebraization of Hybrid Logic with Binders ......................... 281 Tadeusz Litak Using Probabilistic Kleene Algebra for Protocol Verification ............ 296 A.K. McIver, E. Cohen, C.C. Morgan Monotone Predicate Transformers as Up-Closed Multirelations......... 311 Ingrid Rewitzky, Chris Brink Homomorphism and Isomorphism Theorems Generalized from a Relational Perspective ............................................. 328 Gunther Schmidt Relational Measures and Integration................................. 343 Gunther Schmidt A Relational View of Recurrence and Attractors in State Transition Dynamics ........................................................ 358 Giuseppe Scollo, Giuditta Franco, Vincenzo Manca On Two Dually Nondeterministic Refinement Algebras ................ 373 Kim Solin On the Fixpoint Theory of Equality and Its Applications .............. 388 Andrzej Szal(cid:2)as, Jerzy Tyszkiewicz Table of Contents XI Monodic Tree Kleene Algebra ...................................... 402 Toshinori Takai, Hitoshi Furusawa Weak Relational Products.......................................... 417 Michael Winter Author Index................................................... 433

Description:
The book constitutes the joint refereed proceedings of the 9th International Conference on Relational Methods in Computer Science, RelMiCS 2006, and the 4th International Workshop on Applications of Kleene Algebras, AKA 2006, held in Manchester, UK in August/September 2006.The 25 revised full papers
See more

The list of books you might like

Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.