Title: Relating logic to formal languages

Speaker: Prof. Kamal Lodaya (IMSc, https://www.imsc.res.in/~kamal/)

Date: Oct. 16th 15:10-18:00

Room: 二教519 (Teaching Building 2,519)

Abstract:   Since the 1960s, logic has been related to formal language theory. Fixing words, trees, graphs or posets as models, definable sets can be seen as word, tree, graph or poset languages. McNaughton (1960) first asked the question what the first-order definable sets were. The answers connected logic to the theory of finite automata. A lot is known about logic over word models. Less is known about tree models. For graph models, Courcelle and Seese (1990) developed a model-theoretic technique to interpret classes of graphs into trees. This talk is an introduction to this area.

About the speaker: Kamal Lodaya is a professor at the Institute of Mathematical Sciences in Chennai. He obtained his Ph.D. in computer science from the Tata Institute of fundamental research in Mumbai. His interests include in the theory of automata, concurrency, Petritri nets, and logic. He was the president of the Association of Logic in India (2011-2015).