DPDamien Pous

Damien Pous

*This is an algorithmically generated author record based on publicly available information.

Damien Pous has a total of 53 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Higher Catoids, Higher Quantales and their Correspondences

    by Cameron Calk, Philippe Malbos, Damien Pous, Georg Struth

    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.


    • 1 January 2025
    • Published by HAL in HAL
    Open Access

    On the Two Paths Theorem and the Two Disjoint Paths Problem

    by Samuel Humeau, Damien Pous

    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

    Completeness Theorems for Kleene algebra with tests and top

    by Damien Pous, Jana Wagemaker

    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

    On Tools for Completeness of Kleene Algebra with Hypotheses

    by Damien Pous, Jurriaan Rot, Jana Wagemaker

    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

    by Damien Pous, Jurriaan Rot, Jana Wagemaker

    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.

  • Corecursion Up-to via Causal Transformations

    by Damien Pous, Jurriaan Rot, Ruben Turkenburg


  • Open Access

    Cyclic proofs, system t, and the power of contraction

    by Denis Kuperberg, Laureline Pinault, Damien Pous

    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 .


    • 28 April 2018
    • Published by HAL in HAL
    Open Access

    Treewidth-Two Graphs as a Free Algebra

    by Christian Doczkal, Damien Pous

    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.