
The FAMT workshop will begin with three hours of introductory lectures
by R. Ramanujam, Abhisekh Sankaran and Supratik Chakraborty.
Subsequently, there will be four 1hour 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 2hour
talk by Benjamin Rossman. This will be followed by three 1.5hour
talks and one 1hour 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 lastminute modifications.
 Supratik Chakraborty: Introductory lecture 1
 Undecidability of firstorder (FO) logic, and of finite
satisfiability in particular (Trakhtenbrot's theorem).
 Abhisekh Sankaran: Introductory lecture 2
 Quantifier ranks, EhrenfeuchtFraïssé (EF) games,
and applications for FOinexpressibility
 R. Ramanujam: Introductory lecture 3
 FO model checking
 Fagin's theorem, Second OrderHorn, P and FO(lfp)
 Emanuel Kieroński: Decidability and Complexity Issues for TwoVariable Logics
The talk will start from the finite model theorem for twovariable fragment of
firstorder logic. Then some related topics will be discussed, including
the decidability and the complexity of the finite satisfiability problem for the
twovariable guarded fragment with equivalence guards. Techniques like
treelike 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 polynomialtime computable properties of finite structures in the
same way that Fagin had proved that existential secondorder 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 fixedpoint and counting constructs
to firstorder 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
firstorder logic as database query languages; homomorphisms,
conjunctive queries, and Datalog; logicbased 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 orderinvariant FO is more
expressive than FO
 Logic and Random Structures: A quick tour of some 01 laws, and
some recent results in complexity theory from a logic perspective
 Dietmar Berwanger: Automata for Guarded FixedPoint
Logics
Guarded fixedpoint logics extend the guarded fragments of
firstorder logic by adding least fixedpoint constructs, in the same
way as the mucalculus extends basic modal logic. These fixedpoint
extensions are highly expressive and, still, they preserve most of the
good modeltheoretic properties of the firstorder kernel. This talk
is about one fundamental tool for solving decidability questions for
fixedpoint logics: we introduce twoway alternating automata and show
how they yield a decidability procedure for guardedfixed 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
fixedpoint logics to database query languages.
Venue:
All talks of the workshop will be in auditorium LCH
11 on the first floor of Lecture Hall Complex opposite KReSIT Building
(see map). Tea/coffee breaks
will be in LCH 11 foyer outside the auditorium (first floor). Lunch
will be served in the student lounge area on the ground floor of
Lecture Hall Complex.
Workshop Schedule
Saturday,
December 10, 2011

8:00  8:55

Registration [Lecture Hall Complex entrance]

8:55  9:00

Welcome

9:00  9:30

Supratik Chakraborty: Introductory talk 1

9:30  10:30

Abhisekh Sankaran: Introductory talk 2

10:30  11:00

Tea/coffee break [LCH 11 foyer]

11:00  12:30

R. Ramanujam: Introductory talk 3

12:30  13:30

Lunch break [Lecture Hall Complex ground floor: student lounge area]

13:30  14:30

Anuj Dawar: Talk 1

14:30  15:30

Phokion Kolaitis: Talk 1

15:30  16:00

Tea/coffee break [LCH 11 foyer]

16:00  17:00

Emanuel Kieroński: Talk 1

17:00  17:15

Cookies/munchies break [LCH 11 foyer]

17:15  18:15

Dietmar Berwanger: Talk 1


Sunday,
December 11, 2011

9:00  10:30

Benjam Rossman's talk

10:30  11:00

Tea/coffee break [LCH 11 foyer]

11:00  12:30

Anuj Dawar: Talk 2

12:30  13:30

Lunch break [Lecture Hall Complex ground floor: student lounge area]

13:30  15:00

Emanuel Kieroński: Talk 2

15:00  15:30

Tea/coffee break [LCH 11 foyer]

15:30  17:00

Phokion Kolaitis: Talk 2

17:00  17:15

Cookies/munchies break [LCH 11 foyer]

17:15  18:15

Dietmar Berwanger: Talk 2

