Newsletter 33

April 9, 1996

* Olympics!  The 1996 Olympic Games take place from July 19 to Aug 3rd
  in Atlanta.  This period is also peak tourist season.  We have some
  anecdotal evidence that it is difficult already to get flights to New
  York and other places for specific days during that time.
* Further Information.  For the most up-to-date information on FLoC, see
  the web page.  Full travel information will soon be available, but for
  now the web page has a link to information on travelling to DIMACS.
  DIMACS is on the Busch campus of Rutgers.  FLoC will be held on the
  College Avenue campus of Rutgers which is just a few miles away.

  November 3-4, 1996, Boston, Massachusetts. (Precedes KR'96.)  
* Topics.  Speeding up inference using relevance reasoning.  Relevance
  in probabilistic reasoning.  Relevance in explanation.  Relationships
  between relevance and belief revision and updates.  Relevance
  reasoning as a basis for abstraction and reformulation.  Using
  relevance of information to enable drawing appropriate conclusions.
  Applications of relevance reasoning.  Reasoning about relevance of
  information, and foundations of relevance reasoning.
* Submissions.  Extended abstract of at most 5000 words.  Persons
  wishing to attend the workshop and not to present papers should submit
  a 1-2 page research summary that includes a list of relevant
  publications.  Submit PostScript versions of their paper by email to
  either Russ Greiner ( or Alon Levy
  (  Deadline: received by July 8, 1996.
* Program Chairs.  Russ Greiner,  Alon Levy.
* Program Committee.  Adnan Darwiche, Jim Delgrande, Daphne Koller,
  Gerhard Lakemeyer, Alberto Mendelzon, Devika Subramanian.

  September 3-6, 1996, Asilomar, Pacific Grove, California  
* Topics.  Foundations, models, and extensions of rewriting logic (RWL);
  uses of rewriting logic as a logical framework; applications of RWL to
  the specification of languages and systems; applications of RWL to
  object-oriented specification and programming; applications of RWL to
  concurrency and parallel programming; programming languages based on
  rewriting logic.
* Submissions.  2,000 word abstract submitted electronically (in
  postcript format) to the program chair (
  Submission of abstracts due to program chair May 1, 1996.
* Program Committee.  Fiorella De Cindio, Kokichi Futatsugi, Claude
  Kirchner, Christian Lengauer, Narciso Marti-Oliet, Jose Meseguer, Ugo
  Montanari, Carolyn Talcott.
* Invited Speakers.  Narciso Marti-Oliet, Ugo Montanari, Martin Wirsing.

  January 8-10, 1997, Delphi, Greece  
[First call for papers is in Newsletter 31.]

  May 24-26, 1996, Philadelphia, Pennsylvania, USA    
[Call for papers in Newsletter 28.]
* Programs.  Available from the web pages.

  August 12-23, 1996, Prague, Czech Republic  
* Summary.  The main focus will be the intersection of the areas of
  between logic, linguistics, and computation, particularly where it
  concerns the modelling of human linguistic and cognitive abilities. As
  such, the programme includes courses, workshops and symposia covering
  a variety of topics within six areas of interest: Logic, Language,
  Computation, Logic & Computation, Computation & Language, and Language
  & Logic.  Courses are cast at both introductory and advanced
  levels. Introductory courses are designed to familiarize students with
  new fields and do not presuppose any background knowledge, while
  advanced courses are designed to allow participants to acquire more
  specialized expertise in areas they are already familiar with.
* Further Information.  ESSLLI'96, UFAL MFF UK, Malostranske nam. 25,
  118 00 Praha 1, Czech Republic.  Telephone: ++42-2-245.10.286 (ask our
  operator for "linguistics").  Fax: ++42-2-53.27.42.  EMail:  

  July 1-5, 1996, Ludwig-Maximilians-Universit"at, Munich,  Germany
* Program/Further Information.  Available from the above URL's, and from
* Deadline.  Early Registration deadline is May 15.


  April 22-26 1996, Linko"ping, Sweden  
[Call for papers is in Newsletter 28.]
* Program.  See web page.
* Local Arrangements.  CAAP/CC/ESOP'96, attn. Peter Fritzson,
  Department of Computer and Information Science, Linko"ping University,
  S-581 83 Linko"ping, Sweden.  Telephone: +46 13 282297.  Telefax: +46
  13 282666.  E-mail:

  November 6-8, 1996, Palo Alto, CA, USA  
* Topics.  New hardware verification techniques based on theorem
  proving, state exploration, model-checking, and BDDs.  Correct by
  construction approaches to hardware design, such as synthesis and
  transformation.  Hybrid approaches that integrate synthesis and
  verification or different verification techniques.  Integration of
  formal methods with CAD tools, such as synthesis, simulation, and
  design exploration.  Formal verification techniques for hardware
  description languages, such as VHDL, Verilog.  Case studies and
  application of formal methods in industry.
* Invited Speakers. David Dill,  Kurt Keutzer, J S. Moore.
* Submissions.  Papers: 15 page, 11-point limit with abstract,
  containing original research in sufficient detail to assess its merits
  and relevance.  Tutorials: 4 page abstract, 15 page, 11-point for
  final.  Submit in electronically self-contained Postscript to  Deadline (firm): April 15, 1996.
* Further Information.  Please direct all paper and program inquiries to  Registration questions may be directed to
* Program Chair.  Mandayam Srivas.  Tutorials Chair: Albert Camilleri.
* Program Committee.  D. Borrione, R. Brayton, R. Bryant, R. Camposano,
  L. Claesen , E. Clarke, C. Delgado Kloos, M. Fujita, S. German,
  M. Gordon, O. Grumberg, W. Hunt, S. Johnson, R. Kumar, M. Leeser,
  P. Loewenstein, K. McMillan, C. Seger, J. Staunstrup, V. Stavridou,
  P.A. Subrahmanyam, J. Van Tassel.

  August 26/27, Cairns, Australia  
* Topics.  Novel approaches related to the problems of incomplete and
  changing information.  Theoretical foundations, in particular the
  uncovering of strong interconnections among different approaches. It
  is particularly important to combine qualitative and quantitative
  methods.  Implementations, example sets, performance evaluation.
  Actual and potential applications in diagnosis, decision support,
  software engineering, operations research, legal reasoning etc.
* Submissions.  Everybody interested in presenting should submit either
  full papers (up to 10 pages) or extended abstracts (3 to 5
  pages). Electronic submission in the form of postscript files is
  strongly preferred. In cases where this is impossible please send 4
  copies to: Grigoris Antoniou, School of Computing & Information
  Technology, Griffith University, Nathan, QLD 4111, Australia.  Phone:
  +61 7 3875 5041.  Fax: +61 7 3875 5051.  Email:
  Deadline for submission: April 30, 1996.  
* Program Committee.  Grigoris Antoniou (Co-Chair), David Billington,
  Phan Minh Dung, Boon Toh Low, Kym MacNish, Javier Pinto, Miroslaw
  Truszczynski (Co-Chair).

* Summary. The Interest Group in Pure and Applied Logics (IGPL) and the
  European Foundation of Logic, Language and Information (FoLLI) are
  happy to announce the annual prize for the best idea of the year in
  the area of pure and applied logic.  There are many prizes in the
  community and they are usually won by leading researchers with an
  established body of research.  However, progress also depends on fresh
  insights and sudden ideas, often coming from young people in the
  field. It is the latter ideas that we want to encourage.
  We therefore invite nominations for the second US$ 1000 annual IGPL 
  and FoLLI Prize for the Best Idea of the Year.  We are thinking of
  solutions to challenging open questions, but also of attractive new
  research ideas, novel connections between different aspects of logic,
  language and computation, etcetera.  These should be surprising, and
  enhance the connectivity in our field.
  We call upon IGPL and FoLLI members and any other researchers in pure
  and applied logic to put forward candidates, who came out with a prize
  worthy good idea in 1995.  It should be an idea published or in
  preprint during the year.  In certain cases, we are also prepared to
  consider prize essays written precisely for this purpose.
* Nominations.  Proposals with personal background and case for support
  should be sent to the FoLLI chairman: Professor Wilfrid Hodges, School
  of Mathematical Sciences, Queen Mary and Westfield College, Mile End
  Road, London E1 4NS, United Kingdom.  Email:  The
  prize committee consists of the FoLLI chairman, the editorial board of
  the Bulletin of the IGPL and the FoLLI board members.  Deadline for
  proposals for the 1995 prize is 1 May 1996.

  July 15--19, 1996, Ko\v{s}ice, Slovakia
* Topics.  Set theory of reals, finite and infinite combinatorics,
  algorithmic complexity, and logic in computer science.
* Program Committee.  B. Balcar, A. Blass, L. Bukovsk\'y,
  V. Dan\v{c}\'{\i}k, T. Eiter, V. Geffert, J. Hromkovi\v{c},
  J. Kraj\'{\i}\v{c}ek, M. Repick\'y (secretary), P. Vojt\'as,
  B. W\c{e}glorz.
* Associated Conference.  The Conference is organized as the satellite
  conference of the Second European Congress of Mathematics '96 (last
  week before the Congress).
* Submissions.  Deadline for abstracts of the talks is May 31, 1996. The
  abstracts must not exceed one page and can be sent by e-mail, surface
  mail, or fax. The abstract should contain the title of the talk,
  name(s) and address(es) of the author(s) (including e-mail), key
  words, a succinct statement of the problem, and the results achieved.
  Authors are encouraged to use e-mail, preparing a single file version
  of the abstract using LaTeX (document style article) or AmSTeX
  (document style amsppt), but other possibilities for the surface mail
  are not excluded.
* Registration.  Participants from the countries with convertible
  currencies are requested to pay the fees before May 15, 1996.
* Further Information. E-Mail (preferred whenever possible):  Fax: ++42 (95) 62 282 91.  Surface Mail:
  Professor Lev Bukovsk\'y, Department of Computer Science,
  P. J. \v{S}af\'arik University, Jesenn\'a 5, 041 54 Ko\v{s}ice,

  August 28--30, 1996, Stockholm, Sweden  
* Topics. The aim of the workshop is to present recent work (including
  work in progress) and discuss new ideas and trends in the following 4
  fields: program synthesis, program transformation, program
  specialization, and systematic program development, all in the context
  of declarative programming, and logic programming in particular.
  Papers developing the relationships of these topics with other areas
  of automated program development, such as implementation techniques,
  inductive logic programming, meta-languages, program analysis, program
  specification, semantics, query optimization in deductive databases,
  software engineering, synthesis and transformation in the context of
  other programming languages, are welcomed.  Papers describing
  automated systems for program development and overviews of recent work
  on the topics of interest are also solicited.
* Submissions.  Extended abstracts (5-8 pages excluding references and
  appendices) are invited (see deadlines below).  Submission of
  abstracts by e-mail is also accepted (Postscript).  Submitted papers
  will be reviewed for publication in the final proceedings which will
  be published.  Deadline for submissions: May 17, 1996
* Associated Conference.  The workshop is in the week immediately before
  the Joint International Conference and Symposium on Logic Programming
  (JICSLP'96) in Bonn, Germany.
* Programme Committee.  W. Bibel, A. Bossi, N. Fuchs, J. Gallagher,
  T. Gegg-Harrison, A. Hamfelt, P. Hill, B. Martens, U. Nilsson,
  A. Pettorossi, L. Sterling.
* Programme Chair.  John Gallagher, Department of Computer Science,
  University of Bristol, Queen's Building, University Walk, Bristol BS8
  1TR, U.K.  Phone: +44 (0)117 9287959.  Fax: +44 (0)117 9288128.

  April 21 - 23, 1996, DIMACS Center, Rutgers University
* Topics.  The workshop will emphasize the interconnections among proof
  complexity, arithmetic complexity and computational complexity.  This
  encompasses a broad range of topics of current interest, including
  Frege systems, bounded depth proof systems, cutting plane and
  Nullstellensatz proof systems, switching lemmas, recursion theoretic
  characterizations of complexity classes, bounded arithmetic and other
  feasible formal systems, cryptographic conjectures, interpolation
  theorems, independence results, interpretability and conservativity.
* Organizers.  Paul Beame and Sam Buss.  E-Mail:

  July 25-26, 1996, Rutgers University   
* Topics.  Logic and logical thinking are central to all disciplines and
  are critical in the mathematical and computer sciences.  This
  symposium will explore the teaching of introductory logic and logical
  thinking, with a primary focus on the college level and a secondary
  focus on the high school level.  The symposium will be
  interdisciplinary, emphasizing and contrasting approaches used in
  mathematics, computer science, natural sciences, and engineering.
  The symposium seeks a sharing of ideas, rather than consensus, on how
  to teach logic, so that all participants gain an appreciation for the
  fundamental issues and ultimately are better able to motivate the
  importance of logic and to convey the foundations of logical reasoning
  to students.  Topics of interest include, but are not limited to:
  pedagogical approaches; cognitive models of logical reasoning;
  empirical studies; exemplary course material; innovative approaches;
  courseware for teaching logic.
* Associated Conference.  The symposium will be held prior to the
  Federated Logic Conference (FLoC).
* Further Information.  Peter Henderson, Department of Computer Science,
  SUNY Stony Brook, Stony Brook, N.Y. 11794-4400 USA.  (516) 632-8463,

  June 3-5, 1996, University of Colorado, Boulder  
* Topics.  This series of meetings has the goal of bringing together
  mathematicians and theoretical computer scientists to discuss problems
  of common interest and to explore common areas of research.  MFPS has
  focused particularly on programming semantics and related issues,
  including, for example, linear logic and related topics.
* Invited Speakers.  Peter Freyd, Mel Fitting, Matthew Hennessy, Gerard
  Huet, Andre Scedrov, Jeannette Wing.
* Program.  This is a workshop year for MFPS, which means that the
  remainder of the program will be made up of talks by participants.
  The slots for these talks will be allotted on a first-come,
  first-served basis.
* Funding.  Also as in the past, we have received some funding from the
  Office of Naval Research.  While the funding is limited, we especially
  encourage women and minorities, as well as graduate students, to
  inquire about possible support to attend the meeting.
* Co-chairs.  Michael Main and Michael Mislove.
* Further Information.  Those who do not have access to the World Wide
  Web can obtain updates by sending email to
* Registration.  Deadline May 1.  Registration form.

* Journal.  JUCS is Springer's new electronic journal available
  world-wide through the internet and setting up a new standard for
  electronic publishing.  For further information on JUCS, including the
  format, go here or send an empty email
  to with the following subject: info,format.
* Publication Date.  The volume is going to appear in the Spring of
  1997. Following the well established JUCS policy, there will be both
  an electronic (www accessible) edition of the special issue and a
  paper edition appearing at the end of the year.
* Topics.  The issue is open to advanced and innovative applications as
  well as theoretical achievements. Research contributions with
  cross-disciplinary or research-to-practice content are particularly
  welcome, including industrial applications, challenging case studies
  and reports on mature implementations. The area of the submitted paper
  may belong to any field of computer science or engineering.
* Submissions.  Papers must be submitted in 5 hard copies to arrive not
  later than Dec 1, 1996 at the following address: Egon Boerger,
  Dipartimento di Informatica, Universita di Pisa, Corso Italia 40, I -
  56 125 PISA/ Italy.  An electronic copy in ps-format should be
  available and be sent in case of specific request.
* Further Information.

  July 30, 1996, Rutgers University, New Brunswick, USA  
* Topics.  This workshop focuses on proof search in type-theoretic
  languages and their underlying logics. Such languages are logical
  frameworks for representing proofs and in some cases formalize
  connections between proofs and programs that support program
  synthesis.  Topics of interest, in this context, include (but are not
  restricted to): foundations of proof search, techniques and concepts
  related to proof construction, logic programming, proof synthesis vs
  program synthesis, applications, equational theories and rewriting,
  decision procedures, environments for formal proof development.
* Submissions.  Send an extended abstract (5-8 pages) by e-mail
  submissions of Postscript files to the Organizing-Program Chair
  ( before May 12, 1996.  Researchers
  interested in attending the workshop (without giving a presentation)
  should send a position paper (1-2 pages) presenting their interest.
* Attendance. Attendance is by invitation only: authors of accepted
  submissions will be invited.
* Organizing/Program Committee.  D. Galmiche (Chair), F. Pfenning,
  N. Shankar, J. Smith, L. Wallen.

  July 7-12, 1996, Isle of Thorns, East Sussex, England
* Further Information.  In order to receive further details of the
  meeting, together with an application form for accommodation at the
  meeting, please reply by sending your name and postal address either
  by email to:; or by post to: Dr. Christopher
  J. Mulvey, School of Mathematical Sciences, University of Sussex,
  Falmer, brighton, BN1 9QH, United Kingdom.
* Deadline.  The completed application form must be returned by the
  closing date of 15th May, 1996.

  July 30, 1996, Rutgers University, New Brunswick, USA  
* Topics.  Many practical applications of deduction systems in
  mathematics and computer science rely on the correct and efficient
  treatment of partial functions.  There is a rich variety of approaches
  for dealing with partial functions and the undefined expressions that
  often result from their application.  Ranging from workarounds for
  concrete situations to proper general treatments, these approaches
  have their own advantages and disadvantages.  For example, some can be
  used in standard logical formalisms, while others require new
  formalisms.  The purpose of the workshop is to discuss the different
  approaches and to compare their advantages and disadvantages.
* Submissions.  The workshop will solicit two kinds of contributions:
  short papers (up to 6 pages) which argue for a particular approach to
  mechanizing partial functions; ordinary research papers (up to 12
  pages) which address issues concerning the use and implementation of
  partial functions in automated reasoning systems.  Potential
  participants can apply either by submitting a short statement that
  contains a description of their current interests or, if they wish to
  make a (short or long) presentation, an abstract of the work they want
  to present.  The short statements and abstracts should be sent by
  e-mail to Manfred Kerber at by 24 May.
* Organizers.  William Farmer (, Manfred Kerber
  (, Michael Kohlhase (

LOGICS AND MODELS OF COMPUTATION                         
  Sept 16-20, 1996, Institut de Mathematiques de Luminy, Marseille  
* Topics.  One of the main problems in computer science is the
  understanding of the notion of computation, that is to say, the
  dynamics of processes in itself rather than their results. The stake
  is on two different levels.  Practical : the aim being to develop
  languages, or even efficient machines, e.g.  think of the multiple
  problems raised by parallelism.  Theoretical : the notion of
  computation plays a main role in logic, especially in proof theory;
  recent developments stress its dynamics.
  The goal of this Conference is to compare the various approaches, more
  specifically, those from computer science, which have a practical aim:
  G.Berry's work (Esterel) or the CCS system and its recent
  variations of Robin Milner and more theoretical approaches;
  J.L. Krivine's abstract machine or Girard's Linear Logic and its
  computational applications, interaction nets and geometry of
  Topics to be discussed: digital circuits; Pi-calculus; environment
  machines; proof and interaction nets; geometry of interaction and
  optimal execution; the logical aspect of proof search.
* Confirmed Speakers.  Jean-Marc Andreoli, Denis Bechet, Ge'rard Berry,
  Ge'rard Boudol, Albert Burroni, Pierre-Louis Curien, Vincent Danos,
  Philippe De Groote, Eric Goubault, Gerard Huet, Jean-Louis Krivine,
  Philippe Matherat, Guy Perrier, Jean Vuillemin Sergei Artemov, Andrea
  Asperti, Stefano Berardi, Thierry Coquand, Francis Davey, Max
  Kanovich, Alexei Kopylov, Francois Lamarche, Dale Miller, Mati Pentus,
  Thomas Streicher.
* Programme Committee.  G.Berry, J-Y.Girard, M.Kanovich, J-L.Krivine,
  Y.Lafont, F.Lamarche.
* Organizing chair : Marie-Renee Donnadieu-Fleury.  Departement de
  Mathe'matiques-Informatique, Faculte' des Sciences de Luminy, Case
  901, 13288 Marseille Cedex 9, France.  tel : 91 26 90 47.  Fax: 91 26
  93 56.  E-mail:  Also: IML- CNRS, Equipe Logique
  de la Programmation, 163 Avenue de Luminy, Case 930, 13 288 Marseille
  Cedex 9, France.  E-mail :

  R. Lassaigne and M. de Rougemont  
* Summary.  This book, intended for graduate students and researchers,
  follows the introductory book : Logic and foundations of Computer
  Science (Hermes Editions 1993, 250 pages, in french). We present most
  of the Complexity Classes both from the structural and descriptive
  point's of view.
* Table of Contents.  1. Complexity : time and space.  2. Definability.
  3. Inductive definability and second-order logic.  4. Time complexity
  : the classes P and NP.  5. Space complexity : L, NL, FL and PSPACE.
  6. Parallel model of computation.  7. Probabilistic classes.
  8. Approximation.  9. Classes above NP.  10. Logic and computability.
* To Order.  Contact Claudine Bembaron, Hermes editions, 14 rue lantiez,
  75018 Paris, France.  Email :  Fax: (1) 42
  29 15 56. Tel: (1) 42 29 44 66.

[last item in newsletter]

Dear Colleague:

Over the past few years attendance at the ACM Principles of Database
Systems (PODS) conference has increased.  However, there has been a
significant decline in the number of submissions (although the
submissions continue to be of very high quality).  The PODS Executive
Committee is concerned about this trend, and would like to poll the
broad PODS community for ideas on how to increase submissions to PODS.

We'd appreciate it if you could respond to the questionnaire below.

Please send the answers to 
by April 15, 1996.

Alberto Mendelzon
PODS 97 General Chair


1. How many papers did you submit to PODS'96?
   Answer: ___

2. How many papers did you submit to PODS between 
   1993 and 1995, inclusive?
   Answer: ___

3. How many papers did you ever submit to PODS?
   Answer: ___

4. How many times did you attend PODS between
   1991 and 1995, inclusive ?
   Answer: ___

5. PODS submissions have been restricted to be at most 5000 words, 
   i.e., about 10 double-spaced pages (with an optional appendix).  
   Do you feel that this restriction should be relaxed, e.g., to 
   permit submissions of up to 8000 words ? 
   Answer (5 = very strongly, 1 = not at all): ___

6. With PODS, the tradition is that almost all members of the program 
   committee read almost all of the submissions.  Do you support
   maintaining this tradition ?  
   Answer (5 = very strongly, 1 = not at all): ___

7. What database research areas are you mostly interested in? (Please
   put an "X" in the appropriate boxes.)
   [] Active DBs
   [] Access Methods and Data Structures
   [] Approximate data
   [] Concurrency, Recovery, Distributed DBs
   [] Data Mining
   [] Data Models
   [] DB Interoperation
   [] Languages: Query, Update, DB Programming
   [] Logic in Databases, Datalog
   [] Non-standard DBs (scientific, GIS, hypermedia, temporal, text)
   [] Views
   [] Other  ______________________________

8. If you have a paper that might fit into PODS or SIGMOD, how
   do you decide which conference to submit the paper to?

9. Please rate the percentage of papers, invited talks, and tutorials
   presented at recent PODS conferences you have found interesting 
   (5 = almost all, 1 = almost none)
      Papers: ___
      Tutorials: ___
      Invited talks: ___

10. Please rate the percentage of papers, invited talks, and tutorials
    presented at recent SIGMOD conferences you have found interesting 
    (5 = almost all, 1 = almost none)
      Papers: ___
      Tutorials: ___
      Invited talks: ___

11. How do you rate the balance of the topics in recent PODS programs?
    (5 = very good, 1 = very poor)  
    Answer: ___

12. What areas of research did you find to be under-represented in recent
    PODS programs? 

13. What areas of research did you find to be over-represented in recent
    PODS programs?

14. Do you think that the scope of the PODS conference should be
    expanded?  If so, in what directions? 

15. How can PODS be made into a better conference for you?