research
∙
07/31/2023
Syntactically and semantically regular languages of lambda-terms coincide through logical relations
A fundamental theme in automata theory is regular languages of words and...
share
research
∙
05/21/2023
Simply typed convertibility is TOWER-complete even for safe lambda-terms
We consider the following decision problem: given two simply typed λ-ter...
research
∙
01/23/2023
Revisiting the growth of polyregular functions: output languages, weighted automata and unary inputs
Polyregular functions are the class of string-to-string functions defina...
research
∙
08/03/2020
Implicit automata in typed λ-calculi II: streaming transducers vs categorical semantics
We characterize regular string transductions as programs in a linear λ-c...
research
∙
12/23/2019
Complexity of correctness for pomset logic proof nets
We show that it is coNP-complete to decide whether a given proof structu...
research
∙
12/23/2019
Proof nets through the lens of graph theory: a compilation of remarks
This document is intended to eventually gather a few small remarks on th...
research
∙
09/08/2019
When lattice cubes meet affine subspaces: a short note
We give short and simple proofs of what seem to be folklore results: * t...
research
∙
08/14/2019
On the Elementary Affine Lambda-Calculus with and Without Fixed Points
The elementary affine lambda-calculus was introduced as a polyvalent set...
research
∙
06/30/2019
Typed lambda-calculi and superclasses of regular functions
We propose to use Church encodings in typed lambda-calculi as the basis ...
research
∙
04/15/2019
Coherent Interaction Graphs
We introduce the notion of coherent graphs, and show how those can be us...
research
∙
02/01/2019
Around finite second-order coherence spaces
Many applications of denotational semantics, such as higher-order model ...
research
∙
02/01/2019
Finite semantics of polymorphism, complexity and the power of type fixpoints
Many applications of denotational semantics, such as higher-order model ...
research
∙
01/29/2019
Unique perfect matchings, edge-colored graphs and proof nets for linear logic with Mix
This paper establishes a bridge between linear logic and mainstream grap...
research
∙
01/21/2019