DuaLL SIGNED
Duality in Formal Languages and Logic - a unifying approach to complexity and semantics
Total Cost €
0EC-Contrib. €
0Partnership
0Views
0DuaLL 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.
Project "DuaLL" data sheet
The following table provides information about the project.
| Coordinator |
CENTRE NATIONAL DE LA RECHERCHE SCIENTIFIQUE CNRS
Organization address contact info |
| Coordinator Country | France [FR] |
| Project website | https://math.unice.fr/ |
| 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 |
Partnership
Take a look of project's partnership.
| # | ||||
|---|---|---|---|---|
| 1 | CENTRE NATIONAL DE LA RECHERCHE SCIENTIFIQUE CNRS | FR (PARIS) | coordinator | 2˙348˙938.00 |
Map
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.
Publications
| year | authors and title | journal | last update |
|---|---|---|---|
| 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 INEQUALITIES FOR ONE-STEP PRODUCTS 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 |
| 2017 |
HENNING BASOLD, HELLE HVID HANSEN, JEAN-ÉRIC PIN, JAN RUTTEN 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 |
| 2018 |
PAUL-ANDRÉ MELLIÈS, NOAM ZEILBERGER 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 (fabio@fabiodisconzi.com) 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.