LICS Newsletter 44

Newsletter 44

June 10, 1997

[Past issues of the newsletter are available at 

  San Diego, California, January 19-21, 1998
* Topics. The 25th symposium on Principles of Programming Languages
  (POPL98) will address fundamental principles and important
  innovations and accomplishments in the design, definition, analysis,
  and implementation of programming languages, programming systems,
  and programming interfaces. Both practical and theoretical papers on
  principles and innovations are welcome, including both frameworks
  for them and reports on experiences with their use.  Papers on a
  diversity of topics are welcomed, particularly ones that point out
  new directions. POPL98 is not limited to topics discussed in
  previous symposia or to formal approaches. In particular, papers
  integrating new principles into mainstream programming languages or
  widely used systems are encouraged. Authors concerned about the
  appropriateness of a topic may communicate by electronic mail with
  the program chair prior to submission.
* Submission. Submissions consist of a 100-200 word ASCII abstract and
  a 5000 words summary. Submissions must be either electronic
  (encouraged) or postal (discouraged). Electronic submissions must be
  received by 6:00 AM Pacific Daylight Time, Saturday, July 19,
  1997. Submissions may be sent as a single e-mail message to (MIME attachments are allowed). The message should
  contain both the ASCII abstract and the Postscript
  summary. Electronic summaries should be in Postscript form, which
  must be interpretable by Ghostscript. The Postscript must use
  standard fonts, or include the necessary fonts, and must be prepared
  for USLetter (8.5"x11") or A4 page sizes. Authors who cannot meet
  these requirements should submit hardcopy by post instead. Postal
  submissions must be sent to the program chair by airmail and
  postmarked (not metered) on or before Friday, July 11, 1997; 15
  copies (printed double-sided if possible) must be provided.
* Program Chair. Luca Cardelli (Digital Equipment Corporation).
* General Chair. David B. MacQueen (Bell Laboratories, Lucent
* Program Committee.  Luca Cardelli, Jeanne Ferrante, Andrew
  D. Gordon, Carl Gunter, Nevin Heintze, Neil Jones, Todd Knoblock,
  Xavier Leroy, Martin Odersky, Atsushi Ohori, Davide Sangiorgi, Scott
  Smith, Joe Wells, Katherine Yelick.

  Proposal for a new field
  Letter from Jurek Tyszkiewicz
* Dear Colleagues,
  AMS is going to introduce some changes into the 1991 Mathematics
  Subject Classification and asks for input from all interested
  mathematicians. Their announcement is appended at the end of this
  message and can be found here.
  We, the finite-model-theorists, had a discussion concerning the
  location of their field in the new classification scheme, and the
  outcome is that the majority of us is in favor of the following:
* There should be a new field "Logic in Computer Science" within the
  area 68 of Computer Science, say 68X, and it should include a
  subfield 68Xnn devoted to the finite model theory.
* This project can be successful only if other communities which feel
  to belong to the "Logic in Computer Science" field participate in it
  with us, proposing their own subfields, and then start lobbying with
  us to get our proposal accepted.  Therefore we ask and invite you to
  discuss this topic in your own communities as soon as possible, and
  to communicate the outcome to us, by sending email to Jurek
  Tyszkiewicz (see the address below), so that we can make a common
  proposal and submit it to the AMS.  
  Best regards, Jurek Tyszkiewicz (

  July 23-25, 1997, Rutgers University, New Brunswick, NJ
  Call for Participation
* You are invited to participate in a DIMACS Workshop on "Logic and
  Algorithms: One Year Later", which will be held at Rutgers
  University, on July 23-25, 1997. The goal of the workshop is to
  follow up on the 1995-1996 Special Year on Logic and Algorithms
  (SYLA) that 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 (CAV),
  finite-model theory (FMT), and proof complexity (PC).  The workshop
  will cover the three major topics of the Special Year. The program
  of the workshop will consist of 1-hour-long survey talks as well as
  shorter 1/2-hour-long talks. The speakers will 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 will focus on bringing the three topics together, in an
  attempt to provide participants with a broader view of the field.
* Organizers. Eric Allender, Robert Kurshan, Moshe Vardi.
* Invited speakers. CAV: N. Immerman, O. Kupferman, R. Kurshan. 
  FMT: M. Grohe, L. Libkin, M. Otto, E. Rosen. 
  PC: S. Buss, P. Pudlak, T. Pitassi, A. Razborov.
* Complete program and registration info. See the URL above. 

  October 27-28, 1997, Schloss Hagenberg, near Linz (Austria)
  Research Institute for Symbolic Computation (RISC)
* The FTP workshop is intended to focus effort on First-Order Theorem
  Proving as a core theme of Automated Deduction, and to provide a
  forum for presentation of very recent work and discussion of
  research in progress.  The workshop welcomes original contributions
  on theorem proving in first-order logics, including resolution and
  tableau methods; equational reasoning and term-rewriting systems;
  constraint-based reasoning; unification algorithms for first-order
  theories; specialized decision procedures; propositional logic;
  abstraction; first-order constraints; complexity of theorem proving
  procedures; and applications of first-order theorem provers to
  problems in artificial intelligence, verification, mathematics, as
  well as other areas. Papers that bridge the areas of theorem proving
  and constraints (e.g., in the areas of equational reasoning, term
  rewriting systems, and satisfiability problems) are especially
* Invited talk ``The Theorema Project: An Overview'' will be given by 
  Bruno Buchberger of the Research Institute for Symbolic
* Program Committee. Maria Paola Bonacina and Ulrich Furbach
  (co-chairs), Wolfgang Bibel, Ryuzo Hasegawa, Alexander Leitsch,
  Reinhold Letz, Christopher Lynch, Neil Murray, David Plaisted,
  Michael Rusinowitch. 
* Submission. Extended abstract of no more than 5 pages 11pt should be
  sent by electronic mail, as uuencoded gzipped Postscript files, to by August 27, 1997. 

  ACM Computing Surveys
  1998 Symposium on Partial Evaluation
* The Symposium on Partial Evaluation is a collection of short
  articles characterizing the state of the art, stating challenging
  problems, and outlining promising directions for future work.
  Topics of interest include all areas of partial evaluation and
  semantics-based program manipulation, automatic program
  transformation, and their applications. Contributions should be
  expository in nature and should explain relevant trends in partial
  evaluation in both general and technical terms, with a maximum of
  clarity and conciseness.  Statements of open problems that have a
  potential impact on the future development are particularly welcome.
  Every effort should be made to make contributions self-contained and
  understandable to a general audience.
* Guest editors: Olivier Danvy, Robert Glueck, Peter Thiemann
* Submission.   Submissions should be no longer than 1000 words. They
  should adhere to the instructions for authors stated in Please send your submission
  as a postscript file by electronic mail to, by
  September 30, 1997.  Each submission should be accompanied by a
  plain ASCII message giving the title, authors, and the postal and
  electronic address of the corresponding author.

* After ten years of Gurevich's Abstract State Machines, the Special
  ASM issue 3.4 (1997) of J.UCS is ready.  The contributing authors
  are Ahrendt, Blass, Boerger, Dexter, Gurevich, Kwon, Schellhorn,
  Soparkar, Spielmann, Stroetmann, Wallace. 

  Call for Participation
  Aug 19-22, 1997, Bell Labs, Murray Hill, NJ, USA
* Topics.  The conference will be a venue for presentations on the
  following topics, among others: advances in interactive theorem
  proving, proof automation and decision procedures, applications of
  mechanized theorem proving, comparison between different theorem
  proving approaches, exploiting external tools within theorem provers
  and incorporating theorem provers into larger systems.
* Invited Speakers.  Robert Constable, Deepak Kapur, Doron Peled.
* Conference Chair.  Elsa Gunter.
* Registration.  Deadline for early registration and hotel reservation
  is Jun 20, 1997.  Registration and further information at the URL
  above or by email to

  Models and Paradigms of Concurrency
  15-19 September 1997, CISM, Udine, Italy
* Scope.  The IC-EATCS (European Association of Theoretical Computer
  Science) Advanced Schools focus on specific subjects of Theoretical
  Computer Science, and address an international public formed both by
  PhD students and by researchers who wish to deepen their knowledge
  of the field.  Besides the didactical purpose, these events aim at
  the dissemination of advanced scientific knowledge and at the
  promotion of international contacts and exchange of ideas among
  scientists. They intend to be an occasion, especially for the
  youngest participants, to meet other people interested in their
  research with whom to discuss ideas and to compare approaches and
  results.  The IC-EATCS 1997 Advanced School will focus on "Models
  and Paradigms for Concurrency". The aim is to provide a overview of
  some of the hot topics in the field of Concurrency Theory,
  particularly concerning computational models and linguistic
* Organizers.  Furio Honsell, Catuscia Palamidessi, Paolo Serafini.
* Program.  There will be 3 main courses of 10 hours each. Every
  course will be parted in 5 lectures of 2 hours, one per day.
  Additionally, there will be invited talks, one per day, of 1 hour
  and half each. Main courses will be given by Samson Abramsky,
  Prakash Panangaden, Davide Sangiorgi.  Invited talks will be given
  by Pierpaolo Degano, Moreno Falaschi, Roberto Gorrieri, Furio
  Honsell and Simone Martini.
* Application.  To apply, participants should fill the enclosed
  Application Form and return it, either by hard or electronic mail,
  to: IC-EATCS 1997 Advanced School Secretariat, CISM, Palazzo del
  Torso, Piazza Garibaldi 18, 33100 Udine, Italy. Email:, before 30 June 1997.

  June 15 - 17, 1998, Marstrand, Sweden
* Topics. High quality papers on original research are solicited,
  typically in one of the following areas: formal specification of
  sequential and concurrent programs; constructing implementations to
  meet specifications; in particular, program transformation; program
  analysis; program verification; convincing case studies.  While this
  list is not exclusive it is intended to show the focus of the
* Submission.  Full papers should be submitted in Postscript format by
  e-mail to reach Johan Jeuring by December 15, 1997. The details of
  the submission procedure can be found at 
* Program committee.  Ralph-Johan Back, Roland Backhouse, Richard
  Bird, Eerke Boiten, Dave Carrington, Robin Cockett, David Gries,
  Lindsay Groves, Wim Hesselink, Zhenjiang Hu, Barry Jay, Johan
  Jeuring, Dick Kieburtz, Christian Lengauer, Lambert Meertens, Sigurd
  Meldal Bernhard M=F6ller, Chris Okasaki, Jose Oliveira, Ross
  Paterson, Mary Sheeran, Doug Smith.

  Set Theory: On the Structure of the Real Line
  Tomek Bartoszynski, Haim Judah
  A K Peters, 1995
  ISBN 1-56881-044-X Hardcover, 560 pp, $78.00
* This book reflects the current state of research in a major area of
  descriptive set theory.  Its focus is measure and category in set
  theory, most notably on results dealing with asymmetry.  Indeed, the
  authors delve into study of a deep asymmetry between the concept of
  Lebesgue measurability and the Baire property and obtain surprising
  findings on the structure of the real line.  The book consists of
  three interwoven parts: results that can be proven in
  Zermelo-Fraenkel Set Theory (and its extensions), independence
  results, and the 'tools' used to accomplish both.  With its
  attention to basic concepts and broad range of recent findings, this
  book is a valuable reference tool.  The clear and concise exposition
  also makes it well suited as a textbook in set theory for the
  intermediate to advanced graduate student.

  The Most Complex Machine: A Survey of Computers and Computing
  David J. Eck
  A K Peters, 1995
  ISBN 1-56881-054-7, Hardcover, 464 pp, $54.00
* This unique introduction to computer science takes the unusual tack
  of presenting the fundamental ideas and principles upon which the
  field is built rather than trying to teach the reader how to program
  or become an expert computer user.  The book on one level examines
  that most complex machine, the computer, and provides an overview
  appropriate for all students regardless of whether they pursue their
  studies in computer science.  But it is the idea of complexity
  itself, and the methods for creating and understanding that
  complexity, that are the book's real subject.  Eck masterfully uses
  his detailed examination of the computer and its applications as a
  tool for elucidating more abstract ideas.  The book contains an
  annotated bibliography and each chapter ends with a set of
  thought-provoking questions that are meant to be >read and pondered<
  (answers included).  The book will please computer scientists
  because it conveys concepts rather than the usual list of >recipes<,
  and it will be helpful to students because it serves as a useful
  introduction to tools they will use for the rest of their
  professional and personal lives.

  The Incompleteness Phenomenon
  Martin Goldstern, Haim Judah
  A K Peters, 1995 
  ISBN 1-56881-029-6, Hardcover, 264 pp, $54.00
* From the time of Aristotle, in our quest for precision and order, we
  have often relied on mathematics to supply us with >the truth<.  But
  although the mathematical sciences boast of being the epitome of
  exactness, can they always supply us with the right answer?  What is
  Logical Dilemmas: The Life and Work of Kurt Goedel
  John Dawson
  A K Peters, 1997
  ISBN 1-56881-025-3, Hardcover, 376 pp, $49.95
* This definitive biography of the logician and philosopher Kurt
  Goedel is the first in-depth account to integrate details of his
  personal life with his work and is based on the author's intensive
  study of Goedel's papers and surviving correspondence.  Goedel
  (1906-1978) is considered to be the preeminent logic researcher of
  the 20th century.  His noted works on the completeness of
  first-order logic, the incompleteness of formal number theory, and
  the relative consistency of the Axiom of Choice and the Continuum
  Hypothesis established bounds on the efficacy of formal methods in
  investigating foundational questions.  He is also noted for his
  unique and distinctive writings on the philosophy behind
  mathematics, and his lesser-known results in cosmology raised
  problematic issues in the philosophy of time.  Dawson, a logician
  and historian of science, examines the life of this driven man whose
  work on the foundation of mathematics has fundamentally changed our
  thoughts on these subjects and has stimulated much of the research
  conducted in this century.

  Kreiseliana: About and Around Georg Kreisel
  Piergiorgio Odifreddi, editor
  A K Peters, 1997
  ISBN 1-56881-061-X, Hardcover, 512 pp, $60.00
* This multifaceted collection of essays, reminiscences, and
  professional papers combine to create a exceptional tribute to the
  unusual, enigmatic, and ultimately fascinating personality of Georg
  Kreisel.  An eminently influential logician and mathematical
  philosopher, Kreisel is revealed as much more in this entertaining
  combination of viewpoints from famous contributors like Verena
  Huber-Dyson, Sol Feferman, and Francis Crick.  While mathematics
  fans will delight in this look at Kreisel, this book aims to
  communicate to a wider circle his unique personal and intellectual

  Complexity, Logic and Recursion Theory
  Edited By Andrea Sorbi
  Marcel Dekker, Inc
  Lecture Notes in Pure and Applied Mathematics Series/187
  February, 1997 $150.00,  ISBN: 0-8247-0026-0
* Integrating several classical approaches to computability, this
  volume offers detailed coverage of recent research at the interface
  of logic, computability theory and theoretical computer
  science. Written by distinguished experts from seven countries, the
  volume is an excellent resource for complexity and recursion
  theorists, theoretical computer scientists and logicians. The volume
  is a collection of survey/research papers representing the research
  undertaken within the project of the Human Capital and Mobility
  European network ``Complexity, Logic and Recursion Theory''.

  Hulme Hall, Oxford Place, Victoria Park, Manchester, England
  July 14 - 18, 1997
  Call for participation
* See the above URL for program and conference information.

  August 11-22
* The summer school primarily aims at Nordic Ph.D. students, but is
  open to all interested in mathematical logic.
* Registration deadline. June 23, 1997. 
* Program.  Klaus Grue: Basic logic.  Dag Normann: Recursion theory.
  Herman Jervell: Proof theory.  Morten Heine Sorensen: Untyped lambda
  calculus.  Thierry Coquand: Typed lambda calculus.  Neil Jones:
  Complexity.  Erik Palmgren: Effective enumeration.  Erik Palmgren:
  Domain theory.  Klaus Grue: Map theory.  Anders Kock: Category