Logic and Games

Soumya Paul, from the Institute of Mathematical Sciences, Chennai recently gave a talk titled “Logic and Games” at the Department of Mathematical Sciences, Tezpur University. The abstract of the talk is given below:

The connection between logic and two player zero sum games is well known. They can be seen as two sides of the same coin. In this elementary talk, we  look at how the model checking problem of first order logic can be viewed as a game between two players, the verifier and the falsifier, on a graph. In particular, we prove the strategy theorem which says that a first order sentence `s’ is satisfiable on a structure `A’ if and only if the verifier has a winning strategy in the corresponding game on a graph `G(s,A)’ obtained from the sentence ‘s’ and the structure `A’. We then look at the extension of this concept to other logics like modal logic, IF logic, mu calculus etc.

The slides of the talk can be downloaded here.

Soumya Paul passed his school leaving certificate examination from Don Bosco School, Tezpur securing a rank in the top 20 positions. He then completed his Higher Secondary from Cotton College, Guwahati securing the first position in Assam. He joined BITS, Pilani from where he got a B.E. in Computer Science and Engineering. After his Bachelors he joined the Institute of Mathematical Sciences, Chennai for his MSc and then his PhD in Theoretical Computer Science. He will be leaving for the Netherlands after Christmas for a 2 year post doctoral fellowship. His webpage can be found here.