Seminal
The magazine and atlas of EU-funded researchA new publication from the web and AI team at Scott Charnley

Atlas / Germany

European Research Council grant · Running

FINABIS Finite-state abstractions of infinite-state systems

Coordinator
Max-Planck-Gesellschaft Zur Forderung Der Wissenschaften eV, Germany
Runs
1 January 2023 to 31 December 2027
Status
Running
EU funding
€1.5m
Total cost
€1.5m
Partners
1 organisations in 1 countries
Type
European Research Council grant
Grant agreement
101077902

What the project is doing

In the project's own words, from its summary on CORDIS.

The algorithmic analysis of infinite-state systems is a central topicof theoretical computer science that is part of a popular approach tosoftware verification. While analyzing infinite-state systems isindispensable when verifying software, finite-state sytems are farbetter understood and permit much more efficient analysis. In thisproject, I will pursue fundamental questions that arise when we wantto abstract infinite-state systems by finite-state systems.

The goalis to understand two types of problems:1. Separability problems: Given two infinite-state systems, can we find a finite-state overapproximation of the first system whose behaviors are disjoint from those of the second system? Separability is a basic task for synthesizing certificates for disjointness and therefore safety properties in concurrent systems.2. Closure computation. There are several non-constructive results that guarantee the existence of finite-state overapproximations of infinite-state systems that preserve some particular information.

We are interested in how to compute these overapproximations effectively and efficiently. Examples include downward closures and upward closures with respect to the (scattered) subword ordering. Efficient procedures for closure computation would have immediate implications for infinite-state verification tasks that combine recursion with concurrency. In addition to directly attacking well-known deep open problemsregarding these fundamental questions, the project will also developmethods that will likely be crucial for resolving further major openproblems in infinite-state systems.

Moreover, the obtained resultswould have immediate implications for software verification insettings that combine recursion with concurrency, which is anotoriously difficult task.

Topics

Who is involved

OrganisationCityCountryRole
Max-Planck-Gesellschaft Zur Forderung Der Wissenschaften eVMunchenGermanyCoordinator

Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI