Opendata, web and dolomites


A Realizability Approach to Complexity Theory

Total Cost €


EC-Contrib. €






Project "ReACT" data sheet

The following table provides information about the project.


Organization address
address: NORREGADE 10
postcode: 1165

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 Denmark [DK]
 Project website
 Total cost 212˙194 €
 EC max contribution 212˙194 € (100%)
 Programme 1. H2020-EU.1.3.2. (Nurturing excellence by means of cross-border and cross-sector mobility)
 Code Call H2020-MSCA-IF-2014
 Funding Scheme MSCA-IF-EF-ST
 Starting year 2015
 Duration (year-month-day) from 2015-11-01   to  2017-10-31


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    KOBENHAVNS UNIVERSITET DK (KOBENHAVN) coordinator 212˙194.00


 Project objective

'Complexity theory concerns fundamental questions on the mathematics of computer science about the amount of resources needed to run programs or solve problems. The ReACT project will build on recent work in realizability models for linear logic to provide new characterizations of existing complexity classes. The end goal is to enable researchers to attack long-standing open problems in complexity theory by using mathematical techniques, tools and invariants from operators algebras and dynamical systems. The 'complexity-through-realizability' techniques developed by the ReACT project will provide a unified framework for studying many computational paradigms and their associated computational complexity theory grounded on well-studied mathematical concepts. This will allow for comparison of complexity classes defined from different computational paradigms (e.g. sequential and quantum computation), as well as establish a theory of complexity for computational paradigms lacking such (e.g. concurrent processes). The 'complexity-through-realizability' approach stems from established logical-based approaches of complexity theory and inherits their strengths. It furthermore improves crucially over them as it builds upon state-of-the-art theoretical results on realizability models for linear logic using well-studied mathematical concepts from operators algebras and dynamical systems. As a consequence, it opens the way to the use against the open problems of the discipline the many techniques, tools and invariants that were developed in these mathematical disciplines. The ReACT project has two objectives. The first objective aims at establishing this new approach to complexity as an emerging and promising field of study which generalizes and extends previous techniques. The second objective is to investigate investigating how the mathematical methods and techniques derived from of our approach can be used to attack long-standing open problems in complexity theory.'


year authors and title journal last update
List of publications.
2018 Seiller, Thomas
Interaction Graphs: Non-deterministic automata
published pages: , ISSN: , DOI:
ACM Transactions in Computational Logic 2019-06-18
2017 Jean-Yves Moyen, Thomas Rubiano, Thomas Seiller
Loop Quasi-Invariant Chunk Motion by peeling with statement composition
published pages: 47-59, ISSN: 2075-2180, DOI: 10.4204/EPTCS.248.9
Electronic Proceedings in Theoretical Computer Science 248 2019-06-18
2015 Seiller, Thomas
Towards a Complexity-through-Realisability Theory
published pages: , ISSN: , DOI:
2016 Clément Aubert, Marc Bagnol, Thomas Seiller
Unary Resolution: Characterizing Ptime
published pages: 373-389, ISSN: , DOI: 10.1007/978-3-662-49630-5_22
Foundations of Software Science and Computation Structures. FoSSaCS 2016. Lecture Notes in Computer Science, vol 9634 2019-06-18
2016 Seiller, Thomas
From Dynamic to Static Semantics, Quantitatively
published pages: , ISSN: , DOI:
2017 Jean-Yves Moyen, Thomas Rubiano, Thomas Seiller
Loop Quasi-Invariant Chunk Detection
published pages: 91-108, ISSN: , DOI: 10.1007/978-3-319-68167-2_7
Automated Technology for Verification and Analysis. ATVA 2017. Lecture Notes in Computer Science, vol 10482 2019-06-18

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "REACT" 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 "REACT" are provided by the European Opendata Portal: CORDIS opendata.

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

MathematicsAnalogies (2019)

Mathematics Analogies

Read More  

DEMOS (2019)

Disfluencies and Eye MOvements during Speech: what can they reveal about language production?

Read More  

DiMaS (2019)

Retrospective genomic analyses of shortfin Mako shark (Isurus oxyrinchus) using DNA from archived jaws

Read More