DuaLL. -- ERC Advanced project running 2015-2021.

 

There is currently an opening for a postdoc position to start in early 2020. The successful candidate will contribute to the development of an Eilenberg-Reiterman theory beyond regular languages with the goal of obtaining new tools and separation results for Boolean circuit classes. This is an interdisciplinary project primarily combining profinite tools from the algebraic theory of regular languages and Stone/Priestley duality for lattices with additional operations. Candidates must hold a PhD in theoretical computer science or mathematics by the start date. Preference will be given to candidates with prior work in the algebraic theory of regular languages, Stone/Priestley duality, and/or descriptive complexity for low-level complexity classes.

 

Applications should include: a letter of interest, a CV, and contact information of two references (Title, Name, organization, e-mail).
Interested candidates should send their application to mgehrke@unice.fr

 

Please contact Mai Gehrke for more information.

 

 

Duality in Formal Languages and Logic – a unifying approach to complexity and semantics

 

Dualities between algebraic and topological structure are pervasive in mathematics, and toggling back and forth between them has often been associated with important breakthroughs. The main objective of this project is to bring such topo-algebraic dualities to bear on a number of subjects in theoretical computer science thereby advancing, systematizing, and unifying them.

 

One subject of focus is the search for robust extensions of the theory of regular languages. A powerful technical tool for classifying regular languages and proving decidability results is Eilenberg-Reiterman theory, which assigns classes of finite monoids or single profinite algebras to classes of languages. Recent results show that the theory may be seen as a special case of Stone duality for Boolean algebras with operators. The purpose of the project is to:

 

-       Develop an Eilenberg-Reiterman theory beyond regular languages with the goal of obtaining new tools and separation results for Boolean circuit classes, an active area in the search for lower bounds in complexity theory.

 

-       Systematize and advance the search for robust generalizations of regularity to other structures such as infinite words, finite and infinite trees, cost functions, and words with data.

 

The second subject of focus is the development of duality theoretic methods for logics with categorical semantics. We want to approach the problem incrementally:

 

-       View duality for categorical semantics through a spectrum of intermediate cases going from regular languages over varying alphabets and duality for finitely presented Heyting algebras through to recent work on first-order logic duality, thus unifying topics in semantics and formal languages.

 

 

We run a seminar. Please visit its webpage for more information.

 

Sponsored events:

 

TACL conference, 17-21 June 2019 in Nice, and school, 10-15 June 2019 on Ile de Porquerolles

Quantifiers and Duality, 11 September 2018, IRIF, Université Paris Diderot

Journées Niçoises: Logique catégorique , topos, et dualités, 8-12 janvier 2018

 

 

 

 (Project  members)

Thomas Colcombet

Paul-André Melliès

Frederic Patras

Jean-Éric Pin

Carlos Simpson

Sam van Gool

Daniela Petrisan

 

Tomáš Jakl

Wesley Fussner

Brett McLean

 

Axel Osmond

Mehdi Zaïdi

 

(Former Project  members)

Leo Cabrer

Sebastian Schöner

Camell Kachour

Pierre Cagne

Luca Reggio

Célia Borlido

 

 

 

 (Collaborators)

Matthias Baaz

Clemens Berger

Andreas Krebs

Howard Straubing

Marek Zawadowski

 

 

Related literature:

 

M. Gehrke. Stone duality, topological algebra, and recognition. arXiv:1309.2422, 2013.

M. Gehrke, A. Krebs, and J.-E. Pin. Ultrafilters on words for a fragment of logic. To appear in TCS.

M. Gehrke, S. Grigorieff, and J.-E. Pin. A topological approach to recognition. In ICALP’10, 151-162,

2010.

M. Gehrke, S. Grigorieff, and J.-E. Pin. Duality and equational theory of regular languages. In ICALP’08, 246-257, 2008.

 

J.-E. Pin. Profinite methods in automata theory. In STACS’09, 31-50, 2009.

H. Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser, 1994.

P. Weil. Profinite methods in semigroup theory. Int. J. Alg. Comput., 12:137-178, 2002.

 

S. Ghilardi and M. Zawadowski. Sheaves, games, and model completions. Trends in Logic. Kluwer, 2002.

M. Makkai. Duality and definability in first order logic. American Mathematical Society, 1993

S. Awodey and H. Forssell. First-order logical duality. APAL, 164(3):319-348, 2013.

D. Coumans. Generalising canonical extension to the categorical setting. APAL, 163:1940-61, 2012.