Revisiting concatenation hierarchies of regular languages

Room FC1.004, DMat-FCUP at 15:30
Friday, 19 May, 2017

This talk addresses the following question: which languages can we define over a finite alphabet, starting from the class consisting of the empty set only, and alternating two operations a prescribed number of times: (1) Boolean closure and (2) polynomial closure? This basic problem, strongly related to logical definability in first-order logic, is wide open since the early 70s. I will introduce a strengthening of this question, and argue that this harder problem is actually easier to deal with than the original one.


Marc Zeitoun


Bordeaux University

PDF File: