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