Opendata, web and dolomites


Duality in Formal Languages and Logic - a unifying approach to complexity and semantics

Total Cost €


EC-Contrib. €






 DuaLL project word cloud

Explore the words cloud of the DuaLL project. It provides you a very rough idea of what is the project "DuaLL" about.

area    classifying    co    view    boolean    incrementally    categorical    forth    classes    back    regularity    makkai    special    systematising    alphabets    functions    infinite    forms    subject    lower    logic    advancing    jonsson    finite    single    coumans    reiterman    active    mathematics    stone    semantics    science    canonical    ghilardi    theory    breakthroughs    operators    universal    finitely    duality    theoretic    structure    unifying    toggling    regular    extensions    logics    generalisations    dualities    monoids    presented    data    powerful    pervasive    bodirsky    first    authors    algebras    bear    proving    thereby    formal    theorem    forssell    spectrum    decidability    words    separation    systematise    tool    tools    heyting    search    circuit    languages    subjects    eilenberg    birkhoff    algebraic    trees    bounds    awodey    pinsker    assigns    complexity    profinite    structures    intermediate    algebra    tarski    theoretical    computer    obtaining    topological    varying    zawadowski    category    pi   

Project "DuaLL" data sheet

The following table provides information about the project.


Organization address
address: RUE MICHEL ANGE 3
city: PARIS
postcode: 75794

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country France [FR]
 Project website
 Total cost 2˙348˙938 €
 EC max contribution 2˙348˙938 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2014-ADG
 Funding Scheme ERC-ADG
 Starting year 2015
 Duration (year-month-day) from 2015-09-01   to  2021-08-31


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 


 Project objective

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 this important tool to bear on a number of subjects in theoretical computer science thereby advancing, systematising, 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 by the PI and her co-authors show that the theory may be seen as a special case of Stone duality for Boolean algebras with operators. We want 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. -Systematise and advance the search for robust generalisations 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, Ghilardi-Zawadowski duality for finitely presented Heyting algebras, and the Bodirsky-Pinsker topological Birkhoff theorem to Makkai's, Awodey and Forssell's, and Coumans' recent work on first-order logic duality, thus unifying topics in semantics and formal languages.

Our main tools come from Stone duality in various forms including the Jonsson-Tarski canonical extensions and profinite algebra, and from universal algebra and category theory.


year authors and title journal last update
List of publications.
2017 Jean-Éric Pin
Chapter 8: The Dot-Depth Hierarchy, 45 Years Later
published pages: 177-201, ISSN: , DOI: 10.1142/9789813148208_0008
The Role of Theory in Computer Science 2019-10-28
2017 Filippo Bonchi, Daniela PetriÅŸan, Damien Pous, Jurriaan Rot
A general account of coinduction up-to
published pages: 127-190, ISSN: 0001-5903, DOI: 10.1007/s00236-016-0271-4
Acta Informatica 54/2 2019-10-28
2017 Mai Gehrke, Daniela Petrisan, and Luca Reggio
Quantifiers on languages and codensity monads
published pages: , ISSN: , DOI:
Proceedings of the Thirty-Second Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2017) 2019-10-28
2017 Mai Gehrke, Andreas Krebs
Stone duality for languages and complexity
published pages: 28-53, ISSN: , DOI:
ACM SIGLOG News 4(2), April 2017 2019-10-28
2017 Célia Borlido
Some reducibility properties for pseudovarieties of the form DRH
published pages: 1813-1830, ISSN: 0092-7872, DOI: 10.1080/00927872.2017.1360328
Communications in Algebra 46/4 2019-10-28
2017 Jean-Éric Pin, Pedro V. Silva
On uniformly continuous functions for some profinite topologies
published pages: 246-262, ISSN: 0304-3975, DOI: 10.1016/j.tcs.2016.06.013
Theoretical Computer Science 658 2019-10-28
2017 Thomas Colcombet, Daniela Petrisan
Automata and minimization
published pages: 3-27, ISSN: , DOI:
ACM SIGLOG News 4(2), April 2017 2019-10-28
2017 Jorge Almeida, Zoltan Ésik, Jean-Éric Pin
Commutative positive varieties of languages
published pages: , ISSN: 0324-721X, DOI: 10.14232/actacyb.23.1.2017.7
Acta Cybernetica 23 2019-10-28
2018 Cabrer, Leonardo M.; Freisberg, Benjamin; Metcalfe, George; Priestley, Hilary A.
Checking Admissibility Using Natural Dualities
published pages: , ISSN: 0734-2071, DOI:
ACM Transactions of Computer Systems 1 2019-10-28
2016 Mai Gehrke
Stone duality, topological algebra, and recognition
published pages: 2711-2747, ISSN: 0022-4049, DOI: 10.1016/j.jpaa.2015.12.007
Journal of Pure and Applied Algebra 220/7 2019-10-28
2018 Branco , Mário; Pin , Jean-Eric
published pages: 156-168, ISSN: , DOI: 10.1007/978-3-319-98654-8_13
International Conference on Developments in Language Theory (DLT) LNCS, volume 11088 2019-10-28
2018 Bonchi, Filippo; König, Barbara; Petrisan, Daniela
Up-To Techniques for Behavioural Metrics via Fibrations
published pages: , ISSN: , DOI:
29th International Conference on Concurrency Theory (CONCUR 2018) 1 2019-10-28
2017 Colcombet, Thomas; PetriÅŸan, Daniela
Automata in the Category of Glued Vector Spaces
published pages: 52:1-14, ISSN: , DOI:
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) 1 2019-10-28
2017 Colcombet, Thomas; PetriÅŸan, Daniela
Automata Minimization: a Functorial Approach
published pages: , ISSN: , DOI:
7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017) 1 2019-10-28
2017 Célia Borlido, Silke Czarnetzki, Mai Gehrke, Andreas Krebs
Stone Duality and the Substitution Principle
published pages: , ISSN: , DOI: 10.4230/LIPIcs.CSL.2017.13
26th EACSL Annual Conference on Computer Science Logic (CSL 2017) 2019-10-28
2018 Mai Gehrke
Canonical extensions: an algebraic approach to Stone duality
published pages: , ISSN: 0002-5240, DOI: 10.1007/s00012-018-0544-6
Algebra universalis 79/3 2019-10-28
2017 Célia Borlido
The κ -word problem over DRH
published pages: 1-22, ISSN: 0304-3975, DOI: 10.1016/j.tcs.2017.08.008
Theoretical Computer Science 702 2019-10-28
2018 Carton, Olivier; Perrin, Dominique; Pin, Jean-Éric
A survey on difference hierarchies of regular languages
published pages: vol 14, ISSN: 1860-5974, DOI: 10.23638/LMCS-14(1:24)2018
Logical Methods in Computer Science 1 2019-10-28
2018 Samuel J. v. Gool, Luca Reggio
An open mapping theorem for finitely copresented Esakia spaces
published pages: 69-77, ISSN: 0166-8641, DOI: 10.1016/j.topol.2018.03.006
Topology and its Applications 240 2019-10-28
Newton series, coinductively: a comparative study of composition
published pages: 1-29, ISSN: 0960-1295, DOI: 10.1017/s0960129517000159
Mathematical Structures in Computer Science 2019-10-28
An Isbell duality theorem for type refinement systems
published pages: 736-774, ISSN: 0960-1295, DOI: 10.1017/s0960129517000068
Mathematical Structures in Computer Science 28/06 2019-10-28
2018 Mai Gehrke, Michael Pinsker
Uniform Birkhoff
published pages: 1242-1250, ISSN: 0022-4049, DOI: 10.1016/j.jpaa.2017.06.016
Journal of Pure and Applied Algebra 222/5 2019-10-28

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "DUALL" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email ( and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "DUALL" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.1.)

sociOlfa (2020)

Learning from social scents: from territory to identity

Read More  

SuperH (2019)

Discovery and Characterization of Hydrogen-Based High-Temperature Superconductors

Read More  


The Mass Politics of Disintegration

Read More