Invited Talk by Dr. Sreejith A. V. on Applications of Regular quantifiers in Logics

Invited Talk by Dr. Sreejith A. V. on Applications of Regular quantifiers in Logics

Title: Applications of Regular quantifiers in Logics
Speaker: Dr. Sreejith A. V.
Host Faculty: Dr. Saurabh Joshi
Room No: 118 (A-block)
Time: 10:00 AM

Abstract:
In this talk, we look at various extensions of linear temporal logic (LTL) and first order logic (FO). Of particular interest are extensions using modulo counting operators.

First, we give a very brief introduction to logic and automata giving special attention to linear temporal logic. LTL has found tremendous use in program verification. It though has some limitations. One such limitation is, it cannot express periodic properties. For example, ``the bell rings every 1 hour”. We introduce the modulo counting operator which address this weakness of LTL and the satisfiability and model checking problem.

In the second part of the talk, we address an open problem in Descriptive complexity which was posed by Howard Straubing. The modulo counting extensions of first order logic (using addition relation) are closely related to Circuit complexity. It was not known whether there are regular languages which are not definable in this modulo counting extension of first order logic. We use a combination of combinatorics and semigroup theory to show that there are regular languages not definable in this logic, thereby answering Straubing.

Speaker’s Bio:

Dr. Sreejith is currently an assistant professor in university of Warsaw. He received his PhD from Institute of mathematical sciences, Chennai. Hiswork with Prof. Kamal Lodaya got the ACM India, best thesis (honorary) award in 2014.

He is interested in theoretical computer science with special interest in logic, automata theory and it’s applications.
Dates:
Wednesday, February 8, 2017 - 10:00