Christophe Ringeissen
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
Research Subjects
Christophe Ringeissen has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Andrew M. Marshall
University of Mary Washington
6 shared publications - Serdar Erbatur
University of Texas at Dallas
5 shared publications - Paula Chocron
IOMED Medical Solutions SL
3 shared publications - Clark Barrett
Stanford University
2 shared publications - Eric Monfroy
University of Amsterdam The Netherlands
2 shared publications - Paliath Narendran
University at Albany-SUNY
2 shared publications
Latest Publications
- Open Access
- 15 September 2025
- Published by Springer Nature
- p. 153-168
Polite Combination in Parametric Array Theories
Parametric array theories are extensions of the quantifier-free theory of arrays with relations that hold componentwise. We observe that decision procedures for the satisfiability of these theories rely on a kind of finite witnessability property. We use this insight to show the politeness of these theories with respect to the index and element sorts. Our results clarify the politeness of the theory of sets with the cardinality operator, which was left open in the literature.
- 15 September 2025
- Published by Springer Nature
- p. 153-168
Open AccessPolite Combination in Parametric Array Theories
Parametric array theories are extensions of the quantifier-free theory of arrays with relations that hold componentwise. We observe that decision procedures for the satisfiability of these theories rely on a kind of finite witnessability property. We use this insight to show the politeness of these theories with respect to the index and element sorts. Our results clarify the politeness of the theory of sets with the cardinality operator, which was left open in the literature.
- Open Access
- 15 September 2025
- Published by Springer Nature
- Vol. 19 (1) , 209-227
Graph-Embedded Rewrite Systems: Combination and Undecidability Results
In this paper, we consider the knowledge problems of deduction and static equivalence in the formal analysis of security protocols. We extend a recent result that developed a decision procedure for these problems in the non-disjoint combination $$R \cup E$$ , where R is a subterm $$E$$ -convergent term rewrite system (TRS) and $$E$$ is a restricted form of permutative theory. Here, we consider the same combination problem but replace the subterm $$E$$ -convergent TRS with a superclass of subterm $$E$$ -convergent, called contracting $$E$$ -convergent. We show that the previous decision procedure can be extended to obtain a new algorithm for this larger class of combined theories. We also explore the gap between the contracting TRSs, for which deduction and static-equivalence are decidable, and a larger superclass called graph-embedded for which these problems are undecidable. This gap is of interest since one would like to get closer to graph-embedded and still maintain decidability of the above “knowledge problems.” We show that at least one way of weakening the restrictions of the contracting definition will not work, as it leads to undecidability results for deduction and static equivalence. We also show that a subset of the graph-embedded rules is still sufficient to obtain undecidability.- 15 September 2025
- Published by Springer Nature
- Vol. 19 (1) , 209-227
Open AccessGraph-Embedded Rewrite Systems: Combination and Undecidability Results
In this paper, we consider the knowledge problems of deduction and static equivalence in the formal analysis of security protocols. We extend a recent result that developed a decision procedure for these problems in the non-disjoint combination $$R \cup E$$ , where R is a subterm $$E$$ -convergent term rewrite system (TRS) and $$E$$ is a restricted form of permutative theory. Here, we consider the same combination problem but replace the subterm $$E$$ -convergent TRS with a superclass of subterm $$E$$ -convergent, called contracting $$E$$ -convergent. We show that the previous decision procedure can be extended to obtain a new algorithm for this larger class of combined theories. We also explore the gap between the contracting TRSs, for which deduction and static-equivalence are decidable, and a larger superclass called graph-embedded for which these problems are undecidable. This gap is of interest since one would like to get closer to graph-embedded and still maintain decidability of the above “knowledge problems.” We show that at least one way of weakening the restrictions of the contracting definition will not work, as it leads to undecidability results for deduction and static equivalence. We also show that a subset of the graph-embedded rules is still sufficient to obtain undecidability. - 29 August 2025
- Published by Springer Nature
- p. 182-189
Interpolating Parametric Array Theories
- 7 September 2024
- Published by Springer Nature
- p. 82-98
Combined Abstract Congruence Closure for Theories with Associativity or Commutativity
- 7 September 2024
- Published by Springer Nature
- p. 82-98
Combined Abstract Congruence Closure for Theories with Associativity or Commutativity
- 7 September 2024
- Published by Springer Nature
- p. 47-63
Deciding Knowledge Problems Modulo Classes of Permutative Theories
- 7 September 2024
- Published by Springer Nature
- p. 47-63
Deciding Knowledge Problems Modulo Classes of Permutative Theories
- 1 September 2021
- Published by Springer Nature
- p. 25-42
Non-disjoint Combined Unification and Closure by Equational Paramodulation
- 1 September 2021
- Published by Springer Nature
- p. 25-42
Non-disjoint Combined Unification and Closure by Equational Paramodulation
- Open Access
- 5 July 2021
- Published by Springer Nature
- p. 148-165
Politeness and Stable Infiniteness: Stronger Together
We make two contributions to the study of polite combination in satisfiability modulo theories. The first is a separation between politeness and strong politeness, by presenting a polite theory that is not strongly polite. This result shows that proving strong politeness (which is often harder than proving politeness) is sometimes needed in order to use polite combination. The second contribution is an optimization to the polite combination method, obtained by borrowing from the Nelson-Oppen method. The Nelson-Oppen method is based on guessing arrangements over shared variables. In contrast, polite combination requires an arrangement overallvariables of the shared sorts. We show that when using polite combination, if the other theory is stably infinite with respect to a shared sort, only the shared variables of that sort need be considered in arrangements, as in the Nelson-Oppen method. The time required to reason about arrangements is exponential in the worst case, so reducing the number of variables considered has the potential to improve performance significantly. We show preliminary evidence for this by demonstrating a speed-up on a smart contract verification benchmark.
- 5 July 2021
- Published by Springer Nature
- p. 148-165
Open AccessPoliteness and Stable Infiniteness: Stronger Together
We make two contributions to the study of polite combination in satisfiability modulo theories. The first is a separation between politeness and strong politeness, by presenting a polite theory that is not strongly polite. This result shows that proving strong politeness (which is often harder than proving politeness) is sometimes needed in order to use polite combination. The second contribution is an optimization to the polite combination method, obtained by borrowing from the Nelson-Oppen method. The Nelson-Oppen method is based on guessing arrangements over shared variables. In contrast, polite combination requires an arrangement overallvariables of the shared sorts. We show that when using polite combination, if the other theory is stably infinite with respect to a shared sort, only the shared variables of that sort need be considered in arrangements, as in the Nelson-Oppen method. The time required to reason about arrangements is exponential in the worst case, so reducing the number of variables considered has the potential to improve performance significantly. We show preliminary evidence for this by demonstrating a speed-up on a smart contract verification benchmark.
- 24 June 2020
- Published by Springer Nature
- Vol. 12166, 238-255
Politeness for the Theory of Algebraic Datatypes
Algebraic datatypes, and among them lists and trees, have attracted a lot of interest in automated reasoning and Satisfiability Modulo Theories (SMT). Since its latest stable version, the SMT-LIB standard defines a theory of algebraic datatypes, which is currently supported by several mainstream SMT solvers. In this paper, we study this particular theory of datatypes and prove that it is strongly polite, showing also how it can be combined with other arbitrary disjoint theories using polite combination. Our results cover both inductive and finite datatypes, as well as their union. The combination method uses a new, simple, and natural notion of additivity, that enables deducing strong politeness from (weak) politeness.
- 24 June 2020
- Published by Springer Nature
- Vol. 12166, 238-255
Politeness for the Theory of Algebraic Datatypes
Algebraic datatypes, and among them lists and trees, have attracted a lot of interest in automated reasoning and Satisfiability Modulo Theories (SMT). Since its latest stable version, the SMT-LIB standard defines a theory of algebraic datatypes, which is currently supported by several mainstream SMT solvers. In this paper, we study this particular theory of datatypes and prove that it is strongly polite, showing also how it can be combined with other arbitrary disjoint theories using polite combination. Our results cover both inductive and finite datatypes, as well as their union. The combination method uses a new, simple, and natural notion of additivity, that enables deducing strong politeness from (weak) politeness.
- 2 March 2020
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 30 (6) , 683-709
Computing knowledge in equational extensions of subterm convergent theories
We study decision procedures for two knowledge problems critical to the verification of security protocols, namely the intruder deduction and the static equivalence problems. These problems can be related to particular forms of context matching and context unification. Both problems are defined with respect to an equational theory and are known to be decidable when the equational theory is given by a subterm convergent term rewrite system (TRS). In this work, we extend this to consider a subterm convergent TRS defined modulo an equational theory, like Commutativity. We present two pairs of solutions for these important problems. The first solves the deduction and static equivalence problems in rewrite systems modulo shallow theories such as Commutativity. The second provides a general procedure that solves the deduction and static equivalence problems in subterm convergent systems modulo syntactic permutative theories, provided a finite measure is ensured. Several examples of such theories are also given.
- 2 March 2020
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 30 (6) , 683-709
Computing knowledge in equational extensions of subterm convergent theories
We study decision procedures for two knowledge problems critical to the verification of security protocols, namely the intruder deduction and the static equivalence problems. These problems can be related to particular forms of context matching and context unification. Both problems are defined with respect to an equational theory and are known to be decidable when the equational theory is given by a subterm convergent term rewrite system (TRS). In this work, we extend this to consider a subterm convergent TRS defined modulo an equational theory, like Commutativity. We present two pairs of solutions for these important problems. The first solves the deduction and static equivalence problems in rewrite systems modulo shallow theories such as Commutativity. The second provides a general procedure that solves the deduction and static equivalence problems in subterm convergent systems modulo syntactic permutative theories, provided a finite measure is ensured. Several examples of such theories are also given.