Damien Pous
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Damien Pous has a total of 53 co-authors. Here are the top co-authors by number of shared publications:
Daniel Hirschkoff
ENS Lyon, Université de Lyon, CNRS, INRIA
7 shared publicationsFilippo Bonchi
CNRS, Plume team, LIP (UMR 5668, ENS de Lyon, UCBL, Université de Lyon), 46 Allée d'Italie, 69364 Lyon, France
5 shared publications- Paul Brunet
University College London
4 shared publications Burak Ekici
3 shared publicationsDavide Sangiorgi
Università di Bologna, INRIA
3 shared publicationsDominique Duval
3 shared publications
Latest Publications
- Open Access
- 8 January 2026
- Published by Association for Computing Machinery (ACM)
- p. 59-74
Adhesive Category Theory for Graph Rewriting in Rocq
- 8 January 2026
- Published by Association for Computing Machinery (ACM)
- p. 59-74
Open AccessAdhesive Category Theory for Graph Rewriting in Rocq
- Open Access
- 27 June 2025
- Published by Springer Nature in Applied Categorical Structures
- Vol. 33 (4) , 1-67
Higher Catoids, Higher Quantales and their Correspondences
We introduce $$\omega $$ -catoids as generalisations of (strict) $$\omega $$ -categories and in particular the higher path categories generated by computads or polygraphs in higher-dimensional rewriting. We also introduce $$\omega $$ -quantales that generalise the $$\omega $$ -Kleene algebras recently proposed for algebraic coherence proofs in higher-dimensional rewriting. We then establish correspondences between $$\omega $$ -catoids and convolution $$\omega $$ -quantales. These are related to Jónsson-Tarski-style dualisms between relational structures and lattices with operators. We extend these correspondences to $$(\omega,p)$$ -catoids, catoids with a groupoid structure above some dimension, and convolution $$(\omega,p)$$ -quantales, using Dedekind quantales above some dimension to capture homotopic constructions and proofs in higher-dimensional rewriting. We also specialise them to finitely decomposable $$(\omega, p)$$ -catoids, an appropriate setting for defining $$(\omega, p)$$ -semirings and $$(\omega, p)$$ -Kleene algebras. These constructions support the systematic development and justification of $$\omega $$ -Kleene algebra and $$\omega $$ -quantale axioms, improving on the recent approach mentioned, where axioms for $$\omega $$ -Kleene algebras have been introduced in an ad hoc fashion.- 27 June 2025
- Published by Springer Nature in Applied Categorical Structures
- Vol. 33 (4) , 1-67
Open AccessHigher Catoids, Higher Quantales and their Correspondences
We introduce $$\omega $$ -catoids as generalisations of (strict) $$\omega $$ -categories and in particular the higher path categories generated by computads or polygraphs in higher-dimensional rewriting. We also introduce $$\omega $$ -quantales that generalise the $$\omega $$ -Kleene algebras recently proposed for algebraic coherence proofs in higher-dimensional rewriting. We then establish correspondences between $$\omega $$ -catoids and convolution $$\omega $$ -quantales. These are related to Jónsson-Tarski-style dualisms between relational structures and lattices with operators. We extend these correspondences to $$(\omega,p)$$ -catoids, catoids with a groupoid structure above some dimension, and convolution $$(\omega,p)$$ -quantales, using Dedekind quantales above some dimension to capture homotopic constructions and proofs in higher-dimensional rewriting. We also specialise them to finitely decomposable $$(\omega, p)$$ -catoids, an appropriate setting for defining $$(\omega, p)$$ -semirings and $$(\omega, p)$$ -Kleene algebras. These constructions support the systematic development and justification of $$\omega $$ -Kleene algebra and $$\omega $$ -quantale axioms, improving on the recent approach mentioned, where axioms for $$\omega $$ -Kleene algebras have been introduced in an ad hoc fashion. - Open Access
On the Two Paths Theorem and the Two Disjoint Paths Problem
A tuple (s1,t1,s2,t2) of vertices in a simple undirected graph is 2-linked when there are two vertex-disjoint paths respectively from s1 to t1 and s2 to t2. A graph is 2-linked when all such tuples are 2-linked. We give a new and simple proof of the ``two paths theorem'', a characterisation of edge-maximal graphs which are not 2-linked as webs: particular near triangulations filled with cliques. Our proof works by generalising the theorem, replacing the four vertices above by an arbitrary tuple; it does not require major theorems such as Kuratowski's or Menger's theorems. Instead it follows an inductive characterisation of generalised webs via parallel composition, a graph operation consisting in taking a disjoint union before identifying some pairs of vertices. We use the insights provided by this proof to design a simple O(nm) recursive algorithm for the ``two vertex-disjoint paths'' problem. This algorithm is constructive in that it returns either two disjoint paths, or an embedding of the input graph into a web.
Open AccessOn the Two Paths Theorem and the Two Disjoint Paths Problem
A tuple (s1,t1,s2,t2) of vertices in a simple undirected graph is 2-linked when there are two vertex-disjoint paths respectively from s1 to t1 and s2 to t2. A graph is 2-linked when all such tuples are 2-linked. We give a new and simple proof of the ``two paths theorem'', a characterisation of edge-maximal graphs which are not 2-linked as webs: particular near triangulations filled with cliques. Our proof works by generalising the theorem, replacing the four vertices above by an arbitrary tuple; it does not require major theorems such as Kuratowski's or Menger's theorems. Instead it follows an inductive characterisation of generalised webs via parallel composition, a graph operation consisting in taking a disjoint union before identifying some pairs of vertices. We use the insights provided by this proof to design a simple O(nm) recursive algorithm for the ``two vertex-disjoint paths'' problem. This algorithm is constructive in that it returns either two disjoint paths, or an embedding of the input graph into a web.
- Open Access
- 30 September 2024
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 20, Is (3) , 1-27
Completeness Theorems for Kleene algebra with tests and top
We prove two completeness results for Kleene algebra with tests and a top element, with respect to guarded string languages and binary relations. While the equational theories of those two classes of models coincide over the signature of Kleene algebra, this is no longer the case when we consider an additional constant ``top'' for the full element. Indeed, the full relation satisfies more laws than the full language, and we show that those additional laws can all be derived from a single additional axiom. We recover that the two equational theories coincide if we slightly generalise the notion of relational model, allowing sub-algebras of relations where top is a greatest element but not necessarily the full relation. We use models of closed languages and reductions in order to prove our completeness results, which are relative to any axiomatisation of the algebra of regular events. For one of our constructions, we extend the concept of finite monoid recognisability to guarded-string languages; this device makes it possible to obtain a PSpace algorithm for the equational theory of binary relations.
- 30 September 2024
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 20, Is (3) , 1-27
Open AccessCompleteness Theorems for Kleene algebra with tests and top
We prove two completeness results for Kleene algebra with tests and a top element, with respect to guarded string languages and binary relations. While the equational theories of those two classes of models coincide over the signature of Kleene algebra, this is no longer the case when we consider an additional constant ``top'' for the full element. Indeed, the full relation satisfies more laws than the full language, and we show that those additional laws can all be derived from a single additional axiom. We recover that the two equational theories coincide if we slightly generalise the notion of relational model, allowing sub-algebras of relations where top is a greatest element but not necessarily the full relation. We use models of closed languages and reductions in order to prove our completeness results, which are relative to any axiomatisation of the algebra of regular events. For one of our constructions, we extend the concept of finite monoid recognisability to guarded-string languages; this device makes it possible to obtain a PSpace algorithm for the equational theory of binary relations.
- Open Access
- 16 May 2024
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 20, Is (2)
On Tools for Completeness of Kleene Algebra with Hypotheses
In the literature on Kleene algebra, a number of variants have been proposed which impose additional structure specified by a theory, such as Kleene algebra with tests (KAT) and the recent Kleene algebra with observations (KAO), or make specific assumptions about certain constants, as for instance in NetKAT. Many of these variants fit within the unifying perspective offered by Kleene algebra with hypotheses, which comes with a canonical language model constructed from a given set of hypotheses. For the case of KAT, this model corresponds to the familiar interpretation of expressions as languages of guarded strings. A relevant question therefore is whether Kleene algebra together with a given set of hypotheses is complete with respect to its canonical language model. In this paper, we revisit, combine and extend existing results on this question to obtain tools for proving completeness in a modular way. We showcase these tools by giving new and modular proofs of completeness for KAT, KAO and NetKAT, and we prove completeness for new variants of KAT: KAT extended with a constant for the full relation, KAT extended with a converse operation, and a version of KAT where the collection of tests only forms a distributive lattice.
- 16 May 2024
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 20, Is (2)
Open AccessOn Tools for Completeness of Kleene Algebra with Hypotheses
In the literature on Kleene algebra, a number of variants have been proposed which impose additional structure specified by a theory, such as Kleene algebra with tests (KAT) and the recent Kleene algebra with observations (KAO), or make specific assumptions about certain constants, as for instance in NetKAT. Many of these variants fit within the unifying perspective offered by Kleene algebra with hypotheses, which comes with a canonical language model constructed from a given set of hypotheses. For the case of KAT, this model corresponds to the familiar interpretation of expressions as languages of guarded strings. A relevant question therefore is whether Kleene algebra together with a given set of hypotheses is complete with respect to its canonical language model. In this paper, we revisit, combine and extend existing results on this question to obtain tools for proving completeness in a modular way. We showcase these tools by giving new and modular proofs of completeness for KAT, KAO and NetKAT, and we prove completeness for new variants of KAT: KAT extended with a constant for the full relation, KAT extended with a converse operation, and a version of KAT where the collection of tests only forms a distributive lattice.
- Open Access
On Tools for Completeness of Kleene Algebra with Hypotheses
In the literature on Kleene algebra, a number of variants have been proposed which impose additional structure specified by a theory, such as Kleene algebra with tests (KAT) and the recent Kleene algebra with observations (KAO), or make specific assumptions about certain constants, as for instance in NetKAT. Many of these variants fit within the unifying perspective offered by Kleene algebra with hypotheses, which comes with a canonical language model constructed from a given set of hypotheses. For the case of KAT, this model corresponds to the familiar interpretation of expressions as languages of guarded strings. A relevant question therefore is whether Kleene algebra together with a given set of hypotheses is complete with respect to its canonical language model. In this paper, we revisit, combine and extend existing results on this question to obtain tools for proving completeness in a modular way. We showcase these tools by giving new and modular proofs of completeness for KAT, KAO and NetKAT, and we prove completeness for new variants of KAT: KAT extended with a constant for the full relation, KAT extended with a converse operation, and a version of KAT where the collection of tests only forms a distributive lattice.
Open AccessOn Tools for Completeness of Kleene Algebra with Hypotheses
In the literature on Kleene algebra, a number of variants have been proposed which impose additional structure specified by a theory, such as Kleene algebra with tests (KAT) and the recent Kleene algebra with observations (KAO), or make specific assumptions about certain constants, as for instance in NetKAT. Many of these variants fit within the unifying perspective offered by Kleene algebra with hypotheses, which comes with a canonical language model constructed from a given set of hypotheses. For the case of KAT, this model corresponds to the familiar interpretation of expressions as languages of guarded strings. A relevant question therefore is whether Kleene algebra together with a given set of hypotheses is complete with respect to its canonical language model. In this paper, we revisit, combine and extend existing results on this question to obtain tools for proving completeness in a modular way. We showcase these tools by giving new and modular proofs of completeness for KAT, KAO and NetKAT, and we prove completeness for new variants of KAT: KAT extended with a constant for the full relation, KAT extended with a converse operation, and a version of KAT where the collection of tests only forms a distributive lattice.
- Open Access
- 4 January 2021
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 5 (POPL) , 1-28
Cyclic proofs, system t, and the power of contraction
We study a cyclic proof system C over regular expression types, inspired by linear logic and non-wellfounded proof theory. Proofs in C can be seen as strongly typed goto programs. We show that they denote computable total functions and we analyse the relative strength of C and Gödel’s system T. In the general case, we prove that the two systems capture the same functions on natural numbers. In the affine case, i.e., when contraction is removed, we prove that they capture precisely the primitive recursive functions—providing an alternative and more general proof of a result by Dal Lago, about an affine version of system T. Without contraction, we manage to give a direct and uniform encoding of C into T, by analysing cycles and translating them into explicit recursions. Whether such a direct and uniform translation from C to T can be given in the presence of contraction remains open. We obtain the two upper bounds on the expressivity of C using a different technique: we formalise weak normalisation of a small step reduction semantics in subsystems of second-order arithmetic: ACA 0 and RCA 0 .
- 4 January 2021
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 5 (POPL) , 1-28
Open AccessCyclic proofs, system t, and the power of contraction
We study a cyclic proof system C over regular expression types, inspired by linear logic and non-wellfounded proof theory. Proofs in C can be seen as strongly typed goto programs. We show that they denote computable total functions and we analyse the relative strength of C and Gödel’s system T. In the general case, we prove that the two systems capture the same functions on natural numbers. In the affine case, i.e., when contraction is removed, we prove that they capture precisely the primitive recursive functions—providing an alternative and more general proof of a result by Dal Lago, about an affine version of system T. Without contraction, we manage to give a direct and uniform encoding of C into T, by analysing cycles and translating them into explicit recursions. Whether such a direct and uniform translation from C to T can be given in the presence of contraction remains open. We obtain the two upper bounds on the expressivity of C using a different technique: we formalise weak normalisation of a small step reduction semantics in subsystems of second-order arithmetic: ACA 0 and RCA 0 .
- Open Access
- 20 January 2020
- Published by Association for Computing Machinery (ACM)
- p. 325-337
Completeness of an axiomatization of graph isomorphism via graph rewriting in Coq
- 20 January 2020
- Published by Association for Computing Machinery (ACM)
- p. 325-337
Open AccessCompleteness of an axiomatization of graph isomorphism via graph rewriting in Coq
- Open Access
Treewidth-Two Graphs as a Free Algebra
We give a new and elementary proof that the graphs of treewidth at most two can be seen as a free algebra. This result was presented last year at MFCS and was proved through an elaborate analysis of the structure of K4-free graphs, ultimately reproving the well-known fact that the graphs of treewidth at most two are precisely those excluding K4 as a minor. Our new proof is based on a confluent and terminating rewriting system for treewidth-two graphs and does not involve graph minors anymore. The new strategy is simpler and robust in the sense that it can be adapted to subclasses of treewidth-two graphs. It could also be amenable to handle graphs of larger treewidth, where the excluded minors are typically unknown.
Open AccessTreewidth-Two Graphs as a Free Algebra
We give a new and elementary proof that the graphs of treewidth at most two can be seen as a free algebra. This result was presented last year at MFCS and was proved through an elaborate analysis of the structure of K4-free graphs, ultimately reproving the well-known fact that the graphs of treewidth at most two are precisely those excluding K4 as a minor. Our new proof is based on a confluent and terminating rewriting system for treewidth-two graphs and does not involve graph minors anymore. The new strategy is simpler and robust in the sense that it can be adapted to subclasses of treewidth-two graphs. It could also be amenable to handle graphs of larger treewidth, where the excluded minors are typically unknown.