ASSOCIATION FOR AUTOMATED REASONING

NEWSLETTER No. 78, October 2007

From the AAR President
Results of the CADE Trustee Elections 2007
Call for Papers, Workshops, and Posters

  • TAP 2008
  • IJCAR 2008
  • New Constitutional Frame for IJCAR
    Journal of Logic, Language and Information (JOLLI) Special Issue on Visual Languages and Logic
    Book Review

    From the AAR President, Larry Wos... My congratulations to the new officers of CADE's board of trustees. The competition was intense this year, and I hope that many of the candidates' ideas for promoting automated reasoning will be carried out in the next few years. Of course, conferences are an excellent arena for presenting ideas. IJCAR 2008 (and all the associated conferences) includes a call for presentations on working automated deduction systems. The key word is "working" -- and I'd love to hear from those of you who have working systems that are answering open questions in mathematics or logic. I also note a repeated theme in this newsletter: program testing and verification. TAP 2008 has issued a call for papers on testing and verification techniques, and a new book reviewed by Martin Leucker also covers program verification. If you have material to contribute to these topics, please let me know.

    Results of the CADE Trustee Elections 2007
    Wolfgang Ahrendt
    (Secretary of AAR and CADE)
    E-mail: ahrendt@chalmers.se

    An election was held from September 11 through October 2 to fill four positions on the board of trustees of CADE Inc. Christoph Benzmüller, Maria Paola Bonacina, Amy Felty, Robert Nieuwenhuis, Brigitte Pientka, Volker Sorge, Geoff Sutcliffe, and Andrei Voronkov were nominated for these positions. (See AAR Newsletter No. 77, September 2007.)

    Ballots were sent by electronic mail to all members of AAR on September 11, for a total of 736 ballots. Of these, 121 were returned with a vote, representing a participation level of 16.4% (as compared to 16.0% in 2006, 18.1% in 2005, and 19.8% in 2004 and 2003). One vote was invalid (double listing of one candidate), meaning there are 120 valid votes. Therefore, in each iteration of the STV algorithm1, a candidate is elected iff he or she gets strictly more than 60 1st preference votes. Otherwise, the votes of the candidate with the least 1st preference votes are redistributed.

    The following table reports the initial distribution of preferences among the candidates:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 18 13 12 13 11 6 4 43 120
    M.P. Bonacina 29 14 14 11 7 6 6 33 120
    A. Felty 15 20 10 17 8 8 6 36 120
    R. Nieuwenhuis 10 7 13 11 13 9 2 55 120
    B. Pientka 8 10 20 8 7 9 5 53 120
    V. Sorge 5 6 11 9 8 6 10 65 120
    G. Sutcliffe 18 22 17 15 9 3 0 36 120
    A.Voronkov 17 23 11 12 5 5 6 41 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of V. Sorge, one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 20 14 11 13 12 4 12 34 120
    M.P. Bonacina 29 16 14 11 7 9 15 19 120
    A. Felty 15 20 15 13 10 9 17 21 120
    R. Nieuwenhuis 10 7 16 12 12 8 25 30 120
    B. Pientka 8 13 19 9 7 8 22 34 120
    G. Sutcliffe 20 22 18 18 5 1 15 21 120
    A.Voronkov 18 23 13 11 6 6 20 23 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of B. Pientka, one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 21 17 12 13 9 12 14 22 120
    M.P. Bonacina 30 19 12 14 11 9 12 13 120
    A. Felty 17 20 15 19 7 13 13 16 120
    R. Nieuwenhuis 12 8 18 11 14 17 21 19 120
    G. Sutcliffe 21 25 26 10 1 10 15 12 120
    A.Voronkov 19 26 17 7 8 11 20 12 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of R. Nieuwenhuis one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 25 15 17 12 13 9 15 14 120
    M.P. Bonacina 32 19 17 15 9 8 13 7 120
    A. Felty 18 20 19 20 11 8 17 7 120
    G. Sutcliffe 22 32 23 5 10 6 15 7 120
    A.Voronkov 23 25 17 10 9 9 19 8 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of A. Felty one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 28 21 14 19 6 11 15 6 120
    M.P. Bonacina 37 18 23 13 7 8 10 4 120
    G. Sutcliffe 28 37 17 10 3 10 10 5 120
    A.Voronkov 27 29 19 8 6 15 13 3 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of A.Voronkov one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 36 21 25 4 9 13 9 3 120
    M.P. Bonacina 44 31 14 8 6 10 6 1 120
    G. Sutcliffe 36 40 15 3 4 12 8 2 120

    No candidate reaches more than 60 1st preference votes. C. Benzmüller and G. Sutcliffe have the same number of 1st preference votes, but G. Sutcliffe is higher in the ranking because of receiving more 2nd preference votes. By redistributing the votes of C. Benzmüller one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    M.P. Bonacina 56 33 6 6 9 6 3 1 120
    G. Sutcliffe 54 36 4 1 11 7 5 2 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of G. Sutcliffe one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    M.P. Bonacina 89 4 7 8 5 4 3 0 120

    Now M.P. Bonacina reaches more than 60 1st preference votes, and is elected to the board of trustees. The redistribution of her votes produces the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 21 12 18 14 7 5 32 11 120
    A. Felty 25 15 16 11 8 9 22 14 120
    R. Nieuwenhuis 11 12 12 14 12 4 38 17 120
    B. Pientka 12 13 17 8 11 5 35 19 120
    V. Sorge 5 10 13 7 8 12 46 19 120
    G. Sutcliffe 24 25 15 13 7 0 26 10 120
    A.Voronkov 20 25 10 9 6 8 32 10 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of V. Sorge one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 23 13 19 12 7 10 27 9 120
    A. Felty 25 18 15 11 12 14 15 10 120
    R. Nieuwenhuis 11 12 16 14 12 20 23 12 120
    B. Pientka 12 17 15 10 9 17 27 13 120
    G. Sutcliffe 26 26 16 15 1 13 15 8 120
    A.Voronkov 21 25 12 8 10 16 23 5 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of R. Nieuwenhuis one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 25 17 20 11 9 14 18 6 120
    A. Felty 26 18 18 17 9 16 11 5 120
    B. Pientka 14 20 14 12 12 21 20 7 120
    G. Sutcliffe 28 27 22 7 7 13 12 4 120
    A.Voronkov 24 25 11 13 10 18 15 4 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of B. Pientka one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 29 19 20 14 6 15 12 5 120
    A. Felty 29 18 25 15 7 12 10 4 120
    G. Sutcliffe 31 37 14 9 6 10 11 2 120
    A.Voronkov 28 26 16 12 10 14 13 1 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of A.Voronkov one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 36 26 20 4 10 14 9 1 120
    A. Felty 32 33 21 4 11 10 8 1 120
    G. Sutcliffe 42 34 15 3 6 12 8 0 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of A. Felty one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 47 35 2 9 12 9 5 1 120
    G. Sutcliffe 58 33 1 5 9 9 5 0 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of C. Benzmüller one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    G. Sutcliffe 90 2 2 10 6 6 4 0 120

    Now G. Sutcliffe reaches more than 60 1st preference votes, and is elected to the board of trustees. The redistribution of his votes produces the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 23 18 20 10 5 22 18 4 120
    A. Felty 30 20 16 9 7 14 18 6 120
    R. Nieuwenhuis 13 17 14 15 6 24 27 4 120
    B. Pientka 13 20 13 13 7 24 23 7 120
    V. Sorge 7 13 13 5 15 35 24 8 120
    A.Voronkov 31 20 11 8 7 20 20 3 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of V. Sorge one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 27 16 23 6 10 20 14 4 120
    A. Felty 31 23 14 11 13 11 11 6 120
    R. Nieuwenhuis 13 20 14 18 14 21 16 4 120
    B. Pientka 14 22 16 9 14 25 14 6 120
    A.Voronkov 32 23 9 11 13 17 13 2 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of R. Nieuwenhuis one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 30 24 17 10 11 14 12 2 120
    A. Felty 32 26 19 11 10 9 11 2 120
    B. Pientka 17 25 16 14 14 18 14 2 120
    A.Voronkov 36 22 13 12 10 16 10 1 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of B. Pientka one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 34 30 17 4 15 9 9 2 120
    A. Felty 37 30 20 4 11 7 9 2 120
    A.Voronkov 43 25 14 7 10 14 7 0 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of C. Benzmüller one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    A. Felty 51 36 4 5 11 5 6 2 120
    A.Voronkov 53 29 6 5 17 5 5 0 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of A. Felty one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    A.Voronkov 81 4 6 14 8 4 3 0 120

    Now A.Voronkov reaches more than 60 1st preference votes, and is elected to the board of trustees. The redistribution of his votes produces the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 31 20 16 9 15 17 12 0 120
    A. Felty 40 18 15 8 8 17 13 1 120
    R. Nieuwenhuis 21 18 17 7 16 21 19 1 120
    B. Pientka 14 26 12 14 16 19 18 1 120
    V. Sorge 8 16 13 13 29 21 18 2 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of V. Sorge one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 35 21 14 11 15 12 12 0 120
    A. Felty 41 22 14 10 12 9 11 1 120
    R. Nieuwenhuis 22 20 20 12 14 19 12 1 120
    B. Pientka 16 27 16 13 17 19 11 1 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of B. Pientka one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 37 30 14 6 16 7 10 0 120
    A. Felty 47 24 15 6 10 8 9 1 120
    R. Nieuwenhuis 27 27 19 8 12 19 8 0 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of R. Nieuwenhuis one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    C. Benzmüller 51 30 3 10 12 7 7 0 120
    A. Felty 53 33 2 10 7 9 6 0 120

    No candidate reaches more than 60 1st preference votes. By redistributing the votes of C. Benzmüller one gets the following table:

    Candidate 1st pref. 2nd pref. 3rd pref. 4th pref. 5th pref. 6rd pref. 7th pref. 8th pref. Total
    A. Felty 86 2 6 8 8 5 5 0 120

    Now A. Felty reaches more than 60 1st preference votes, and is elected to the board of trustees.


    Altogether, the four candidates which are elected to the board of trustees in this election are M. P. Bonacina, G. Sutcliffe, A. Voronkov, and A. Felty.

    After this election, the following people (listed alphabetically) are serving on the board of trustees of CADE Inc.:

    Wolfgang Ahrendt (Secretary, appointed 5/2007)
    Alessandro Armando (IJCAR 2008 Program Co-chair)
    Franz Baader (President, CADE-19 Program Chair, elected 10/2003, reelected 10/2006)
    Peter Baumgartner (elected 10/2003, reelected 10/2006)
    Maria Paola Bonacina (Secretary 9/1999 to 5/2004, elected 10/2004, reelected 10/2007)
    Amy Felty (Secretary 5/2004 to 5/2007, elected 10/2007)
    Reiner Hähnle (Vice President, elected 10/2005)
    Neil Murray (Treasurer)
    Geoff Sutcliffe (elected 10/2004, reelected 10/2007)
    Aaron Stump (elected 10/2006)
    Cesare Tinelli (elected 10/2005)
    Andrei Voronkov (CADE-18 Program Chair, elected 10/2002, Vice President 2003, elected 10/2007)

    On behalf of the AAR and CADE Inc., I thank David Basin and Rajeev Goré for their service as trustees during the past three years, all candidates for running in the election, all the members who voted; and offer congratulations to Maria Paola Bonacina, Amy Felty, Geoff Sutcliffe, and Andrei Voronkov on being elected.

    Call for Papers, Workshops, and Posters

    TAP 2008

    The second international conference on Tests and Proofs (TAP) will take place April 9-11, 2008, in Prato (near Florence), Italy. The TAP conference is devoted to the convergence of proofs and tests. It combines ideas from both sides for the advancement of software quality.

    To prove the correctness of a program is to demonstrate, through impeccable mathematical techniques, that it has no bugs; to test a program is to run it with the expectation of discovering bugs. The two techniques seem contradictory: if you have proved your program, it's fruitless to comb it for bugs; and if you are testing it, that is surely a sign that you have given up on any hope to prove its correctness. Accordingly, proofs and tests have, since the onset of software engineering research, been pursued by distinct communities using rather different techniques and tools. And yet the development of both approaches leads to the discovery of common issues and to the realization that each may need the other. The emergence of model checking has been one of the first signs that contradiction may yield to complementarity, but in the past few years an increasing number of research efforts have encountered the need for combining proofs and tests, dropping earlier dogmatic views of incompatibility and taking instead the best of what each of these software engineering domains has to offer.

    How does deduction help testing? How does testing help deduction? How can the combination of testing and deduction increase the reach of both? TAP 2008 seeks to address these questions. Topics include the following:

  • Generation of test data, oracles, or preambles by deductive techniques such as theorem proving, model checking, symbolic execution, constraint logic programming, etc.
  • Generation of specifications by deduction
  • Verification techniques combining proofs and tests
  • Program proving with the aid of testing techniques
  • Transfer of concepts from testing to proving (e.g., coverage criteria)
  • Automatic bug finding
  • Formal frameworks
  • Tool descriptions and experience reports
  • Case studies
  • The abstract submission deadline November 2, 2007; papers are due November 9, 2008.

    Submissions should describe previously unpublished work (completed or in progress), including descriptions of research, tools, and applications. Papers must be formatted following the Springer LNCS guidelines and be at most 15 pages long. Submission of papers is via EasyChair. The proceedings are planned to be published within Springer's LNCS series. They will be available at the conference.

    For further information, see the Web site.

    IJCAR 2008

    The 4th International Joint Conference on Automated Reasoning will take place in Sydney, Australia, August 10-15, 2008.

    IJCAR 2008 is a merger of several leading events:

  • CADE (Conference on Automated Deduction),
  • FroCoS (Workshop on Frontiers of Combining Systems),
  • FTP (Workshop on First-order Theorem Proving) and
  • TABLEAUX (Conference on Analytic Tableaux and Related Methods)
  • The IJCAR technical program will consist of presentations of high-quality original research papers, system descriptions, and invited talks, as well as two days of workshops and tutorials preceding the main conference.

    IJCAR 2008 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. See the IJCAR website for a detailed list of logics, methods, and applications of interest. The proceedings of IJCAR 2008 will be published by Springer-Verlag in the LNAI/LNCS series.

    Submission is electronic, through EasyChair. Authors are strongly encouraged to use LaTeX and the Springer "llncs" format, which can be obtained from the Springer website. The page limit is 15 pages for full papers and 5 pages for system descriptions.

    The paper registration deadline is February 22, 2008; the paper submission deadline is March 2, 2008.

    Workshops and Tutorials

    Workshop and tutorial proposals on IJCAR-related topics are solicited. Proposals that promise to bring new topics into IJCAR, of either practical or theoretical importance, or provide a forum for more detailed discussion on central topics of continuing importance are highly welcome. Proposals that close the gap between automated reasoning and related areas, e.g., formal methods or software engineering, are especially encouraged.

    Proposals must contain information sufficient for the programme committee to judge the importance, quality and community interest in the proposed topic. Each workshop or tutorial must have one or more designated organizers, and may have a programme committee as well.

    Proposals must be limited to three pages and provide at least the following information:

  • Title
  • Description of the workshop topic and goals. (Why do you believe this is an interesting and significant topic?)
  • Intended audience. (From which areas do you expect potential participants to come? How many participants do you expect?);
  • Organization of the workshop. (Describe the intended format of the workshop, its expected duration (from half a day to two days) and preferred dates (August 10 or 11 or both).)
  • Organizers' details. (Provide affiliations, backgrounds and contact details (email, etc.) of organizers and committee members)
  • Proposals should be sent as plain text and as PDF to the workshop chair Michael Norrish (NICTA) (michael.norrish@nicta.com.au).

    Important dates: Deadline for proposal submissions: December 17, 2007; deadline for camera-ready copy of workshop notes: July 14, 2008 For further information, see the Web site.

    New Constitutional Frame for IJCAR

    IJCAR, the International Joint Conference on Automated Reasoning, has a new constitutional frame. And thanks to Geoff Sutcliffe, IJCAR also has a Web presence, at www.ijcar.org. Located there are the new IJCAR Rules and the IJCAR Steering Committee.

    Journal of Logic, Language and Information (JOLLI)
    Special Issue on Visual Languages and Logic

    Diagrams of one sort or another have always been used as aids to abstract reasoning. Although many are informal mnemonics, reminding their authors about structures and relationships they have observed or deduced, considerable research effort has been expended on formalising graphical notations so that they may play a more central role in the application of logic to problems.

    While early work concentrated on diagrammatic representations of logic as a more intuitive or revealing paper-based replacement for textually represented logic, research in this area now mostly involves notations specifically designed for computer implementation either as computational models or interface languages. Examples include relational and existential graphs (C.S. Peirce), conceptual graphs (J.F. Sowa), various flavours of semantic networks such as conceptual dependency graphs (R. Schank), graphical deduction systems such as clause interconnectivity graphs (S. Sickel), Venn diagrams, Euler diagrams, constraint diagrams, and visual logic programming languages.

    Following the success of the 2007 Workshop on Visual Languages and Logic VLL 2007, we are soliciting, for a special issue of JOLLI, papers in which the primary focus is research at the intersection of logic and visual languages. In particular, we invite VLL 2007 authors to submit updated and expanded versions of their papers. Topics of interest include the following:

  • Graphical notations for logics (either classical or nonclassical, such as first or higher order logic, temporal logic, description logic, independence friendly logic, spatial logic)
  • Diagrammatic reasoning
  • Theorem proving
  • Formalisation (syntax, semantics, reasoning rules)
  • Expressiveness of visual logics
  • Visual logic programming languages
  • Visual specification languages
  • Applications
  • Tool support for visual logics
  • Those who intend to submit a paper should email a title, abstract, and keywords to VLL@cs.dal.ca by November 30, 2007. This information will be used to assign referees in advance of the paper deadline. Papers may be up to 30 pages, must conform to the JOLLI style (see following URL), and be emailed as a PDF to VLL@cs.dal.ca by January 31, 2008. Note that although PDF is not the required format for the final copies of accepted papers, it is the most convenient for reviewing.

    Book Review
    by Martin Leucker

    The Calculus of Computation: Decision Procedures with Applications to Verification by Aaron R. Bradley and Zohar Manna (Springer-Verlag Berlin Heidelberg 2007, ISBN 978-3-540-74112-1) presents a logical approach to modeling, analyzing, and verifying sequential programs. It is divided into two parts. Part I covers foundations of first-order logic and program verification. This part presents standard material of an undergraduate course plus a detailed chapter on program verification.

    Part II presents decision procedures for various theories, discusses the combination of decision procedures, and concludes with an outlook on program analysis. This second part of the book is well suited for a graduate course on decision procedures, motivated by program verification but also, probably leaving out Section 10, motivated when dealing with all sorts of constraint solving.

    The book is written in a semi-formal style, and most of the material is easy accessible thanks to the explanations and many examples given by the authors. It is well suited as a basis and reference for introductory courses on logic and program verification but especially for advanced courses on decision procedures. Thus, it is also valuable for lecturers compiling their preferred course from the rich material covered in this book.


    Gail Pieper
    2007-10-17