LICS 2001 - Affiliated Workshops

Complexity, Logic, and Computation: A Symposium in Honor of Albert Meyer

Friday, June 15, 2001
John Riecke (

Full Completeness and Full Abstraction

Tuesday p.m. and Wednesday, June 19-20, 2001
Samson Abramsky ( and P. Scott (

Logic and Learning

Tuesday p.m. and Wednesday, June 19-20, 2001

Logic has been used as the underlying representation language in many areas of AI including machine learning. Learnability of logical expressions has been studied in many paradigms including PAC learning, query based learning, inductive inference, and inductive logic programming. There are theoretical results on learning in propositional logic as well as for logic programs, description logic, and fragments of first-order logic. The techniques applied are probabilistic and combinatorial, recursion theoretic, proof theoretic, and model theoretic.

The workshop aims to focus on such logic-based results and techniques for learning, fostering further understanding of the use of logic in learning. The workshop has a two-fold objective: to provide an introduction to the area for those who work in other LICS areas and are interested in applying logic to learning, and to provide a forum for research in the area of logic learning. The workshop will feature invited talks by experts in the field, and contributed talks presenting new research results. Confirmed invited speakers include: Arun Sharma (University of New South Wales), Leslie Valiant (Harvard University), and Stefan Wrobel (University of Magdeburg and GMD).

R. Khardon ( and G. Turan (

Satisfiability Testing: Theory and Applications

Thursday and Friday, June 14-15, 2001

Great strides have been made in recent years in the theory and practice of propositional satisfiability testing. On the theoretical side, a wide range of mathematical approaches -- ranging from classical combinatorial analysis to arguments based on statistical physics -- have increased our understanding of problem hardness. On the practical side, new systematic and non-systematic search algorithms have increased the size of problems that can be solved by several orders of magnitude. As a result there is an growing interest in using SAT as a practical tool for solving real-world problems, as well as using the insights gained from SAT research to create problem-specific solutions.

The purpose of this workshop is to bring together researchers from different communities -- including theory, artificial intelligence, verification, mathematical theorem-proving, and operations research -- in order to share ideas and increase synergy between theoretical and empirical work.

H. Kautz ( and B. Selman (

Back to the LICS web page.

Martin Grohe
Last modified: November 8, 2000