ERC Advanced project running 2015-2020.
There is currently an opening for a postdoc position to start in Fall 2018. 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.
The position will remain open until 30 April 2018, and the successful candidate will start in Fall 2018. The position is for 1 year, renewable for a second year.
Interested candidates should send a vita and a letter of interest.
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.
(Former Project members)
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.