ERC Advanced project running
20152020.
There is currently an opening for a postdoc position
to start in Fall 2018. The successful candidate will contribute to the
development of an EilenbergReiterman 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 lowlevel 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 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 topoalgebraic 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 EilenbergReiterman 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 EilenbergReiterman 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 firstorder logic duality, thus unifying topics in semantics and formal
languages.
(Project
members)
(Former Project
members)
(Collaborators)
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, 151162,
2010.
M. Gehrke, S. Grigorieff, and J.E. Pin. Duality and
equational theory of regular languages. In ICALP’08, 246257, 2008.
J.E. Pin. Profinite methods in automata theory. In STACS’09, 3150, 2009.
H. Straubing. Finite Automata,
Formal Logic, and Circuit Complexity. Birkhauser, 1994.
P. Weil. Profinite methods in semigroup theory. Int. J. Alg. Comput., 12:137178, 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. Firstorder logical duality. APAL, 164(3):319348, 2013.
D. Coumans. Generalising canonical extension to the categorical setting.
APAL, 163:194061, 2012.