# Revisiting concatenation hierarchies of regular languages

Submitted by sleroux on Tue, 17/01/2017 - 12:21
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

LaBRI CS Lab, Bordeaux University

Friday, 5 May, 2017 - 13:15

Forum C