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)
(Former Project members)
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.