[FOM] CFP: Workshop CEDAR 2008

Miki Hermann hermann at lix.polytechnique.fr
Mon May 5 16:22:27 EDT 2008

*                                                                     *
* Complexity, Expressibility, and Decidability in Automated Reasoning *
*                             (CEDAR'08)                              *
*          http://www.mpi-inf.mpg.de/~sofronie/cedar08.html           *
*                                                                     *
*   Affiliated with IJCAR 2008 Sydney, Australia, 10-15 August 2008   *
*                     http://www.ijcar.org/2008/                      *
*                                                                     *

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 CEDAR   is to  bring  together researchers   interested in
problems   that are in the   interface between automated reasoning and
computational complexity, in particular 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


Topics of interest for CEDAR 2008 include (but are not restricted to):
  - Complexity:
    - complexity analysis for fragments of first- (or higher) order
    - complexity analysis for combinations of logical theories
      (including parameterized complexity results)
  - Expressibility (in logic, automated reasoning, algebra, ...)
  - Decidability:
    - decision procedures based on logical calculi such as:
      resolution, rewriting, tableaux, sequent calculi, or natural deduction
    - decidability in combinations of logical theories
  - Application domains for which complexity issues are essential
    (verification, security, databases, ontologies, ...)

The  goal of CEDAR   is  to bring together  researchers  interested in
exploring the topics above, both  at a theoretical level and motivated
by applications, and  to  enhance  the interaction between   automated
reasoning and computational complexity through invited and contributed

The ultimate aim is to  expand the horizons of  this area of research,
deepen the interactions,  sensibilize other people  from the automated
reasoning community  to   the complexity problems,  and   last but not
least,  offer persons working in   research and development centers of
software companies the possibility to get an overview of the problems.

Invited speaker
  - Carsten Lutz (TU Dresden)

Program and Workshop Chairs
  - Franz Baader (TU Dresden)
  - Silvio Ghilardi (U. Milano)
  - Miki Hermann (Ecole Polytechnique, Palaiseau)
  - Ulrike Sattler (U. Manchester)
  - Viorica Sofronie-Stokkermans (MPI, Saarbrücken)

Program Committee
  - Carlos Areces (INRIA Nancy)
  - Franz Baader (TU Dresden)
  - Matthias Baaz (TU Wien)
  - Maria Paola Bonacina (U. Verona)
  - Sebastian Brandt (U. Manchester)
  - Christian Fermüller (TU Wien)
  - Silvio Ghilardi (U. Milano)
  - Reiner Haehnle (Chalmers U.)
  - Miki Hermann (Ecole Polytechnique, Palaiseau)
  - Felix Klaedtke (ETH Zurich)
  - Sava Krstic (Intel Corporation)
  - Christopher Lynch (Clarkson U.)
  - Bijan Parsia (U. Manchester)
  - Silvio Ranise (LORIA/INRIA-Lorraine)
  - Ulrike Sattler (U. Manchester)
  - Renate Schmidt (U. Manchester)
  - Viorica Sofronie-Stokkermans (MPI,Saarbrücken)
  - Lidia Tendera (U. Opole)
  - Ashish Tiwari (SRI International)
  - Luca Vigano (U. Verona)
  - Frank Wolter (U. Liverpool)

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.


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.

Important Dates
  - 19 May 2008:          Submission deadline
  - 19 June 2008:         Notification
  - 10 July 2008:         Final version
  - 10 August 2008:       Workshop


For further informations please send an e-mail to

      Viorica Sofronie-Stokkermans (sofronie [at] mpi-inf.mpg.de)

More information about the FOM mailing list