New ERC-advanced project starting September 2015 at LIAFA/PPS (soon to be the Institut de Recherche en Informatique Fondamentale (IRIF)), CNRS and Université Paris Diderot, Paris 7.
PhD and postdoc positions available. Please contact 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.
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,
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.