Revisiting concatenation hierarchies of regular languages

Marc Zeitoun
LaBRI CS Lab, Bordeaux University
Friday, 5 May, 2017 - 13:15
Forum C

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.