posted by user: Yoric || 1906 views || tracked by 4 users: [display]

CEDAR 2008 : Complexity, Expressibility, and Decidability in Automated Reasoning


When Aug 10, 2008 - Aug 15, 2008
Where Sydney, Australia
Submission Deadline May 19, 2008
Notification Due Jun 19, 2008
Categories    complexity   expressibility   decidability   automated reasoning

Call For Papers

Decidability, and especially complexity and tractability of logical
theories is extremely important for a large number of applications.
Although general logical formalisms are undecidable, decidable theories
- or 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 (e.g. 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
at the interface between automated reasoning and computational complexity,
in particular in:

- identifying (fragments of) logical theories which are decidable,
resp. 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 of interest for CEDAR 2008 include (but are not restricted to):

- Complexity:
- complexity analysis for fragments of first- (or higher) order logic
- 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
- specialized decision procedures

- 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 talks.

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.

- 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).

Given the informal style of the workshop, the submission of papers
presenting student's work and work in progress is encouraged. The purpose
of the presentation-only papers is to allow researchers to communicate
good ideas that the attendees may not be aware of.

Related Resources

AAAI 2020   The Thirty-Fourth AAAI Conference on Artificial Intelligence
CCCG 2020   Canadian Conference on Computational Geometry
UNIF 2020   The 34th International Workshop on Unification
IJCAR 2020   10th International Joint Conference on Automated Reasoning
SIMULTECH 2020   10th International Conference on Simulation and Modeling Methodologies, Technologies and Applications
SIGLOG/VCLA/ILLC Awards for WiL 2020   SIGLOG, VCLA and ILLC Travel Awards for WiL 2020 (Women in Logic Workshop)
LPAR 2020   LPAR23 - 23rd International Conference on Logic for Programming, Artificial Intelligence and Reasoning
ASE 2020   International Conference on Automated Software Engineering
ICAPS 2020   The 30th International Conference on Automated Planning and Scheduling
ATVA 2020   18ᵗʰ International Symposium on Automated Technology for Verification and Analysis