5 citations · 19 across the 10 of their papers we have counts for
5 papers · 1 filter
Complexity of correctness for pomset logic proof nets
Lê Thành Dũng Nguyên
We show that it is coNP-complete to decide whether a given proof structure of pomset logic is a correct proof net, using the graph-theoretic used in a previous paper of ours (arXiv…
Coherent Interaction Graphs
Lê Thành Dũng Nguyen, Thomas Seiller
We introduce the notion of coherent graphs, and show how those can be used to define dynamic semantics for Multiplicative Linear Logic (MLL) extended with non-determinism. Thanks t…
Around finite second-order coherence spaces
Lê Thành Dũng Nguyên
Many applications of denotational semantics, such as higher-order model checking or the complexity of normalization, rely on finite semantics for monomorphic type systems. We exhib…
Unique perfect matchings, forbidden transitions and proof nets for linear logic with Mix
Lê Thành Dũng Nguyên
This paper establishes a bridge between linear logic and mainstream graph theory, building on previous work by Retoré (2003). We show that the problem of correctness for MLL+Mix pr…
Constrained path-finding and structure from acyclicity
Lê Thành Dũng Nguyên
This note presents several results in graph theory inspired by the author's work in the proof theory of linear logic; these results are purely combinatorial and do not involve logi…