LICS Newsletter 43

Newsletter 43

April 23, 1997

[Past issues of the newsletter are available at 

  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: 

  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
* 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 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 (, Tom Leighton
  (, Christos Papadimitriou
  (, Moshe Vardi (, and
  Peter Wegner ( 

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:

  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

  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. 

  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. 

  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

  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,
  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.

  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
* Application form: 

  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. 

  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
* 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. 

  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: 

  Call for participation
  July 1 - 4, 1997 
  Warsaw, Poland

  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 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. 

  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
* 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:

  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: 
  Joachim Parrow, email: 
* 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

  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: before May 10,

  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
* Editors. Fausto Giunchiglia (, Nicholas
  R. Jennings (, Mike Wooldridge
* 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.  

  Bologna, Italy
  July 7-11, 1997  
  Call for participation

  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:
  Closing date: 5 May 1997.  Details of how to apply will appear at
  URL N.B. E-mail applications not accepted.