Newsletter 88
October 27, 2003

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

  LICS 2004 - Call for Workshop Proposals
  IJCAR 2004 - Call for Papers
  RTA 04 - Call for Papers
  CDB'04 - Call for Papers
  HSCC 2004 - Call for Papers
  ACSD04 - Call for Papers
  CONCUR 2004 - Preliminary Announcement
  Aspects of Incompleteness - Per Lindstrom
  Many-Dimensional Modal Logics: Theory and Applications - D. Gabbay,
    A. Kurucz, F. Wolter, M. Zakharyaschev
  An Introduction to Mathematical Logic and Type Theory: To Truth Through
    Proof (Second Edition) - Peter B. Andrews
  Reasoning About Uncertainty - Joseph Y. Halpern
  Acta Informatica Special Issue on Types in Concurrency
  PhD & postdoc vacancies - Vrije Universiteit, Amsterdam, Netherlands
  Chairs, Readers & Lecturers - University Durham, UK

  Turku, Finland
  LICS 2004: July 14-17, 2004
  LICS 2004 Workshops:  July 12-13 and July 18, 2004.
  Call for Workshop Proposals
* The Nineteenth IEEE Symposium on Logic In Computer Science (LICS 2004)
  will be held in Turku, Finland July 14-17, 2004 in conjunction with
  ICALP. The organizers have made arrangements for pre- and post-LICS
  workshops to be run in conjunction with the main conference. Possible
  dates are July 12-13 and July 18, and could be joint with ICALP (see
* Researchers and practitioners are invited to submit proposals for
  workshops on topics relating logic - broadly construed - to computer
  science or related fields.  Typically, LICS workshops feature a number
  of invited speakers and a smaller number of contributed presentations.
  LICS workshops do not produce formal proceedings.  However, in the past
  there have been special issues of journals based in part on certain LICS
* Proposals should include:
  - A short scientific summary and justification of the proposed topic.
    This should include a discussion of the particular benefits of the topic
    to the LICS community.
  - A discussion of the proposed format and agenda.
  - The proposed duration, which may vary from half a day to two days,
    and preferred dates.
  - Procedures for selecting participants and papers.
  - Expected number of participants.
  - Potential invited speakers.
  - Plans for dissemination (for example, special issues of journals).
* Proposals are due Nov. 15, 2003 and should be submitted electronically to:
  Philip Scott
  Workshops Chair, LICS 2004
* The selections will be chosen by a committee consisting of Phokion
  Kolaitis (LICS General Chair), Harald Ganzinger (LICS 2004 Program
  Committee Chair), Phil Scott (LICS Workshop Chair) and Lauri Hella (LICS
  2004 Conference chair). The results will be announced by Nov 30th, 2003.

  Cork, Ireland
  July  4-8, 2004
  Call for Papers
* The Second International Joint Conference on Automated Reasoning (IJCAR)
  is the fusion of several major conferences in Automated Reasoning:
    CADE (International Conference on Automated Deduction)
    TABLEAUX (International Conference on Automated Reasoning with
      Analytic Tableaux and Related Methods)
    FTP (International Workshop on First-Order Theorem Proving)
    FroCoS (Workshop on Frontiers of Combining Systems)
    CALCULEMUS (Symposium on the Integration of Symbolic Computation and
      Mechanized Reasoning)
  These five events will join for the first time at the IJCAR conference
  in Cork in July 2004.
* IJCAR 2004 invites submissions related to all aspects of automated
  reasoning, including foundations, implementations, and applications.
  Original research papers and descriptions of working automated deduction
  systems are solicited.
* Submitted research papers and system descriptions must be original and
  not submitted for publication elsewhere. Research papers can be up to 15
  proceedings pages long, and system descriptions can be up to 5 pages
  long. The proceedings of IJCAR 2004 will be published by Springer-Verlag
  in the LNAI/LNCS series.
* Important Dates
  January 5, 2004: Submission deadline
  March  22, 2004: Notification of acceptance
  April  14, 2004: Camera-ready copy due
  July  4-8, 2004: IJCAR 2004

  Call for Papers
* important dates:
  Jan  15 2004: Deadline electronic submission of title+short abstract
  Jan  22 2004: Deadline electronic submission of papers
  Mar  14 2004: Notification of acceptance of papers
  Apr   4 2004: Deadline for final versions of accepted papers
  Jun 3-5 2004: Conference.
* subjects:
  case studies; rule-based (functional and logic) programming;
  symbolic and algebraic computation; theorem proving;
  system synthesis and verification; proof checking.
  matching and unification; narrowing; completion techniques;
  strategies; constraint solving; explicit substitutions; tree automata.
  string, term, and graph rewriting; lambda-calculus and
  higher-order rewriting; proof nets; constrained
  rewriting/deduction; categorical and infinitary rewriting.
  compilation techniques; parallel execution; rewriting tools.
  equational logic; rewriting logic.
* program committee: Zena Ariola, Jurgen Giesl, Masahito Hasegawa,
  Helene Kirchner, Pierre Lescanne, Klaus Madlener, Narciso Mart-Oliet,
  Paul-Andre Mellies, Oege de Moor, Vincent van Oostrom (program chair),
  Frank Pfenning, Ashish Tiwari, Ralf Treinen.
* RTA'04 is part of RDP'04:

  (in conjunction with SIGMOD-PODS 2004)
  Call for Papers
  Paris, France, June 12-13, 2004
* Scope. The last few years saw a growing interest of constraint
  database theory, query evaluation, and applications in a variety
  of conferences, journals, and books. This symposium wants to
  bring together people from several diverse areas that can contribute
  to the practice and the application of constraint databases.
* Topics of interest: We especially encourage submissions
  - opening new and future directions in constraint database
  - addressing constraints over domains other than the reals;
  - contributing to a better implementation of constraint
    database systems, in particular of query evaluation;
  - addressing efficient quantifier elimination; and
  - describing applications of constraint databases.
  The following is a non-exclusive list of topics of interest:
  Applications: bioinformatics, CAD and GIS, computer security
  data mining, model checking, string databases.
  Data and knowledge representation: approximation techniques,
  constraint data extraction, constraint interpolation, incomplete
  information, spatiotemporal models, visualization
  Query evaluation: algebras, indexing, quantifier elimination
  Query languages: complexity, expressive power, new operators
* All submissions must be done electronically. See webpage for details.
* Important dates: Abstract submission: January 23, 2004,
  Submission deadline: February 2, 2004.
* Invited Speakers: Joos Heintz (Universities of Buenos Aires and of
  Cantabria), Leonid Libkin (University of Toronto), Andreas Podelski
  (Max-Planck-Institut fur Informatik).

  (Technically co-sponsored by the IEEE Control Systems Society)
  MARCH 25-27, 2004
  Call for Papers
* The Seventh International Workshop on Hybrid Systems :
  Computation and Control  (HSCC 2004), will be held at the Hilton Inn at
  Penn on the campus of the University of Pennsylvania, from March 25-27,
  2004. The annual workshop on hybrid systems attracts researchers from
  academia and industry interested in modeling, analysis, and
  implementation of dynamic and reactive systems involving both discrete
  and continuous behaviors.  The previous workshops in the HSCC series of
  were held in Berkeley, USA (1998), Nijmegen, The Netherlands (1999),
  Pittsburgh, USA (2000), Rome, Italy (2001), Palo Alto, USA (2002), and
  Prague, Czech Republic (2003).
* TOPICS. Submissions are invited in all areas pertaining to the design,
  analysis, implementation, and applications of hybrid systems. Topics of
  interest include, but are not limited to: Modeling and representations,
  Computability and complexity issues, Tools  for analysis and
  verification, Tools  for synthesis and design, Programming language
  support and implementation, Control and optimization, Hybrid models in
  biology and other sciences, Engineering applications such as automotive
  control, avionics, energy systems, transportation networks,
  manufacturing, and robotics
* INVITED SPEAKERS. Edmund M. Clarke , Department of Computer Science,
  Carnegie Mellon University; John Doyle , Control and Dynamical Systems,
  California Institute of Technology
* SPECIAL INVITED SESSION. In addition to the keynote speakers, during
  the workshop there will be one special invited session focusing on the
  interplay between biomolecular networks, systems biology, formal
  methods, and control of hybrid systems.    Invited speakers include:
  Patrick Lincoln , Director, Computer Science Laboratory, SRI; Harvey
  Rubin , School of Medicine, University of  Pennsylvania
* PAPER SUBMISSION. The conference proceedings will be published in the
  Springer Lecture Notes in Computer Science series. Selected papers will
  be invited after the meeting to submit an extended version to a special
  issue of the journal Formal Methods in System Design (Kluwer Academic
  Publishers). Submitted papers must present original, unpublished
  research that has not been submitted elsewhere. Papers should be
  prepared using Springer's LNCS style, and must be at most 15 pages
  including abstract, figures, and bibliography. Instructions for
  submitting the papers electronically will be available on the conference
  homepage in September 2003.
* IMPORTANT DATES. October 10, 2003: Submission deadline; December 1,
  2003: Notification of Acceptance/Rejection; January 15, 2004: Final
  Papers Due

  Hamilton, Canada
  June 16-18, 2004
* The International Conference on Application of Concurrency to System
  Design (ACSD) serves as a forum for disseminating theoretical results
  and advanced methods and tools for the design of complex concurrent
  systems. While there are a few success stories in the field, there is
  still a strong need to bring theory and practice closer together. The
  conference aims at cross-fertilizing both types of research.
* Submitted papers must be in IEEE CS Press 2-column format (see
  instruct.pdf at
  The cover page must contain an abstract of no more than 60 words,
  the corresponding author's physical and e-mail addresses, as well as
  phone and FAX numbers.
* Important dates:
    Deadline for submissions: 19 December, 2003
    Notification of acceptance of papers: 28 February, 2004
    Final papers due: 26 March, 2004

  Royal Society, London
  31 August - 3 September 2004
  Preliminary Announcement
* The purpose of the CONCUR conferences is to bring together
  researchers, developers and students in order to advance the theory of
  concurrency, and promote its applications. Typical topics of the
  CONCUR conferences are all areas of semantics, logics and verification
  techniques for concurrent systems.
* The proceedings will be published by Springer Verlag in the Lecture Notes
  in Computer Science series.
* Important dates:
  Submission: Friday 9 April 2004
  Notification: Monday 31 May 2004
  Final version: Tuesday 15 June 2004
  Workshops: Monday 30 August and Saturday 4 September 2004
  Main conference: Tuesday 31 August - Friday 3 September 2004
* General chair: Philippa Gardner
  Programme Committee co-chairs: Philippa Gardner, Nobuko Yoshida
  Workshops organisers: Vladimiro Sassone, Julian Rathke
  Local organiser: Iain Phillips
* Concur 2004 webpage:
* Email:

  Aspects of Incompleteness; Lecture Notes in Logic, #10
  Per Lindstrom
  Association for Symbolic Logic (Dist. By A K Peters, Ltd.)
  2003, ISBN 1-56881-173-X; Paperback; $35.00
* This thoroughly revised second edition of a classic book on the main
  ideas and results of general meta-mathematics contains new results and
  simplified proofs, as well as an up to date bibliography. In addition
  to the standard results of Godel and others on incompleteness, (non)
  finite axiomatizability, interpretability, etc.., it contains a thorough
  treatment of partial conservativity and degrees of interpretability.
  The reader should be familiar with the widely used method of
  arithmetization and with the elements of recursion theory.
* Ordering information. See the URL above.

  Many-Dimensional Modal Logics: Theory and Applications.
  Authors: D. Gabbay, A. Kurucz, F. Wolter, M. Zakharyaschev
  Studies in Logic and the Foundations of Mathematics, 148,
  Elsevier, North-Holland, 2003, 0-444-50826-0
* Information about the book can be obtained from:

  An Introduction to Mathematical Logic and Type Theory: To Truth
    Through Proof (Second Edition)
  Peter B. Andrews
  Dept. of Mathematical Sciences, CMU, Pittsburgh, PA, USA
* Book Series: Applied Logic Series: Volume 27
* This introduction to mathematical logic starts with propositional calculus
  and first-order logic. Topics covered include syntax, semantics, soundness,
  completeness, independence, normal forms, vertical paths through negation
  normal formulas, compactness, Smullyan's Unifying Principle, natural
  deduction, cut-elimination, semantic tableaux, Skolemization, Herbrand's
  Theorem, unification, duality, interpolation, and definability.
  The last three chapters of the book provide an introduction to type theory
  (higher-order logic). It is shown how various mathematical concepts can be
  formalized in this very expressive formal language. This expressive notation
  facilitates proofs of the classical incompleteness and undecidability
  theorems which are very elegant and easy to understand. The discussion of
  semantics makes clear the important distinction between standard and
  nonstandard models which is so important in understanding puzzling phenomena
  such as the incompleteness theorems and Skolem's Paradox about countable
  models of set theory.
  Some of the numerous exercises require giving formal proofs. A computer
  program called ETPS which is available from the web facilitates doing and
  checking such exercises.
* Audience: This volume will be of interest to mathematicians, computer
  scientists, and philosophers in universities, as well as to computer
  scientists in industry who wish to use higher-order logic for hardware and
  software specification and verification.
* For ordering information see:

  Reasoning About Uncertainty
  Joseph Y. Halpern
  8 x 9, 456 pp., 12 illus., cloth, ISBN 0-262-08320-5
* Uncertainty is a fundamental and unavoidable feature of daily life; in order
  to deal with uncertaintly intelligently, we need to be able to represent it
  and reason about it. In this book Joseph Halpern examines formal ways of
  representing uncertainty and considers various logics for reasoning about it.
  While the ideas presented are formalized in terms of definitions and
  theorems, the emphasis is on the philosophy of representing and reasoning
  about uncertainty; the material is accessible and relevant to researchers and
  students in many fields, including computer science, artificial intelligence,
  economics (particularly game theory), mathematics, philosophy, and
* Halpern begins by surveying possible formal systems for representing
  uncertainty, including probability measures, possibility measures, and
  plausibility measures. He considers the updating of beliefs based on changing
  information and the relation to Bayes' theorem; this leads to a discussion of
  qualitative, quantitative, and plausibilistic Bayesian networks. He considers
  not only the uncertainty of a single agent but also uncertainty in a
  multi-agent framework. Halpern then considers the formal logical systems
  for reasoning about uncertainty. He discusses knowledge and belief; default
  reasoning, and the semantics of default; reasoning about counterfactuals,
  and combining probability and counterfactuals; belief revision; first-order
  modal logic; and statistics and beliefs. He includes a series of exercises
  at the end of each chapter.
* Joseph Y. Halpern is Professor of Computer Science at Cornell University.
  He is the editor-in-chief of the Journal of the ACM and coauthor of
  Reasoning About Knowledge (MIT Press, 1995).
* "Halpern presents a masterful, complete and unified account of the many
  ways in which the connections between logic, probability theory and
  commonsensical linguistic terms can be formalized. Terms such as 'true,'
  'certain,' 'plausible,' 'possible,' 'believed,' 'known,' 'default,'
  'relevant,' 'independent,' and 'preferred are given rigorous semantical
  and syntactical analyses, and their interrelationships explicated and
  exemplified. An authoritative panoramic reference for philosophers,
  cognitive scientists and artificial intelligence researchers."
  - Judea Pearl, Computer Science Department, University of California, Los
* For more information please visit:

  Proposed by IFIP Working Group 2.2 on Formal Description of
    Programming Concepts (
  Guest Editors: R. De Nicola, Univ. Firenze and D. Sangiorgi, Univ. Bologna.
  Both research and tutorial/surveys papers are welcome.
* Dates. Authors are invited to send a pdf or a
  ps file with their paper to AND by 15 January 2004.
  Authors are also requested to email us a title and a short abstract
  in plain text as early as possible (ideally before end October).
* Meeting. Apart for publication on Acta Informatica, some of the
  submitted papers will be also considered for presentation at the
  meeting of the IFIP Working group 2.2 that will take place in
  Bertinoro (Italy) 12-17 September 2004.
* Details:

  Agent Systems Research Group
  Department of Artificial Intelligence
  Vrije Universiteit, Amsterdam
* The Department of Artificial Intelligence within the Faculty of
  Sciences has a number of postdoc and PhD student vacancies for four
  years in Multi-Agent Organisation Dynamics, in particular in the
  Agent Systems Research Group, headed by dr. C.M. Jonker.
* For further information contact Dr. C.M. Jonker,
  tel. 020-44 47743/47700, e-mail,
  or prof. dr. J. Treur, tel. 020-44 47763/47700, e-mail

  Department of Computer Science
  Chairs, Readers and Lecturers
* The Department of Computer Science at the University of Durham is to
  make up to 10 appointments at the level of Chair, Reader and Lecturer.
  These are non-fixed-term positions and are tenable from 1st January 2004
  or from a mutually acceptable date thereafter.
* Applicants should have research interests in software engineering,
  distributed computing or theoretical computer science (under a broad
  interpretation), although strong candidates with research interests in
  other areas of Computer Science are welcome to apply.  Candidates with
  research interests relating to e-Science and inter-disciplinary research
  are particularly encouraged to apply.  Indeed, one Lectureship will be
  reserved exclusively for such a candidate.
* The Department's web-pages can be found at:
  and further details as regards the positions at:
* Potential candidates are strongly encouraged to contact Professor Iain
  Stewart (Head of Department) for informal discussions:
  e-mail:, tel: +44 (0)191 334 1720.
* The closing date for applications is 1st November 2003

Back to the LICS web page.