[Past issues of the newsletter are available at http://www.bell-labs.com/topic/conferences/lics/ LOGIC COLLOQUIUM 97 European Summer Meeting of the Association for Symbolic Logic University of Leeds UK 6 - 13 July 1997, Scientific Programme 7 - 12 July * Short course lecturers. R. Shore (Cornell), A. Wilkie (Oxford), M. Rathjen (Leeds), J. Steel (Berkeley). * Plenary lecturers. P. Benacerraf (Princeton), U. Berger (Munich), L. van den Dries (Urbana), S. Goncharov (Novosibirsk), R. Jensen (Berlin), N. Jones (Copenhagen), B. Kim (Fields Inst), J. Knight (Notre Dame), I. Neeman (UCLA), L. Newelski (Wroclaw), J. van Oosten (Amsterdam), D. Over (Sunderland), P. Pudlak (Prague), G. Sacks (Harvard), R. Soare (Chicago), S. Solecki (UCLA), L. Rips (North Western), L. Wallen (Oxford). * Special sessions. There will in addition be special sessions in the main topics, and sessions for short contributed talks (deadline for receipt of abstracts 6 April 97). Special sessions will be chaired by: Computability Theory: K. Ambos-Spies (Heidelberg), S. Lempp (Madison). Model Theory: A. Pillay (Urbana). Proof Theory: H. Schwichtenberg (Munich), G. Jaeger (Bern). Set Theory: S. Friedman (MIT). * Further information. Logic Colloquium 97, School of Mathematics, The University of Leeds, Leeds LS2 9JT, UK. e-mail: logic97@amsta.leeds.ac.uk. KANELLAKIS AWARD Call for Contributions * The Association for Computing Machinery has instituted a "Kanellakis Award for a theoretical contribution with a significant impact on practice". This award is in memory of Paris C. Kanellakis, who perished in a tragic airplane accident in December 1995. The first Kanellakis Award was given at ACM '97 to Adelman, Diffie, Hellman, Merkle, Rivest, and Shamir for their work on public-key cryptography. * So far, $80,000 have been raised from SIGACT, SIGMOD, the Kannelakis family, and PWS publishing, towards the award endowment. Additional $20,000 are needed to allow the award to be given every year. We should like to provide an opportunity for friends and colleagues of Paris to contribute to the award endowment. We invite pledges to honor Paris and the tradition of scholarly excellence he embodied. Please indicate the amount you wish to pledge by sending email to shp@cs.brown.edu or writing to the following address: ACM Kanellakis Award, c/o Susan Platt, Box 1910, Dept of Computer Science, Providence, RI 02912. ACM will then contact you concerning your (tax deductible) contribution. * Further information. Contact any member of the award committee: David Johnson (dsj@research.att.com), Tom Leighton (ftl@math.mit.edu), Christos Papadimitriou (christos@cs.berkeley.edu), Moshe Vardi (vardi@cs.rice.edu), and Peter Wegner (pw@cs.brown.edu). BOOLE 1997 One hundred fifty years of mathematical analysis of logic September 26-27, 1997 University of Lausanne, Switzerland. * This conference is being organized by the Swiss Society for Logic and Philosophy of Sciences. Confirmed speakers include M.-J. Durand-Richard, I. Grattan-Guinness, T. Hailperin, S. Nambiar, M. Panteki, V. Peckhaus, S. Rahman and N. Vassallo. Further information may be obtained from J. Gasser, Institut de mathematiques appliquees, BFSH2, Universite de Lausanne, CH-1015 Lausanne, Switzerland; telephone: 41-21-692-3124; fax: 41-21-692-3125; e-mail: james.gasser@imaa.unil.ch. BOOK ANNOUNCEMENT Bounded Variable Logics and Counting -- A Study in Finite Models Martin Otto Lecture Notes in Logic, vol.9, Springer-Verlag, 1997. ISBN 3-540-62037-0. * This monograph in finite model theory offers a comprehensive treatment of results in the model theory and descriptive complexity theory of infinitary logics with a bounded number of variables and logics with counting constructs. The exposition is largely self-contained, with introductory sections on the relevant logics, model theoretic concepts, and the programme of descriptive complexity. BOOK ANNOUNCEMENT Semantics and Logics of Computation Edited by Andrew M Pitts and P Dybjer Cambridge University Press, January 1997, UKL 35.00 ISBN 0521580579 * The aim of this volume is to present modern developments in semantics and logics of computation in a way that is accessible to graduate students. The book is based on a summer school at the Isaac Newton Institute and consists of a sequence of linked lecture courses. The authors are leaders in their fields and much of material they present was either not previously accessible, or not accessible in such a digestible form. * Contents. S. Abramsky, Semantics of interaction: an introduction to game semantics. T. Coquand, Computational content of classical logic. M. Hofmann, Syntax and semantics of dependent types. M. Hyland, Game semantics. E. Moggi, Metalanguages and applications. A. Pitts, Operationally-based theories of program equivalence. G. Winskel and M. Nielsen, Categories in concurrency. DIMACS WORKSHOP: LOGIC AND ALGORITHMS -- ONE YEAR LATER Rutgers University, July 23-25, 1997 * The 1995-1996 Special Year on Logic and Algorithms (SYLA) was aimed at bridging a dichotomy in computer science between two major branches of research, one in algorithms and complexity, and the other one in models and semantics. SYLA focused on three bridge areas: computer-aided Verification, finite-model Theory, and proof complexity. Computer-Aided Verification studies algorithms and structures for verifying properties of programs. Finite-model theory studies the logical properties of finite structures, and has intimate connections with complexity theory and database theory. Proof complexity studies the length of proofs and the complexity of the inference steps within the proof. SYLA consisted of a 3-week long summer school, 11 workshop, and a federated logic conference. * We are now planning to hold a DIMACS Workshop on "Logic and Algorithms: One Year Later", to take place at Rutgers University, on July 23-25, 1997. The goal of the workshop is to follow up on SYLA. The workshop will cover the three major topics of the Special Year, computer-aided verification, finite-model theory, and proof complexity. We are inviting to the workshop people who participated in the Special Year. We would like them to report on research results that arose during the Special Year or following it. During the Special Year, we conducted many specialized workshops. In this workshop, we are trying to bring the three topics together, in an attempt to provide participants with a broader view of the field. * Organizers: Eric Allender, Robert Kurshan, Moshe Vardi. SUMMER SCHOOL AND WORKSHOP ON NEW PARADIGMS FOR COMPUTATION ON CLASSICAL SPACES Birmingham, 8-10 September 1997 and 11-13 September 1997 * The two events are centered around recent developments in the theory of continuous domains as applied to classical problems in Mathematics and Semantics. These developments are based on ground-breaking work by Abbas Edalat who, using earlier work by Jimmie Lawson, Claire Jones and Gordon Plotkin, showed in the early 90's how a classical (locally compact) space could be embedded as the set of maximal points in a domain. This led to a new theory of integration with applications in the theory of Iterated Function Systems, Neural Networks, Statistical Physics, and Fractal Geometry. More recently, Abbas Edalat and Martin Escardo have made substantial progress on the question of exact real number computation. The Summer School is intended to teach the mathematical background of the theory enabling participants to fully take part in the following Workshop. A small number of grants for the Summer School are available for PhD students. TENTH EUROPEAN SUMMER SCHOOL IN LOGIC, LANGUAGE AND INFORMATION (ESSLLI-98) August 17 - 28, 1998, Saarbruecken, Germany Call for proposals * The ESSLLI-98 Programme Committee invites proposals for introductory and advanced courses, workshops and panels for the 10th annual Summer School on a wide range of topics in the following fields: Logic, Language, Computation, Language and Logic, Logic and Computation, Language and Computation. In addition to courses, workshops and panels, there will be a Student Session. A Call for Papers for the Student Session will be distributed separately. While the Programme Committee welcomes proposals in all of the above areas, for advanced courses, workshops and panel discussions it would especially like to encourage proposals that emphasize cognitive aspects. * Proposal submission. All proposals should be submitted by electronic mail to the program chair, at esslli98@dcs.warwick.ac.uk, in plain ASCII text as soon as possible, but no later than June 15, 1997. Authors of proposals will be notified of the committee's decision no later than September 1, 1997. Proposers should follow the guidelines below while preparing their submissions; proposals that deviate substantially will not be considered. BRICS INTERNATIONAL PHD SCHOOL IN COMPUTER SCIENCE University of Aarhus, Denmark Announcement and Call for Applications * An international PhD School in computer science is opening at the University of Aarhus. This is its initial call for admissions and grant applications. The School is an integrated part of the BRICS (Basic Research in Computer Science) Research Centre, and both are funded by the Danish National Research Foundation. The school admits 10-12 students annually, and provides a substantial number of grants for Danish as well as foreign students. The PhD School wishes to recruit foreign PhD students of the highest international standards. It provides an excellent research environment and scientific training facilities, and aims at making its PhD graduates attractive for a wide spectrum of employers - in private and public research and development institutions, both in Denmark and abroad. * Further information: URL above or phdschool@brics.dk. * Application form: http://www.brics.dk/PhDSchool/Application.html. EUROPEAN JOINT CONFERENCES ON THEORY AND PRACTICE OF SOFTWARE (ETAPS'98) Lisbon, Portugal March 30 - April 3, 1998 * The European Joint Conferences on Theory and Practice of Software (ETAPS) is a new annual meeting covering a wide range of topics in Software Science which will take place in Europe each spring in the slot currently occupied by CAAP/ESOP/CC and TAPSOFT. ETAPS is a loose and open confederation of existing and new conferences and other events which aims to become the primary European forum for academic and industrial researchers working on topics relating to Software Science. * Invited speakers. for 1998 are: Kent Beck. Randy Bryant. Margaret Burnett. Cliff Jones. Michael Mislove. Amir Pnueli. Gert Smolka. * Call for papers. The call for papers is now open for the five main conferences of ETAPS'98, with a submission deadline of October 6, 1997. See the ETAPS web page for more details about the scope and submission instructions of each individual conference. MATHFIT SUMMERSCHOOL IN EDINBURGH Games and Computation Laboratory for the Foundations of Computer Science June 23-24, 1997 * The use of games to model various aspects of computation has been notably successful over the past few years. In particular, two areas where there has been rapid progress recently are: game semantics and its applications to programming languages and logic; and the use of games in verifying properties of concurrent processes. Game semantics has been used to give the first syntax-independent constructions of fully abstract models for functional languages such as PCF and FPC, for imperative languages such as Idealized Algol, and for languages with non-local control operators such as call-cc. There are promising applications to object-oriented languages in progress. * Speakers. Samson Abramsky, Martin Hyland, Perdita Stevens, Colin Stirling, Wolfgang Thomas, * Grants. A small number of grants for the Summer School are available for PhD students. * Further information. See the URL above. FIRST PANHELLENIC SYMPOSIUM ON LOGIC July 21-24 1997 Nicosia, Cyprus * In its modern form Logic manifests itself as a fundamental area in many other disciplines such as Mathematics, Computer Science, Philosophy, Law and others. This Symposium aims to bring together researchers from these various disciplines to address modern developments in logic. In particular, the symposium aims to promote cross-fertilization amongst developments and needs in these different disciplines and evaluate the overall significance of Logic as a unifying basic discipline. * Invited speakers. I. Antoniou, C. Dimitrakopoulos, T. Feidas, L. Kirousis, P. Kolaitis, G. Metakides, C. Papadimitriou, E. Papadopetrakis, J. Sifakis, S. Zachos. * Submission. Papers are invited on all aspects of Logic from researchers who are interested in participating. Position papers on open problems in Logic or the relationship and relevance of logic in other areas are particularly encouraged. Papers must be short not exceeding five pages. They can be written in either English or Greek and should be sent to Panhellenic Symposium on Logic, Department of Computer Science, University of Cyprus, P.O.Box 537, CY-1678 Nicosia, Cyprus. Fax: +357-2-339062, before May 31, 1997. Papers can be sent either in hard copy form or electronic form. Authors are requested to classify their work in one of the following domains: 1. Formal Logic, 2. Logic in Computer Science, 3. Logic, Sciences and Philosophy, 4. Other (please specify). * Further information. E-mail: antonis@turing.cs.ucy.ac.cy. EIGHTH INTERNATIONAL CONFERENCE ON CONCURRENCY THEORY (CONCUR'97) Call for participation July 1 - 4, 1997 Warsaw, Poland REWRITING TECHNIQUES AND APPLICATIONS (RTA 98) Call for papers March 30 - April 1, 1998 Tsukuba, Japan * Topics. Term rewriting systems, symbolic and algebraic computation, unification and matching, completion techniques, string and graph rewriting, conditional and typed rewriting, rewriting-based theorem proving, parallel rewriting and deduction, constrained rewriting and deduction, constraint solving, higher-order rewriting, lambda-calculi, functional and logic programming languages. * Submissions. Research papers (up to 15 pages), system descriptions (4 pages) or problem sets must be submitted in postscript form to rta98@informatik.tu-muenchen.de. Alternatively, 6 hardcopies may be sent to: Prof. T. Nipkow, Institut fuer Informatik, TU Muenchen, 80290 Muenchen, Germany. * Dates. Submission deadline: September 28, 1997. Notification of acceptance or rejection: December 1, 1997. Final papers due: January 12, 1998. * Best student paper award. A prize of $500 will be given to the best paper, as judged by the program committee, written solely by one or more students. * Program committee. J. Avenhaus, F. Baader, R. Di Cosmo, M. Fernandez, H. Ganzinger, M. Hanus, D. Kapur, A. Middeldorp, T. Nipkow (Chair), V. van Oostrom, M. Oyamaguchi, R. Treinen. * Local arrangements. Aart Middeldorp and Tetsuo Ida, University of Tsukuba, Tsukuba, Japan. * Invited speakers. Hubert Comon, Jan Willem Klop, Gordon Plotkin. POSITION in COMPUTER SCIENCE University of Munich * C1 position in Theoretical Computer Science is available at the University of Munich (Ludwig-Maximilians-Universitaet Muenchen) with starting date July 1, 1997. Initial contract for period up to 3 years, with a possibility of extension thereafter for another 3 years [2 years in case of doctoral students]. * Research interests of our current group include (a) lambda calculus, type theory, programming logics, semantics of programming languages, applications of category theory in computer science. (b) computational complexity: boolean complexity, complexity of higher type functionals, proof length in propositional logic calculi, free variable equational calculi, bounded arithmetic. (c) computational biology: hidden Markov models, protein folding on lattice models, applications of constraint programming languages, probabilistic analysis. * Application. Interested candidates should send the following if possible by 15 May 1997: (1) short email (2) application letter stating research interests, (3) curriculum vitae (4) three letters of reference (5) pertinent reprints or preprints of work to the following address: Sekretariat, Lehr- und Forschungseinheit fuer Theoretische Informatik, Ludwig-Maximilians-Universitaet Muenchen, Oettingenstrasse 67, D-80538 Muenchen, GERMANY, Email: job@tcs.informatik.uni-muenchen.de. EXPRESSIVENESS IN CONCURRENCY Call for Papers 8-12 September 1997 Santa Margherita Ligure, Italy * Scope. This meeting aims at a general understanding of the interconnections and relations between formal systems, ranging from programming languages for concurrency to logics. More specifically, we consider methods to compare concurrent programming concepts, such as imperative programming, logic programming, functional programming, concurrent programming, object-oriented programming, dataflow, and the various combinations thereof, on the basis of their relative expressive power. We also consider associated mathematical formalisms such as process algebras, Petri nets, modal logics, rewrite systems etc. from this point of view. * Co-chairs. Catuscia Palamidessi, email: catuscia@disi.unige.it. Joachim Parrow, email: joachim@it.kth.se. * Invited speakers. Ralph Back, Jean-Jacques Levy, Eugenio Moggi, Ugo Montanari, Amir Pnueli, Vaughan Pratt, Colin Stirling. * Submissions. We seek research or expository papers on at most 15 pages (12pt font) submitted electronically (postscript format) no later than May 2, 1997. Information about the submission procedure will be available soon at the URL above. * Programme committee. Luca Aceto, Jan Bergstra, Eike Best, Frank de Boer, Ilaria Castellani, Philippe Darondeau, Rocco De Nicola, Ursula Goltz, Jan Willem Klop, Catuscia Palamidessi, Joachim Parrow, Frits Vaandrager. INTERNATIONAL WORKSHOP ON LOGIC PROGRAMMING AND MULTI-AGENTS in conjunction with ICLP'97 Leuven, Belgium July 8--12, 1997 * Topics. Interacting agents, Meta logic programmming applied to multi agent programming, Distributed reactive systems, Cognitive robotics, Applications: Integration of heterogeneous autonomous systems, Software agents, agent oriented interface programming, real-time systems, Relations between agent oriented programming and object-oriented programming, Inductive logic programming for self-organizing agents. * Programme committee. L. C. Aiello, L. DeRaedt, D. DeSchreye, P.M. Dung, K. Fischer, M. Gelfond, R. Kowalski, T. Kakas, P. Mancarella, C. Palamidessi, L. M. Pereira, D. Pearce, M. Shanahan, Y. Shoham, J. Siekmann, F. Toni, G. Wagner. * Submission. A PostScript file not larger than 15 pages when printed together with a separate PostScript file of the abstract not larger than 1 page should be sent to: paolo@di.unipi.it before May 10, 1997. SPECIAL ISSUE OF THE JOURNAL OF LOGIC AND COMPUTATION Computational & Logical Aspects of Multi-Agent Systems * Topics. Logical foundations of rational agency: logics of knowledge and belief, logics of belief, desire, and intention logics of STIT and obligation for agent specification, mutual mental states: common knowledge, joint intention, the logic of speech acts, cooperation & coordination protocols, integrated theories of ability, knowledge & action, logics of interaction; Formal methods in agent-based systems engineering: formalisms for agent specification, executing (logical) agent specifications, synthesis of agents from logical/formal specifications, verification and validation of (multi-)agent systems; Computational aspects of multi-agent systems: multi-agent decision problems and reasoning, complexity of multi-agent/social reasoning. * Editors. Fausto Giunchiglia (fausto@irst.itc.it), Nicholas R. Jennings (n.r.jennings@qmw.ac.uk), Mike Wooldridge (mjw@dib.com). * Submission. Authors who wish to submit to the special issue should send six hardcopies of their paper to the editorial address of the JLC (Jane Spurr (JLC), Department of Computing, Imperial College of Science, Technology and Medicine, Huxley Building, 180 Queen's Gate, London SW7 2BZ, UK), to arrive later than 1 August 1997. All submissions should clearly indicate that they are intended for the special issue on multi-agent systems. The first page of each submission should list the full contact details (including full name, postal address, email address, phone and fax number) of at least one author. Papers will ideally be formatted using LaTeX (12pt `article' document class, with the `plain' bibliography style), and will not exceed 25 pages in length. INTERNATIONAL COLLOQUIUM ON AUTOMATA, LANGUAGES, AND PROGRAMMING (ICALP'97) Bologna, Italy July 7-11, 1997 Call for participation POSITION ANNOUNCEMENT Associate Professor in Experimental System Development University of Aarhus, Denmark * A tenured position as associate professor in the area of modelling and validation of concurrent/distributed systems is available at the Department of Computer Science, starting 1 September 1997. Applicants must have documented scientific qualifications in the area (equivalent to a PhD plus at least 2-3 years of additional research). The position is intended to strengthen the Department=B4s existing research group in Experimental System Development. The group works with: system development with end-users, rapid prototyping, computer supported cooperative work, hyper-media, object-orientation (including languages, system development environments, analysis, design, implementation, distribution and data bases) plus modelling and analysis by means of high-level Petri nets and corresponding tools. * For further information, contact the Department Chairman, Peter D. Mosses, phone: +45 8942 3364, e-mail: pdmosses@daimi.aau.dk. Closing date: 5 May 1997. Details of how to apply will appear at URL http://www.daimi.aau.dk/ N.B. E-mail applications not accepted.