The FAMT workshop will begin with three hours of introductory lectures by R. Ramanujam, Abhisekh Sankaran and Supratik Chakraborty. Subsequently, there will be four 1-hour talks by Anuj Dawar, Phokion Kolaitis, Emanuel Kieroński and Dietmar Berwanger on the first day (Dec 10, 2011). These talks are intended to introduce the audience gently to ideas and concepts useful for understanding more advanced topics to be covered on the second day (Dec 11, 2011). The second day of the workshop (Dec 11, 2011) will start with a 2-hour talk by Benjamin Rossman. This will be followed by three 1.5-hour talks and one 1-hour talk on advanced topics by Anuj Dawar, Emanuel Kieroński, Phokion Kolaitis and Dietmar Berwanger.

Sketches of talks by individual speakers is given below. The topics/abstracts listed are for both parts of a talk, whenever a talk is split into two parts. Please note that the topics are tentative, and there may be some last-minute modifications.

• Supratik Chakraborty: Introductory lecture 1
  • Undecidability of first-order (FO) logic, and of finite satisfiability in particular (Trakhtenbrot's theorem).
• Abhisekh Sankaran: Introductory lecture 2
  • Quantifier ranks, Ehrenfeucht-Fraïssé (EF) games, and applications for FO-inexpressibility
• R. Ramanujam: Introductory lecture 3
  • FO model checking
  • Fagin's theorem, Second Order-Horn, P and FO(lfp)
• Emanuel Kieroński: Decidability and Complexity Issues for Two-Variable Logics
  The talk will start from the finite model theorem for two-variable fragment of first-order logic. Then some related topics will be discussed, including the decidability and the complexity of the finite satisfiability problem for the two-variable guarded fragment with equivalence guards. Techniques like tree-like unravellings and integer programming will be presented.
• Anuj Dawar: Descriptive Complexity and Polynomial Time
  A central open question in the field of finite model theory, first posed by Chandra and Harel in 1982, asks whether there exists a logic that expresses exactly the polynomial-time computable properties of finite structures in the same way that Fagin had proved that existential second-order logic captures NP. In this tutorial, I will give a history of the problem and cover some highlights of results that have been obtained over the years. In particular, I will examine the logic formed by adding fixed-point and counting constructs to first-order logic (FPC). This captures PTIME on many interesting classes of finite structures, but not the class of all finite structures. I will look at recent results examining the descriptive complexity of problems from linear algebra which form a new frontier in the search for a logic for P.
• Phokion Kolaitis: Logic and Databases
  The aim of this presentation is to give an overview of the interaction between logic, databases, and computational complexity. Topics to be covered include: relational algebra and first-order logic as database query languages; homomorphisms, conjunctive queries, and Datalog; logic-based languages for specifying data interoperability tasks; foundations of data exchange and data integration.
• Benjamin Rossman: Logic and Random Structures
  • FO Logic: Differences between classical and finite model theory
  • EF games building up to a proof that order-invariant FO is more expressive than FO
  • Logic and Random Structures: A quick tour of some 0-1 laws, and some recent results in complexity theory from a logic perspective
• Dietmar Berwanger: Automata for Guarded Fixed-Point Logics
  Guarded fixed-point logics extend the guarded fragments of first-order logic by adding least fixed-point constructs, in the same way as the mu-calculus extends basic modal logic. These fixed-point extensions are highly expressive and, still, they preserve most of the good model-theoretic properties of the first-order kernel. This talk is about one fundamental tool for solving decidability questions for fixed-point logics: we introduce two-way alternating automata and show how they yield a decidability procedure for guarded-fixed point logics and how they are used to solve the finite satisfiability problem. If time allows, we will discuss applications of different variants of guarded fixed-point logics to database query languages.

Venue:

Workshop Schedule