Newsletter 85
April 23, 2003

* Past issues of the newsletter are available at
* Instructions for submitting an announcement to the newsletter
  can be found at

  LICS 2003 - Call for Participation
  Typical Case Complexity and Phase Transitions - Announcement and Call
    for Papers
  Foundations of Global Computing - Call for Papers
  MERLIN 2003 - Call for Papers
  Kalmar Workshop on Logic and Computer Science - Call for Papers
  Algebraic and Topological Methods in Non-classical Logics - Call
    for Papers
  Workshop on Feature Interactions in Telecommunications and Software
    Systems - Call for Participation
  ACSD 2003 - Call for Participation
  EEF Global Computing Summer School
  Computability and Models Perspectives East and West, edited by
    S. Barry Cooper and Sergei S. Goncharov
  Abstract State Machines. A Method for High-Level System Design
    and Analysis, by Egon Boerger and Robert Staerk
  Aspects of Complexity, Minicourses in Algorithmics, Complexity,
    and Computational Algebra, edited by Rod Downey and
    Denis Hirschfeldt - Price Reduction

  June  22 - 25, 2003, Ottawa, Canada
  Call for Participation
* The LICS Symposium is an annual international forum on theoretical and
  practical topics in computer science that relate to logic in a broad
  sense. The conference is intended to emphasize the relevance of logic
  to computer science.
* The program of LICS 2003 features 4 invited talks, 2 invited tutorials,
  34 contributed papers, and 14 short presentations. As in previous years,
  there will be a number of workshops affiliated with the conference.
  The full program is available on the conference website.
* Pre-LICS Summer School: The Fields Institute Summer School on Logic
  and Foundations of Computation will be held at the University of
  Ottawa, June 2-20, 2003. For information, see the summer school
  web site at:
* Registration: LICS 2003 registration and conference information is
  now available on the LICS 2003 website or directly at:
* The deadline for early registration is Tuesday, May 20, 2003.

  Affiliated with LICS 2003
  June 21, 2003, Ottawa, Canada
  Announcement and Call for Papers
* Typical-case complexity refers to algorithmic complexity  that holds
  with high probability  for a class of random instances of a problem.
  Usually, the class of instances considered is parameterized by a
  "control parameter." It has been observed that for many computationally
  interesting problems, their typical-case complexity undergoes an abrupt
  change (phase transition) about a critical value of the control
  parameter. At the same critical region, other phenomena of combinatorial
  interest are often observed. Papers  reporting  on experimental and
  theoretical research in this area are solicited, especially if they are
  the outcome of cross-fertilization between computer simulation results
  and mathematical advances in discrete mathematics, probability theory or
  theoretical computer science. Of particular interest are threshold
  phenomena in which logic comes into play and connections to Proof
  Complexity, Satisfiability, and Statistical Physics.
* Program committee: J. Chayes; N. Creignou; L. Kirousis;
  E. Kranakis; D. Krizanc.
* Invited speakers (confirmed): Jennifer Chayes (Seattle);
  Nadia Creignou (Marseille); Paul Beame (Seattle); John Franco (Cincinnati)
* Submit short abstracts of at most five pages in ps or pdf either to or
* Submission deadline: April  28, 2003

  co-located with ICALP 2003, 28-29 June 2003, Eindhoven, The Netherlands
  Call for Papers
* Foundations of Global Computing focuses on foundational aspects of
  global computing, and invites submissions of original scientific work
* The workshop proceedings will be published in the ENTCS series and a
  selection of papers will appear in a special issue of a leading
  Computer Science journal. It will be held as a ICALP 2003 satellite
  event under the auspices of the EATCS.
* Invited Speakers: Cedric Fournet (Microsoft Research); Robert Harper (CMU);
  Martin Hofmann (LMU Munich); Li Gong (SUN Microsystems)
* Authors are invited to submit an extended abstract of their papers,
  presenting original contributions to the workshop themes. Submissions
  should be in English and not exceed 15 standard pages. They should be
  sent as PS or PDF files to and be accompanied by
  a text-only message containing: title, abstract and keywords, the
  authors' full names, and address and e-mail for correspondence.
  Simultaneous submission to other meetings with published proceedings
  is not allowed.
* Submission deadline: 27 Apr 2003

  Affiliated with  PLI 2003
  Uppsala, Sweden, August 26, 2003
  Call for papers
* Theme.  The automation of the metatheory of programming languages,
  particularly work which involves variable binding and fresh name
  generation. Theoretical and practical problems of encoding variable
  binding, especially the representation of, and reasoning about,
  datatypes defined from binding signatures.
* Invited speaker: Simon Peyton Jones
* Papers should be submitted electronically as a PostScript or PDF file
  to the email address
* Deadline for paper submission:  June 16, 2003
* Program Committee: Simon Ambler (University of Leicester), Furio
  Honsell (University of Udine), Marino Miculan (University of Udine,
  Italy), Dale Miller (INRIA/Futurs, France), Ugo Montanari (University of
  Pisa, Italy), Tobias Nipkow (Technische Universitat Muenchen Germany),
  Andrew M. Pitts (University of Cambridge, UK),  Carsten Schuermann (Yale
  University, USA).

  Call for Papers
  Szeged, Hungary, October 1 - 2, 2003
* Laszlo Kalmar (1905 - 1976) was a pioneer in mathematical
  logic and computer science. The objective of the workshop is to
  commemorate his work, and to present recent research results in
  the broad area of logic and computer science.
* Workshop Chair: F. Gecseg (Szeged)
* Workshop Co-Chairs: J. Csirik (Szeged), Gy. Turan (Szeged, Chicago)
* Invited speakers include: E. Graedel (Aachen), A. Hajnal (New
  Brunswick, Budapest), J. Lloyd (Canberra), G. Proszeky (Budapest)
* Co-located Event: 13th International Conference on Inductive Logic
  Programming (ILP 2003), September 29 - October 1, 2003.
* Publication:  the accepted papers will be available in a booklet of
  notes at the workshop. A special journal issue is under consideration.
* Important dates:
    Paper submission: June 30, 2003
    Notification of acceptance: August 15, 2003
    Final version submission: September 15, 2003
* Submission information: Submitted papers should be extended abstracts
  up to 10 pages. The papers are to be submitted electronically in PDF
  or PostScript form. For additional details, please see the workshop
  home page.
* Program Committee: H. Andreka (Budapest), A. Atserias (Barcelona),
  S. Bloom (Hoboken), J. Csirik (Szeged), J. Demetrovics (Budapest),
  B. Domolki (Budapest), M. Grohe (Edinburgh), J. Makowsky (Haifa),
  A. Salomaa (Turku), Gy. Turan (chair, Szeged, Chicago)
* Organizing Committee: D. Csendes, T. Koles, B. Szorenyi

  Tbilisi, Georgia, 7 - 11 July 2003
  Final Call for Papers
* The aim of this conference is to present some recent advances in the
  use of algebraic, order-theoretic, and topological methods in
  non-classical logics. We also hope to bring together researchers
  in the fields of non-classical logics, lattice theory, universal algebra,
  category theory, and general topology in order to foster collaboration
  and to get new ideas for further research.
* Conference Topics: lattices with operators, topological semantics of
  modal logic, topological and topos semantics of intuitionistic logic,
  ordered topological spaces.
* Invited Speakers: Johan van Benthem, University of Amsterdam;
  Leo Esakia, Georgian Academy of Sciences; Mai Gehrke, New Mexico
  State University; John Harding, New Mexico State University;
  Ramon Jansana, University of Barcelona; Daniele Mundici, Milan
  University; Yde Venema, University of Amsterdam; Michael
  Zakharyaschev, King's College; Marek Zawadowski, University of Warsaw.
* Call for papers: If you wish to speak at the conference, please send
  by email a title and abstract of your talk to Guram Bezhanishvili
  ( The deadline for submissions is 1 May. We will
  let you know by 15  May if you will be invited to speak at the
  conference. The deadline to register for the conference is 1 June.
* For further information, contact Guram Bezhanishvili
  ( or Pat Morandi (

  10th June to 13th June, 2003, Ottawa, Canada.
  Call for Participation
* The Feature Interaction Workshop is the primary international forum for
  discussion and reporting on research in the feature interaction problem
  in telecommunications and software systems. The workshop aims to bring
  together representatives of the telecommunications industry, the
  software industry, and the research community working on various aspects
  of feature interactions in order to discuss possible solutions and their
  practical applications, as well as setting directions for further
  research. Active debates will be encouraged.
* Proposals for poster presentations and tool demonstrations, including
  title, authors, and short description (400 words maximum) should be sent
  to before May 17th.
* Registration forms are available on the Workshop's Web site. Early
  birds' rates are valid until May 9th. Special rates for students are
  also available, but places are limited. It is possible to register to
  the tutorials, to the Workshop, or to both. Register now!

  18-20 June, 2003 Guimaraes, Portugal
  Call for Participation
* The registration form, the list of accepted papers, and
  other information are available from

  Edinburgh, Scotland, 7th to 11th July 2003
* Description.  This school provides researchers with insights into
  the problems of the design and construction of global computing
  systems.  Global computation is an active field of research which
  includes distributed and mobile computation and addresses the
  foundational problems in the area such as security, access control,
  resource control, discovery, architecture and decentralised
  organisation.  The fundamental tools used to analyse and build such
  systems are type systems, process algebras, modelling languages and
  state-of-the-art programming languages and environments.
* Speakers. Ian Clarke (provisional); Andrew Gordon; Martin Hofmann;
  Rocco de Nicola; Davide Sangiorgi; and Martin Wirsing.
* Applications.  A  number of scholarships are available.  Whether or
  not they are applying for funding, anyone who wishes to attend must
  apply via the form on the Web page by Friday 16th May 2003.

  Computability and Models Perspectives East and West
  edited by S. Barry Cooper and Sergei S. Goncharov
  Kluwer Academic/Plenum Publishers, Hardbound, ISBN 0-306-47400-X
  January 2003,  388 pp.
  EUR 142.00 /  USD 135.00 /  GBP 90.50
  Book Series: University Series in Mathematics
* There are few notions as fundamental to contemporary science as those of
  computability and modelling. 'Computability and Models' attempts to make
  some of the exciting and important new research developments in this area
  accessible to a wider readership. Written by international leaders drawn
  from major research centres both East and West, this book is an essential
  addition to scientific libraries serving both specialist and the
  interested non-specialist reader.
* Order at:

  Abstract State Machines. A Method for High-Level System Design and Analysis
  Egon Boerger and Robert Staerk
  Springer Verlag, 2003, ISBN 3-540-00702-4
* The systems engineering method proposed in this book, which is based
  on Abstract State Machines (ASMs), guides the development of software
  and embedded hardware-software systems seamlessly from requirements
  capture to actual implementation and documentation. Within a single
  conceptual framework it covers design, verification by reasoning
  techniques, and validation by simulation and testing. ASMs improve
  current industrial practice by using accurate high-level modeling and
  by linking the descriptions at the successive stages of system
  development in an organic and efficiently maintainable chain of
  rigorous and coherent system models at stepwise-refined abstraction
* The book combines the features of a textbook and a
  handbook. Researchers will find here the most comprehensive
  description of ASMs available today and professionals will use it as a
  "modeling handbook for the working software engineer." As a textbook
  it supports self-study or it can form the basis of a lecture
  course. The book is complemented by a CD containing the whole book
  text, additional course material, solutions to exercises, and
  additional examples.
* Ordering from or
  or send an email to

  Aspects of Complexity
  Minicourses in Algorithmics, Complexity, and Computational Algebra,
  MathematicsWorkshop, Kaikoura, New Zealand, January 7-15, 2000
  Editors: Rod Downey, Denis Hirschfeldt
  de Gruyter Series in Logic and Its Applications, Volume 4
  2001. vi, 172 pages. ISBN 3-11-016810-3
  USA, Canada, Mexico: Cloth US$ 59.95
  All other countries: EUR 58.00 [D] / sFr 93,-
* The contributions in this volume are a result of the sixth
  summer workshop of the New Zealand
  Mathematical Sciences Research Institute. The title of this
  workshop was Computability, Complexity,
  and Computational Algebra.
* The lecture notes presented here are based on minicourses
  from leading experts on various
  aspects of complexity. The minicourses are from areas
  including basic complexity, Kolmogorov
  complexity, enumeration complexity, complexity in algebra,
  real complexity and the BlumShub
  Smale model, parametric complexity, and aspects of the
* The material and level of presentation are aimed at
  beginning graduate students, and the
  resulting text will be a valuable resource for the working
  mathematician and computer scientist.
* Ordering Information: see URL above.

Back to the LICS web page.