K Lakshmanan Memorial Distinguished Lecture
Time: 2.00 pm Venue: Seminar Hall
An old problem on automata and first-order logic
Howard Straubing
Boston College USA.
08-03-23

---

Abstract

A 1960 technical report by Robert McNaughton, 'Symbolic Logic and Automata' was never published--at least not in its original form--and is seldom read. It has nonetheless exerted a large influence: It provided the impetus for decades of research on the links among automata, logic and algebra, exhibited a surprising connection with computational complexity, and raised a number of simple-sounding questions that are still open. Much of this talk is a broad historical survey, but I will also present some recent results on one of the open questions ('Difference hierarchies and duality with an application to formal languages', by Borlido, Gehrke, Krebs and Straubing; 'The regular languages of first-order logic with one alternation', by Barloy, Cadilhac, Paperman and Zeume).