Seminars

Title:The Regular Languages of First-Order Logic with One Alternation
Abstract: The regular languages with a neutral letter expressible in first-order logic with one alternation are characterized. Specifically, it is shown that if an arbitrary Σ2 formula defines a regular language with a neutral letter, then there is an equivalent Σ2 formula that only uses the order predicate. This shows that the so-called Central Conjecture of Straubing holds for Σ2 over languages with a neutral letter, the first progress on the Conjecture in more than 20 years. To show the characterization, lower bounds against polynomial-size depth-3 Boolean circuits with constant top fan-in are developed. The heart of the combinatorial argument resides in studying how positions within a language are determined from one another, a technique of independent interest.

Title:
Separator logic, expressive power and algorithmic applications
Abstract:
First-order logic (FO) can express many algorithmic problems on graphs,
but fails to express whether two vertices are connected. We define a
new logic (separator logic) by enriching FO with connectivity
predicates connk(x, y, z1, . . . , zk) that hold true in a graph if
there exists a path between x and y after deletion of z1, . . . , zk.
In this talk I will first present a study of the expressive power of
this new logic.
I will then present algorithmic results for this logic on graph classes
that exclude a topological minor.
These results were obtained in collaboration with Michał Pilipczuk,
Nicole Schirrmacher, Sebastian Siebertz, and Szymon Toruńczyk.