March 1998 - Categories - categories.org.au

ICALP '98: List of Accepted Papers
by Uffe Henrik Engberg 18 Mar '98

18 Mar '98

The papers listed below were accepted for ICALP '98, which will be held on July 13-17 in Aalborg, Denmark. Further information on ICALP '98 is available on the Web at http://www.cs.auc.dk/icalp98/ ------------------------------------------------------------------------------- A duality between Kruskal and Dershowitz theorems by Paul-Andre Mellies ------------------------------------------------------------------------------- A genuinely polynomial-time algorithms for sampling two-rowed contingency tables by Martin Dyer, Catherine Greenhill ------------------------------------------------------------------------------- Efficient Simulations by Queue Machines by Holger Petersen, John Michael Robson ------------------------------------------------------------------------------- On the Complexity of Deriving Score Functions from Examples for Problems in Molecular Biology by Tatsuya Akutsu, Mutsunori Yagiura ------------------------------------------------------------------------------- Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees by David Peleg ------------------------------------------------------------------------------- Deterministic Polylog Approximation for Minimum Communication Spanning Trees by David Peleg, Eilon Reshef ------------------------------------------------------------------------------- A Good Class of Tree Automata and Application to Inductive Theorem Proving by Denis Lugiez ------------------------------------------------------------------------------- On Computing the Entropy of Cellular Automata by Michele D'amico, Giovanni Manzini, Luciano Margara ------------------------------------------------------------------------------- On Branching Programs With Bounded Uncertainty by Stasys Jukna, Stanislav Zak ------------------------------------------------------------------------------- CONS-Free Programs with Tree Input by Amir Ben-Amram, Holger Petersen ------------------------------------------------------------------------------- Global/Local Subtyping and Capability Inference for a Distributed pi-calculus by Peter Sewell ------------------------------------------------------------------------------- Computing Mimicking Networks by Shiva Chaudhuri, K.V. Subrahmanyam, Frank Wagner, Christos Zaroliagis ------------------------------------------------------------------------------- Robust asynchronous protocols are finite-state by Madhavan Mukund, K Narayan Kumar, Jaikumar Radhakrishnan, Milind Sohoni ------------------------------------------------------------------------------- Optimal Sampling Strategies in Quicksort by Conrado Martinez, Salvador Roura ------------------------------------------------------------------------------- The relevance of proof-irrelevance by Gilles Barthe ------------------------------------------------------------------------------- Deciding global partial-order properties by Rajeev Alur, Ken McMillan, Doron Peled ------------------------------------------------------------------------------- Efficient Minimization of Numerical Summation Errors by Ming-Yang Kao, Jie Wang ------------------------------------------------------------------------------- Simpler and Faster Static AC^0 Dictionaries by Torben Hagerup ------------------------------------------------------------------------------- Structural Recursive Definitions in Type Theory by Eduardo Gimenez ------------------------------------------------------------------------------- On the Determinization of Weighted Finite Automata by Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery R. Westbrook ------------------------------------------------------------------------------- A Degree-Decreasing Lemma for (MOD q -- MOD p) Circuits by Vince Grolmusz ------------------------------------------------------------------------------- Improved Pseudorandom Generators for Combinatorial Rectangles by Chi-Jen Lu ------------------------------------------------------------------------------- Checking Strong/Weak Bisimulation Equivalences and Observation by Zhoujun Li, Huowang Chen ------------------------------------------------------------------------------- On Existentially First-Order Definable Languages and their Relation to NP by Bernd Borchert, Dietrich Kuske, Frank Stephan ------------------------------------------------------------------------------- Morphing simple polygons optimally - a proof for an improved conjecture by T. Graf, V. Kamakoti ------------------------------------------------------------------------------- Metric Semantics for True Concurrent Real Time by Christel Baier, Joost-Pieter Katoen, Diego Latella ------------------------------------------------------------------------------- Static and Dynamic Low-Congested Interval Routing Schemes by Serafino Cicerone, Gabriele Di Stefano, Michele Flammini ------------------------------------------------------------------------------- Independent sets with domination constraint by Magnus M. Halldorsson, Jan Kratochvil, Jan Arne Telle ------------------------------------------------------------------------------- Sequential Iteration of Interactive Arguments and an Efficient Zero-Knowledge Argument for NP by Ivan Damgaard, Birgit Pfitzmann ------------------------------------------------------------------------------- A modular approach to denotational semantics by John Power, Giuseppe Rosolini ------------------------------------------------------------------------------- Generalised Flowcharts and Games by Pasquale Malacaria, Chris Hankin ------------------------------------------------------------------------------- Efficient approximation algorithms for the {sc Subset-Sums Equality} problem by Cristina Bazgan, Miklos Santha, Zsolt Tuza ------------------------------------------------------------------------------- A complex eample of a simplifying rewrite system by H. Touzet ------------------------------------------------------------------------------- Low-Bandwidth Routing and Electrical Power Networks by Doug Cook, Vance Faber, Madhav Marathe, Aravind Srinivasan, Yoram J. Sussmann ------------------------------------------------------------------------------- Deciding Bisimulation-Like Equivalences with Finite-State Processes by Petr Jancar, Antonin Kucera, Richard Mayr ------------------------------------------------------------------------------- The equivalence problem for propositional programs is decidable in polynomial time. by Vladimir A. Zakharov ------------------------------------------------------------------------------- A Total AC-Compatible Reduction Ordering on Higher-Order Terms by Daria Walukiewicz ------------------------------------------------------------------------------- Partial-Congruence Factorization of Bisimilarity Induced by Open Maps by Slawomir Lasota ------------------------------------------------------------------------------- The Regular Real-Time Languages by Henzinger Tom, Raskin Jean-Francois, Schobbens Pierre-Yves ------------------------------------------------------------------------------- Multi-Stage Programming: Axiomatization and Type Safety by Walid Taha, Zine-El-Abidine Benaissa, Tim Sheard ------------------------------------------------------------------------------- Limited Wavelength Conversion in All-Optical Tree Networks by Luisa Gargano ------------------------------------------------------------------------------- Difficult configurations - on the complexity of LTrL by Igor Walukiewicz ------------------------------------------------------------------------------- Inversion of Circulant Matrices over Z_m by dario bini, gianna del corso, giovanni manzini, luciano margara ------------------------------------------------------------------------------- A Hierarchy of Equivalences for Asynchronous Calculi by Cedric Fournet, Georges Gonthier ------------------------------------------------------------------------------- Explicit Substitutions for Constructive Necessity by Neil Ghani, Valeria de Paiva, Eike Ritter ------------------------------------------------------------------------------- Locally Periodic Infinite Words and a Chaotic Behaviour by Juhani KarhumÃ¤ki, Arto LepistÃ¶, Wojciech Plandowski ------------------------------------------------------------------------------- BRIDGES FOR CONCATENATION HIERARCHIES by Jean-Eric Pin ------------------------------------------------------------------------------- Application of lempel-ziv encodings to the solution of words equations by Wojciech Plandowski, Wojciech Rytter ------------------------------------------------------------------------------- Constraint Automata and the Complexity of Recursive Subtype Entailment by Fritz Henglein, Jakob Rehof ------------------------------------------------------------------------------- Randomness Spaces by Peter Hertling, Klaus Weihrauch ------------------------------------------------------------------------------- Power of cooperation and multihead finite systems. by Pavol Duri\v{s}, Tomasz Jurdzinski, Miroslaw Kutylowski, Krzysztof Lorys ------------------------------------------------------------------------------- A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity by Artur Czumaj, Andrzej Lingas ------------------------------------------------------------------------------- Bulk-synchronous parallel multiplication of Boolean matrices by Alexandre Tiskin ------------------------------------------------------------------------------- Reasoning about The Past with Two-Way Automata by Moshe Y. Vardi ------------------------------------------------------------------------------- Translation Validation for Synchronous Languages by A. Pnueli, O. Shtrichman, M. Siegel ------------------------------------------------------------------------------- Quantum Counting by Gilles Brassard, Peter Hoyer, Alain Tapp ------------------------------------------------------------------------------- Complete Proof Systems for Observation Congruences in Finite-Control pi-Calculus by Huimin Lin ------------------------------------------------------------------------------- On asynchrony in name-passing calculi by Massimo Merro, Davide Sangiorgi ------------------------------------------------------------------------------- A Simple Solution to Type Specialization by Olivier Danvy ------------------------------------------------------------------------------- Concatenable Graph Processes: Relating Processes and Derivation Traces by Paolo Baldan, Andrea Corradini, Ugo Montanari ------------------------------------------------------------------------------- On the Expressiveness of Real and Integer Arithmetic Automata by Bernard Boigelot, Stephane Rassart, Pierre Wolper ------------------------------------------------------------------------------- Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Method by Thore Husfeldt, Theis Rauhe ------------------------------------------------------------------------------- Reset nets between decidability and undecidability by C. Dufourd, A. Finkel, Ph. Schnoebelen ------------------------------------------------------------------------------- Totality, definability and boolean ciruits by Antonio Bucciarelli, Ivano Salvo ------------------------------------------------------------------------------- Concurrent Constraints in the Fusion Calculus by BjÃ¶rn Victor, Joachim Parrow ------------------------------------------------------------------------------- Simple Linear-Time Algorithms for Minimal Fixed Points by Xinxin Liu, Scott A. Smolka ------------------------------------------------------------------------------- Axioms for Contextual Net Processes by Fabio Gadducci, Ugo Montanari ------------------------------------------------------------------------------- An algebraic approach to communication complexity by Jean-Francois Raymond, Pascal Tesson, Denis Therien ------------------------------------------------------------------------------- Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses by R. C-N. Chuang, A. Garg, X. He, M-Y. Kao, H-I. Lu ------------------------------------------------------------------------------- Non-Interactive Statistical Zero-Knowledge: a Complete Problem and Closure Properties by Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung -------------------------------------------------------------------------------

1 0

ICCL'98 Call For Participation
by Christopher Colby 13 Mar '98

13 Mar '98

CALL FOR PARTICIPATION IEEE Computer Society 1998 International Conference on Computer Languages Loyola University Chicago, USA, 14--16 May, 1998 Sponsored by the IEEE Computer Society Technical Committee on Computer Languages, in cooperation with the ACM Special Interest Group on Programming Languages. http://www.math.luc.edu/iccl98/ This is the sixth in a series of conferences devoted to all aspects of computer languages, serving to bring together people broadly interested in machine processable descriptions. The hallmarks of ICCL are diversity, openness to a wide range of linguistic research, and international representation. The focus is on new ideas in languages and language technology which are innovative or experimental in nature. On May 13, a pre-conference Workshop on Internet Programming Languages will be conducted at Loyola University. Details are given at the end of this announcement. IMPORTANT DEADLINES Hotel discount reservation deadline: April 12, 1998 Early conference registration deadline: April 22, 1998 Information about hotels and conference registration appears below and at the ICCL web page cited above. CONFERENCE PROGRAM The conference runs Thursday, May 14, 8:30am-6:00pm; Friday, May 15, 8:45am-5:30pm; and Saturday, May 16, 8:45am-12:45pm The invited speakers are Luca Cardelli, Microsoft Cambridge Labs (UK) Paul Hudak, Yale University (US) James Larus, University of Wisconsin (US) The technical sessions consist of the following talks: THURSDAY, MAY 14th Invited Lecture: Luca Cardelli, Microsoft Cambridge Labs (UK) Security and Dynamic Class Loading in Java: A Formalisation T. Jensen D. Le M'etayer T. Thorn, IRISA/CNRS/INRIA (FR) TJava: A Transactional Java Alex Garthwaite and Scott Nettles, University of Pennsylvania (US) Breaking Abstractions and Unstructuring Data Structures Christian Collberg, Clark Thomborson and Douglas Low, The University of Auckland (NZ) Using Reflexivity to Interface with CORBA Roberto Ierusalimschy, Renato Cerqueira, Noemi Rodriguez, Rio de Janeiro-Brazil (BR) Reactive Programming in Standard ML Riccardo R. Pucella, Bell Laboratories, Lucent Technologies (US) Design and Implementation of Triveni: A Process-algebraic API for Threads + Events Christopher Colby, Lalita Jategaonkar Jagadeesan, Radha Jagadeesan, Konstantin L"aufer and Carlos Puchol, Loyola University Chicago (US) and Bell Laboratories, Lucent Technologies (US) Distributed Computations Driven by Resource Consumption Luc Moreau and Christian Queinnecy, University of Southampton (UK), LIP 6 & INRIA-Rocquencourt (FR) Automatic Generation of Microarchitecture Simulators Soner Vnder and Rajiv Gupta, University of Pittsburgh (US) Microprocessor Specification in Hawk J. Matthews, J. Launchbury, B. Cook, Oregon Graduate Institute (US) The Template and Multiple Inheritance Approach into Attribute Grammars Marjan Mernik, Mitja Lenic, Enis Avdicausevic, Viljem Zumer University of Maribor (Slovenia) Combining Functional and OOprogramming Methodologies in a Large Commercial Application Ian Poole, Craig Ewington, Arthur Jones and Steve Wille, Vysys, Inc and Lawrence Berkeley National Lab (US) FRIDAY, MAY 15th Invited Lecture: Paul Hudak, Yale University (US) Modular Compilers Based on Monad Transformers William L. Harrison and Samuel N. Kamin, University of Illinois, Urbana-Champaign (US) Automatic, Template-Based Run-Time Specialization: Implementation and Experimental Study Francois Noel, Luke Hornof, Charles Consel, Julia L. Lawall, University of Rennes and IRISA (FR) Controlled Self-applicable On-line Partial Evaluation, Using Strategies Mattox Beckman and Sam Kamin, University of Illinois at Urbana-Champaign (US) Parallelization via Context Preservation Wei-Ngan Chin, A. Takano and Zhenjiang Hu, NUS (SG), Hitachi (JP), University of Tokyo (JP) Type Reconstruction for Syntactic Control of Interference, Part 2 Hongseok Yang and Howard Huang, University of Illinois at Urbana-Champaign (US) An Operational Semantics for Probabilistic Concurrent Constraint Programming Alessandra Di Pierro and Herbert Wiklicky, City University London (UK) Set Constraints for Destructive Array Update Optimization Mitchell Wand and William D. Clinger, Northeastern University (US) A Conservative Technique to Improve Deterministic Evaluation of Logic Programs Abhik Roychoudhury, C.R. Ramakrishnan, I.V. Ramakrishnan and R.C. Sekar, SUNY Stony Brook and Iowa State (US) Dependence Analysis for Recursive Data Yanhong A. Liu, Indiana University (US) Optimal Code Motion in the Presence of Large Expressions Oliver R"uthing, Dortmund University (DE) SATURDAY, MAY 16 Invited Lecture: James Larus, University of Wisconsin (US) Path Profile Guided Partial Redundancy Elimination Using Speculation Rajiv Gupta, David A. Berson, and Jesse Z. Fang, University of Pittsburgh (US), Intel Corporation Microcomputer Research Lab (US) An Infrastructure for Profile-Driven Dynamic Recompilation Robert G. Burger and R. Kent Dybvig, SAGIAN (US), Indiana University (US) Formal Callability and its Relevance and Application to Interprocedural Data Flow Analysis Jens Knoop, Universitat Passau (DE) Loop Optimization for Aggregate Array Computations Yanhong A. Liu and Scott D. Stoller, Indiana University (US) Data Flow Analysis Across Tuplespace Process Boundaries James B. Fenwick Jr. and Lori L. Pollock, University of Delaware (US) REGISTRATION Secure online registration is available at https://secure.computer.org/conf/iccl/register.htm This registration application accepts MasterCard, Visa, American Express, and Diners Club cards. If you do not have one of these credit cards, or if you prefer not to register online, please print out the form and fax or mail it with payment to the address given on the form. Conference registration includes admission to the technical sessions, morning and afternoon refreshment breaks, the Wednesday evening reception, and one copy of the proceedings. Advance Registration Fees: IEEE Member $220, Nonmember $275, Full-time Student $120 Late/On-Site Registration Fees: IEEE Member $265, Nonmember $330, Full-time Student $120 HOTELS We have negotiated special rates for ICCL attendees at the Talbott Hotel (+1-312-944-4970, 20 East Delaware Place) and at the Days Inn Lake Shore Drive (+1-312-943-9200, 644 North Lake Shore Drive). Please mention ICCL/Loyola University to get the special group rate. The hotels require a room deposit guaranteed with a major credit card. Rooms for Saturday night (May 16) are very limited because of the annual Chicago Restaurant Convention. Therefore, attendees SHOULD BOOK THEIR HOTEL ROOM FIRST and only then purchase a plane ticket second. The Talbott is only a two-minute walk away from the conference site but has fewer rooms available. The Days Inn is a fifteen-minute walk away from the conference site. Please see the ICCL web page http://www.math.luc.edu/iccl98/ for details. TRANSPORTATION United Airlines is offering a 10% discount off the unrestricted mid-week coach fare or 5% discount off the lowest applicable fares, including First Class, to all attendees of ICCL '98. This special offer applies to travel on domestic segments of all United Airlines, United Express and Shuttle-by-United flights. See the ICCL web page for details. Information about transportation from the Chicago airports to the hotels and conference site is also available from the ICCL web page. CONTACT PERSONS Local Arrangements Chair: Publications Chair: Konstantin La"ufer Christopher Colby Loyola University Chicago Loyola University Chicago laufer(a)cs.luc.edu colby(a)cs.luc.edu Program Committee Co-Chairs: Purush Iyer Young-il Choo North Carolina State University Gifford-Fong Associates purush(a)csc.ncsu.edu yic(a)gfa-genesis.com Conference Chair: David Schmidt Kansas State University schmidt(a)cis.ksu.edu ============================================================================== WORKSHOP ON INTERNET PROGRAMMING LANGUAGES On May 13, a pre-conference Workshop on Internet Programming Languages will be conducted at Loyola University. Interested parties should contact one of the organizers: Henri Bal, Vrije Universiteit, The Netherlands, bal(a)cs.vu.nl Boumediene Belkhouche, Tulane University, USA, bb(a)eecs.tulane.edu Luca Cardelli, Microsoft Research, Cambridge, UK, luca(a)luca.demon.co.uk The workshop program is located at http://www.math.luc.edu/iccl98/ipl-program.html Information about attendance and registration will be available soon from the above URL and through a separate Call For Participation.

1 0

Call for participation: MPC'98
by johanj＠relay.cs.ruu.nl 13 Mar '98

13 Mar '98

Call for participation: MPC '98 Fourth International Conference on MATHEMATICS OF PROGRAM CONSTRUCTION ----------------------------------- http://www.md.chalmers.se/Conf/MPC98/ June 15 - 17, 1998 Marstrand, Sweden Post-conference workshops: * Workshop on Generic Programming, WGP'98 http://www.cse.ogi.edu/PacSoft/conf/wgp/ * International Workshop on Constructive Methods for Parallel Programming, CMPP'98 http://brahms.fmi.uni-passau.de/cl/cmpp98/index.html * Formal Techniques for Hardware and Hardware-like Systems, FTH'98 http://www.cs.chalmers.se/~ms/FTH98/ The general theme of this series of conferences is the use of crisp, clear mathematics in the discovery and design of algorithms and in the development of corresponding software or hardware. The conference theme reflects the growing interest in formal, mathematically based methods for the construction of software and hardware. The goal of the MPC conferences is to report on and significantly advance the state of the art in this area. Previous conferences were held in 1989 at Twente, The Netherlands, organised by the Rijksuniversiteit Groningen, in 1992 at Oxford, United Kingdom, and in 1995 at Kloster Irsee, Germany, organised by Augsburg University. Invited speakers: Burghard von Karger (Kiel University) John Hughes (Chalmers Technical University) David Harel (Weizmann Institute) CONFERENCE PROGRAMME Monday June 15 1998 8.50 - 9.00 Welcome 9.00 - 10.00 Invited talk: A proof rule for control loops Burghard von Karger (Kiel University) 10.00 - 10.30 Break Session 1. Chair: Roland Backhouse (Eindhoven University of Technology) 10.30 - 11.15 Polytypic Downwards Accumulations Jeremy Gibbons (Oxford Brookes University) 11.15 - 12.00 Nested Datatypes Richard Bird (Oxford University) and Lambert Meertens (CWI Amsterdam and Utrecht University) 12.00 - 1400 Lunch Session 2. Chair: Richard Bird (Oxford University) 14.00 - 14.45 Layered Graph Traversals and Hamiltonian Path Problems - An Algebraic Approach Thomas Brunn, Bernhard M�ller, and Martin Russling (Augsburg University) 14.45 - 15.30 Computing Spanning Trees Rudolf Berghammer, Burghard von Karger and Andreas Wolf (Kiel University) 15.30 - 16.00 Break Session 3. Chair: Bernhard M�ller (Augsburg University) 16.00 - 16.45 Computation Calculus - Bridging a Formalization Gap Rutger M. Dijkstra (Groningen University) 16.45 - 17.30 A Unifying Framework for Correct Program Construction Henning Dierks and Michael Schenke (University of Oldenburg) Tuesday June 16 1998 9.00 - 10.00 Invited talk: Generalising Monads John Hughes (Chalmers Technical University) 10.00 - 10.30 Break Session 4. Chair: Eerke Boiten (University of Kent at Canterbury) 10.30 - 11.15 Calculating a Round-Robin Scheduler Matteo Vaccari (University of Milano) and Roland Backhouse (Eindhoven University of Technology) 11.15 - 12.00 Formal derivaton of a loadable asynchronous counter Mark B. Josephs (South Bank University London) 12.00 - 1400 Lunch Session 5. Chair: Jose Oliveira (University of Minho at Braga) 14.00 - 14.45 An application of program derivation techniques to 18th century mathematics A. Bijlsma (Eindhoven University of Technology) 14.45 - 15.30 An Approach to Object-Orientation in Action Systems Kaisa Sere, (�bo Akademi University) Joost Kok and Marcello Bonsangue (Leiden University) 15.30 - 16.00 Break Session 6. Chair: Robin Cockett (University of Calgary) 16.00 - 16.45 Beyond Fun: order and membership in polytypic imperative programming David A. Naumann (Stevens Institute of Technology) 16.45 - 17.30 Realizability for Monotone Coinductive Definitions and Its application to Program Synthesis Makoto Tatsuta (Kyoto University) Wednesday June 17 1998 9.00 - 10.00 Invited talk: On the Aesthetics of Diagrams David Harel (Weizmann Institute) 10.00 - 10.30 Break Session 7. Chair: Sigurd Meldal (CalPoly) 10.30 - 11.15 Convergence of Program Transformers in the Metric Space of Trees Morten Heine Sorensen (University of Copenhagen, DIKU) 11.15 - 12.00 A set-theoretic model for real-time specification and reasoning C.J. Fidge, I.J. Hayes, A.P. Martin and A.K. Wabenhorst (University of Queensland) 12.00 - 1400 Lunch Session 8. Chair: Christian Lengauer (University of Passau) 14.00 - 14.45 An elementary derivation of the Alternating Bit Protocol W.H.J. Feyen, A.J.M. van Gasteren (Eindhoven University of Technology) and Birgit Schieder (M�nchen Technical University) 14.45 - 15.30 Slack elasticity in concurrent computing Rajit Manohar and Alain J. Martin (Caltech) 15.30 - 16.00 Break Session 9. Chair: Mary Sheeran (Chalmers Technical University) 16.00 - 16.45 A Semantic Approach to Secure Information Flow K. Rustan M. Leino (DEC SRC) and Rajeev Joshi (University of Texas, Austin) 16.45 End of Mathematics of Program Construction 1998 VENUE Marstrand is a small island on the beautiful westcoast of Sweden, 40 km from G�teborg. The charming old houses, the fortress, the walking paths, and the absence of cars make this island a very pleasant resort. There are direct flights to G�teborg Landvetter from most European main cities, and busses from G�teborg to Marstrand. PROGRAMME COMMITTEE Ralph-Johan Back Finland Roland Backhouse The Netherlands Richard Bird UK Eerke Boiten UK Dave Carrington Australia Robin Cockett Canada David Gries USA Lindsay Groves New Zealand Wim Hesselink The Netherlands Zhenjiang Hu Japan Barry Jay Australia Johan Jeuring Sweden (Chair) Dick Kieburtz USA Christian Lengauer Germany Lambert Meertens The Netherlands Sigurd Meldal Norway Bernhard M�ller Germany Chris Okasaki USA Jose Oliveira Portugal Ross Paterson UK Mary Sheeran Sweden Doug Smith USA LOCAL ORGANISATION MPC '98 is organised by the Computing Science department of Chalmers University of Technology and University of G�teborg. The organisation committee consists of the following people: Patrik Jansson Johan Jeuring Marie Larsson Mary Sheeran

1 0

Re: Bill Fest (fwd)
by Michael Barr 12 Mar '98

12 Mar '98

I remind everyone of the Billfestschrift. > > > > Date: Wed, 1 Oct 1997 10:30:58 GMT > > From: Michael Barr <barr(a)triples.math.mcgill.ca> > > > > A special issue of JPAA will be devoted to papers for the Billfest. The > > deadline for submission is March 31, 1998 and may be sent to one of > > the three editors, Myles Tierney, Ieke Moerdijk or me. > > > > Michael > > > > > >

1 0

5th WoLLIC'98 - 3rd Call
by Ruy de Queiroz 12 Mar '98

12 Mar '98

Third Call for Contributions 5th Workshop on Logic, Language, Information and Computation (WoLLIC'98) July 28-31, 1998 ! TUTORIALS >> (Tutorial Day: July 28th) << TUTORIALS ! IME-USP, Sao Paulo, Brazil The "5th Workshop on Logic, Language, Information and Computation" (WoLLIC'98), the fifth version of a series of workshops which started in 1994 with the aim of fostering interdisciplinary research in pure and applied logic, will be held in Sao Paulo, Brazil, from July 28th to 31st 1998. Contributions are invited in the form of short papers (6 10pt pages or 1800 words) in all areas related to logic, language, information and computation, including: pure logical systems, proof theory, model theory, algebraic logic, type theory, category theory, constructive mathematics, lambda and combinatorial calculi, program logic and program semantics, logics and models of concurrency, logic and complexity theory, nonclassical logics, nonmonotonic logic, logic and language, discourse representation, logic and artificial intelligence, automated deduction, foundations of logic programming, logic and computation, and logic engineering. The 5th WoLLIC'98 has the scientific sponsorship of the Interest Group in Pure and Applied Logics (IGPL), the European Association for Logic, Language and Information (FoLLI), the Association for Symbolic Logic (ASL), the Sociedade Brasileira de Computacao (SBC), and the Sociedade Brasileira de Logica (SBL). There will be a number of guest speakers, including: Sergei Artemov (Moscow State Univ, Russia) (CONFIRMED), Sam Buss (Univ Calif San Diego, US) (CONFIRMED), Edmund Clarke (Carnegie-Mellon Univ, US) (CONFIRMED), Heinz Dieter Ebbinghaus (Universitaet Freiburg, Germany) (CONFIRMED), Michael Fourman (Edinburgh Univ, UK) (CONFIRMED), Dov Gabbay (Imperial Coll, UK) (*), Ehud Hrushovski (Hebrew Univ Jerusalem, Israel) (*), Hans Kamp (Stuttgart Univ, Germany) (CONFIRMED), Phokion Kolaitis (Univ Calif Santa Cruz, US) (*), Valeria de Paiva (Birmingham Univ, UK) (CONFIRMED), Maarten de Rijke (Amsterdam Univ, The Netherlands) (CONFIRMED), Giovanni Sambin (Padoa Univ, Italy) (CONFIRMED). (*) TO BE CONFIRMED Submission: Papers (sent preferably in LaTeX format by e-mail to ** wollic(a)ime.usp.br **, or in 5(five) copies to postal address) must be RECEIVED by APRIL 3rd, 1998 by one of the Co-Chairs of the Organising Committee. Papers must be written in English and give enough detail to allow the programme committee to assess the merits of the work. Papers should start with a brief statement of the issues, a summary of the main results, and a statement of their significance and relevance to the workshop. References and comparisons with related work is also expected. Technical development directed to the specialist should follow. Results must be unpublished and not submitted for publication elsewhere, including the proceedings of other symposia or workshops. One author of each accepted paper will be expected to attend the conference in order to present it. Authors will be notified of acceptance by MAY 15th, 1998. The abstracts of the papers will be published in a "Conference Report" section of the Logic Journal of the IGPL (ISSN 1367-0751) (Oxford Univ Press) as part of the meeting report. Papers presented at the meeting will be invited for submission (in full version) to the Logic Journal of the IGPL (http://www.oup.co.uk/jnls/igpl/) The WoLLIC'98 is hosted by Universidade de Sao Paulo (USP), and will take place at the Mathematics and Statistics Institute (IME). Programme Committee: Andreas Blass (Michigan Univ, USA), Itala D'Ottaviano (Univ Campinas, BR), J. Michael Dunn (Indiana Univ, USA), Wilfrid Hodges (Queen Mary Coll, UK), Francisco Miraglia (Univ Sao Paulo, BR), Luiz Carlos Pereira (Cathol Univ Rio, BR), Andrew Pitts (Cambridge Univ, UK), Amir Pnueli (Weizmann Inst, Israel). Organising Committee: L. S. C. Baptista (UFPE/UFPB), M. Finger (USP), E. Hermann Haeusler (PUC-Rio), A. C. V. de Melo (USP), A. G. de Oliveira (UFBA/UFPE), R. de Queiroz (UFPE), F. C. da Silva (USP). For further information, contact the Co-Chairs of the Organising Committee: Ruy de Queiroz, Departamento de Informatica, Univ. Federal de Pernambuco, CP 7851, 50732-970 Recife, PE, Brazil, e-mail: ruy(a)di.ufpe.br, tel.: (+55 81) 271 8430, fax: (+55 81) 271 8438. Marcelo Finger, Departamento de Ciencia da Computacao, Instituto de Matematica e Estatistica, Universidade de Sao Paulo, Rua do Matao 1010, 05508-900 Sao Paulo, SP, Brazil, e-mail: mfinger(a)ime.usp.br, tel.: (+55 11) 818 6287, fax: (+55 11) 818 6134. Web page: http://www.ime.usp.br/~wollic

1 0

PSSL'66
by Neil Ghani 11 Mar '98

11 Mar '98

If you intend to attend, please make the organisation of this meeting easier by registering now. A detailed program will be circulated soon. **** Final Announcement and Registration **** The 66th Peripatetic Seminar on Sheaves and Logic March 28-29, 1998 University of Birmingham England The 66th meeting of the PSSL will be held at the University of Birmingham, England, over the weekend of 28-29 March 1998. Since its inception, the focus of the PSSL has broadened and now includes talks related to category theory, logic and theoretical computer science. The meetings are informal in nature and talks on work in progress is welcome. We have arranged bed and breakfast in the University House which will cost 23 pounds per night. In addition, a buffet lunch and tea/coffee will be provided on Saturday and Sunday at a cost of 8 pounds per day. Student participation is particularly encouraged at this meeting and hence we have been granted a small fund to help with the costs of attendence for students. Those interested in this offer should contact the organisers as soon as possible. All payments should be by cash or cheque (travellers cheques are acceptable). There are several ATM machines on campus. Participants may wish to plan their arrival so that they may attend our 3pm Friday afternoon theory seminar at which Paul Taylor will be our guest speaker. This document, campus maps and travel information can be found at the following URLs. http://www.bham.ac.uk/general/intro/vguide.htm http://www.cs.bham.ac.uk/~nxg/pssl66.html ** REGISTER NOW !!! ** Please send the following registration information via email to nxg(a)cs.bham.ac.uk by Monday 16 March and include the phrase PSSL in the title. THIS DEADLINE IS IMPORTANT AS AFTERWARDS WE CANNOT GUARANTEE ACCOMODATION ETC. Please make cheques payable to the "University of Birmingham" in sterling. Once we have received your registration we shall send further details concerning the programme etc Name: Job title: Affiliation: Address: email: phone: fax: presentation? (yes/no): title: Bed and Breakfast: Friday Night @ 23.00: Saturday Night @ 23.00: Lunch, Tea, Coffee : Saturday @ 8.00: Sunday @ 8.00: Total Cost:

1 0

Memorial article
by Peter Freyd 07 Mar '98

07 Mar '98

The AMS Notices will publish a memorial article for Sammy. These projects are put together in a hurry and who gets asked to submit remarks is something of a random process. In this case it's Hyman Bass, Henri Cartan, Alex Heller, Saunders Mac Lane and I. Hy will also provide a narrative vita. Please send me material you'd like included. If I get too many suggestions, I will, with your permission, not include any of them in the Notices but will publish -- after the Notices -- memorial pages in the JPAA.

2 1

ANNOUNCING: Xy-pic version 3.6 released!
by krisrose＠sauternes.ens-lyon.fr 06 Mar '98

06 Mar '98

Dear Category Theorists, Please find enclosed a copy of the TRAILER for a new version of Xy-pic! Sincerely, Kristoffer H. Rose ======================================================================= ANNOUNCING the Xy-pic version 3.6 DIAGRAM TYPESETTING PACKAGE ======================================================================= This is to announce a release of my diagram typesetting package Xy-pic. Version 3.6 contains new and improved PostScript fonts donated by Y&Y Inc. (as well as several minor bug fixes). ----------------------------------------------------------------------- GENERAL ----------------------------------------------------------------------- Xy-pic is a package for typesetting a variety of graphs and diagrams with TeX. Xy-pic works with most formats (including LaTeX, AMS-LaTeX, AMS-TeX, and plain TeX), in particular Xy-pic is provided as a LaTeX2e `supported package' (following the `CTAN LaTeX2e bundle' standard). Further specifics of the package are in the distribution README file. ----------------------------------------------------------------------- NEWS ----------------------------------------------------------------------- The primary purpose of release 3.6 is the inclusion of much improved PostSript fonts courtesy of Y&Y TeX and several Internetwide volunteers: these make it possible to use Xy-pic output with Windows (in addition to Macintosh and Un*x), Adobe's ATM software, and to produce Adobe PDF ("Acrobat") files. NOTE: This change means that you must REMOVE SOME OLD FONT FILES (the details of which and how are in the INSTALL file). Release 3.6 furthermore fixes a few problems of release 3.5: * frames more robust against disappearing on bogus PostScript printers * thickness of curves now adjustable * TDS compliance improved * bogus `graph escape redefined' message eliminated Thanks to David Carlisle, John Landamore, Ralph Loader, Thorsten Schwander, and Timco Visser, for your bug reports, and to Adam Worrall, Thierry Bouche, Tanmoy Bhattacharya and especially to Berthold Horn and Louis Vosloo of Y&Y Inc. for their work on the PostScript fonts. Finally profound thanks to BRICS and DAIMI for hosting Xy-pic (and Kristoffer :) for a most productive and enjoyable year! ----------------------------------------------------------------------- AVAILABILITY ----------------------------------------------------------------------- Xy-pic can be retrieved through the World Wide Web Xy-pic `home pages': URL: http://www.ens-lyon.fr/~krisrose/Xy-pic.html URL: http://www.mpce.mq.edu.au/~ross/Xy-pic.html as well as by anonymous ftp from CTAN: macros/generic/diagrams/xypic and from the private TeX archives of the authors: ftp.ens-lyon.fr : /pub/users/LIP/krisrose/TeX/ ftp.mpce.mq.edu.au : /pub/maths/TeX/ Check the README file in each location for specifics, in particular check that you have reached a version 3.6 copy (some archives take a while to mirror the latest files)! ----------------------------------------------------------------------- HISTORY & CREDITS ----------------------------------------------------------------------- The first public release (version 1.40) of Xy-pic was created by Kristoffer H. Rose, DIKU, U of Copenhagen (now ENS-Lyon, France) and distributed via Usenet on December 19, 1991. This quickly became version 2 of which version 2.6 was the most stable. The thorough rewrite that became version 3 is a continued collaboration with Ross Moore, Macquarie U, Sydney, initiated through a visit to Macquarie (Jan-May 1994 supported by the Australian Research Council, Macquarie University, and using donated DEC equipment). However, full backwards compatibility is maintained (except for the unavoidable but fully documented obscure cases). Xy-pic is Copyright (c) 1991-1998 by Kristoffer H. Rose and 1994-1998 by Ross Moore under GNU COPYLEFT which means that you can use the package for any purpose but if you provide the macros or any code derived from them to a third party then you are obliged to include the entire Xy-pic package (full details in the file COPYING). The PostScript fonts are additionally Copyright (c) 1997 Y&Y Inc. ---------------------------------------------------- This is the end of the announcement. Enjoy Xy-pic! ----------------------------------------------------------------------- Kristoffer H�gsbro Rose, Ph.D., prof.associ� <Kristoffer.Rose(a)ENS-Lyon.FR> Laboratoire de l'Informatique du Parall�lisme �quipe PLUME, bureau LR5-026 Ecole Normale Sup�rieure de Lyon; 46, All�e d'Italie; F-69364 Lyon 07 cedex phone: +33(0)4 7272 8642; fax:...8080 <http://www.ens-lyon.fr/~krisrose>

1 0

Uday's question
by Reinhold Heckmann 05 Mar '98

05 Mar '98

When reading the last message of Uday Reddy, I got three ideas. 1) Several people have pointed out that naturality is impossible. Yet a weaker form of naturality may be appropriate. Consider existential quantification on sets. If f: A -> B is a function and p: B -> M (= Bool) a predicate, then exists x in A: p(fx) iff exists x in f(A): p x This suggests to require naturality E_A (p o f) = E_B p for *epis* f: A -> B only. 2) Uday Reddy asked about the significance of the third equation: E_A(\x. E_B(\y.hxy)) = E_B(\y. E_A(\x.hxy)) This equation looks a bit like the Foubini theorem in integration theory. The difference is that in Foubini's theorem, there is a third mediating term, whose analogue would be E_(A x B) (\(x,y). hxy) . [Distinguish the product symbol x in A x B from the variable x.] 3) The analogy with integration also shows that something may be missing from the present setting: The integral depends on the function to be integrated and also on a measure. It is in fact an operator I_A: [A->M] x M(A) -> M where M are the (non-negative?) reals with the multiplicative monoid structure, and M(A) is the set of measures on A. [Distinguish the operator M from the monoid M. Yet there is some connection: M(1) = M if M is taken to consist of the non-negative reals.] Now, we get I_A(\x. a * gx, m) = a * I_A(g, m) I_A(\x. gx * a, m) = I_A(g, m) * a by linearity of integration, and I_A(\x.1, m) = m(A) (= 1, if only normalised measures are considered, but then M = M(1) is lost) Of course, integration has many more properties, e.g. additivity in the function, and linearity in m. The last equation becomes I_A (\x. I_B (\y. hxy, mb), ma) = I_B (\y. I_A (\x. hxy, ma), mb) = I_(A x B) (\(x,y). hxy, ma x mb) with the product measure ma x mb. There is also kind of naturality, namely the law of substitution: For f: A -> B, I_A (p o f, ma) = I_B (p, ma o f^-1) (for p: B -> M and ma in M(A) ). This becomes a bit more categorical by noting that M(-) is a functor with M(f) (ma) = ma o f^-1 and so I_A ( [f->] p, ma) = I_B (p, M(f) ma) . Much of this can be formulated abstractly with a functor M. For the mediating term of the Foubini theorem, a natural transformation x_AB: M(A) x M(B) -> M(AxB) is needed to form the product measure. It may be useful to introduce a natural transformation eta_A: A -> M(A), giving point measures. I_A (p, eta_A(x)) = p(x) holds for p: A -> M and x in A. The transformation x_AB induces a binary operation on M(1) = M(1 x 1), and for 1 = {()}, eta_1 () is an element of M(1). This gives a monoid structure on M(1), giving back the original monoid M. Back to existential quantification: =================================== Take M(A) = P(A), the powerset of A, and M = P(1) = Bool and define E_A (p, S) = exists x in S: p(x) for p: A -> M and S in P(A). Then all the equations for integration hold (with x_AB : P(A) x P(B) -> P(A x B) being cartesian product and eta_A(x) = {x} ) Instead of considering E_A: [A->M] x P(A) -> M, one may, using CC, also consider E'_A: P(A) -> [[A->M]->M] . This is even a monad homomorphism from the power set monad to the monad [[- -> M] -> M] (known as continuation monad with "final answers" M). A similar thing is possible in the category of domains, with P being some power domain construction (see my paper "Power Domains and Second Order Predicates", TCS 111, 59 - 88 (1993) ). Maybe, this is the essence of Uday's work: defining a monad homomorphism from some monad used in the semantic description of a language to the continuation monad. Regards, Reinhold Heckmann Universitaet des Saarlandes

1 0

Master Class in Logic - Reminder
by Jaap van Oosten 04 Mar '98

04 Mar '98

MASTER CLASS IN MATHEMATICAL LOGIC - REMINDER Dear colleagues, This is to remind you of the Master Class in Logic which will be held in Utrecht, the Netherlands, and for which we posted an ad some time ago. The deadline for applications of students who wish to participate but do not need funding is June 1st; students who wish to apply for a funding may still do so IF THEIR APPLICATION REACHES US (that is: Marian Brands, at the Department of Maths., Utrecht University) BEFORE THE END OF NEXT WEEK. We let the text of the original message follow: In the academic year 1998-1999 the Universities of Utrecht and Nijmegen organize, as part of the MRI Master Class, a year-long education program in Mathematical Logic. The program is aimed at students who intend to enter a Ph.D.-program in the subsequent year. The courses are in English and foreign students are specifically invited to apply. A limited number of stipends are available. The contents of the program are detailed in a brochure which exists both as hard copy and electronically. The text can be seen on the homepage of the Mathematical Research Institute. URL: http://www.math.ruu.nl/mri If you're interested in receiving a hard copy of the brochure, please send a message to Marian Brands, at brands(a)math.ruu.nl Thank you, Jaap van Oosten Ieke Moerdijk Harold Schellinx ----- End Included Message ----- ----- End Included Message -----

1 0