Automated Deduction: Decidability, Complexity, Tractability

Affiliated with CADE-21 Bremen, Germany, 15 July, 2007

All sessions will take place at the International University Bremen, in the West Hall. Click here for a map of the campus.

NEW: Call for papers

for special issue on Automated Deduction: Decidability, Complexity, Tractability

in the Journal of Symbolic Computation

Invited speaker

Michaël Rusinowitch (LORIA-INRIA-Lorraine)



ADDCT proceedings



  • Silvio Ghilardi (U. Milano)
  • Ulrike Sattler (U. Manchester)
  • Viorica Sofronie-Stokkermans (MPI,Saarbrücken)
  • Ashish Tiwari (Menlo Park)
  • Program Committee

  • Matthias Baaz (T.U.Wien)
  • Maria Paola Bonacina (U. Verona)
  • Christian Fermüller (T.U.Wien)
  • Silvio Ghilardi (U. Milano)
  • Reiner Haehnle (Chalmers U.)
  • Felix Klaedtke (ETH Zurich)
  • Sava Krstic (Intel Corporation)
  • Viktor Kuncak (EPFL Lausanne)
  • Carsten Lutz (TU Dresden)
  • Christopher Lynch (Clarkson U.)
  • Silvio Ranise (LORIA/INRIA-Lorraine)
  • Ulrike Sattler (U. Manchester)
  • Renate Schmidt (U. Manchester)
  • Viorica Sofronie-Stokkermans (MPI,Saarbrücken)
  • Ashish Tiwari (SRI)
  • Luca Vigano (U. Verona)
  • Call for papers


    Submission procedure


    Important Dates

  • 11 May 2007: Submission deadline
  • 5 June 2007: Notification
  • 15 June 2007: Final version
  • 15 July 2007: Workshop
  • Contact

    For further informations please send an e-mail to

    Decidability, and especially complexity and tractability of logical theories is extremely important for a large number of applications. Although general logical formalisms (such as predicate logic or number theory) are undecidable, decidable theories or decidable fragments thereof (sometimes even with low complexity) often occur in mathematics, in program verification, in the verification of reactive, real time or hybrid systems, as well as in databases and ontologies. It is therefore important to identify such decidable fragments and design efficient decision procedures for them. It is equally important to have uniform methods (such as resolution, rewriting, tableaux, sequent calculi, ...) which can be tuned to provide algorithms with optimal complexity.

    The goal of ADDCT is to bring together researchers interested in

  • identifying (fragments of) logical theories which are decidable, identifying fragments thereof which have low complexity, and analyzing possibilities of obtaining optimal complexity results with uniform tools;
  • analyzing decidability in combinations of theories and possibilities of combining decision procedures;
  • efficient implementations for decidable fragments;
  • application domains where decidability resp. tractability are crucial.

  • Topics

    Topics of interest for ADDCT include (but are not restricted to):
  • Decidability:
  • decision procedures based on logical calculi such as:
    resolution, rewriting, tableaux, sequent calculi, or natural deduction
  • decidability in combinations of logical theories
  • Complexity:
  • complexity analysis for fragments of first- (or higher) order logic
  • complexity analysis for combinations of logical theories
    (including parameterized complexity results)
  • Tractability (in logic, automated reasoning, algebra, ...)

  • Application domains for which complexity issues are essential
    (verification, security, databases, ontologies, ...)
  • The goal of ADDCT is to bring together researchers interested in exploring the topics above, both at a theoretical level and motivated by applications.

    Submission and selection procedure:

    We plan to accept three types of papers:
  • Original papers (up to 15 pages, LNCS style, including bibliography); should describe original research and contain sufficient detail to assess the merits and relevance of the contribution. Simultaneous submission of material is prohibited.

  • Work in progress (up to 6 pages, LNCS style, without bibliography).

  • Presentation-only papers (please submit an abstract of up to 3 pages, LNCS style + a link to the already published paper): may describe work previously published. The abstracts of accepted presentation-only papers will appear in the informal proceedings to be distributed at the workshop (full papers in this category will not be inserted in the proceedings).
    We are allowing the submission of previously published work in order to allow researchers to communicate good ideas that the attendees may not be aware of.

  • Given the informal style of the workshop, the submission of papers presenting student's work and work in progress is encouraged.
    Submission of papers is via Easychair


    The final versions of the selected contributions will be collected in a volume to be distributed at the workshop. These informal proceedings will also be made accessible on the web.

    A special issue of the Journal of Symbolic Computation on the topic of the ADDCT workshop is planned.


    Silvio Ghilardi      Viorica Sofronie-Stokkermans
    Università degli Studi di Milano Max-Planck-Institut für Informatik, Saarbrücken
    Ulrike Sattler      Ashish Tiwari
    University of Manchester Stanford Research International