Showing 1–3 of 3 results for author: Cervelle, J

Cross-constraint basis theorems and products of partitions

Authors: Julien Cervelle, William Gaudelier, Ludovic Levy Patey

Abstract: We both survey and extend a new technique from Lu Liu to prove separation theorems between products of Ramsey-type theorems over computable reducibility. We use this technique to show that Ramsey's theorem for $n$-tuples and three colors is not computably reducible to finite products of Ramsey's theorem for $n$-tuples and two colors. We both survey and extend a new technique from Lu Liu to prove separation theorems between products of Ramsey-type theorems over computable reducibility. We use this technique to show that Ramsey's theorem for $n$-tuples and three colors is not computably reducible to finite products of Ramsey's theorem for $n$-tuples and two colors. △ Less

Submitted 2 July, 2024; originally announced July 2024.

Comments: 35 pages

The Reverse Mathematics of CAC for trees

Authors: Julien Cervelle, William Gaudelier, Ludovic Patey

Abstract: CAC for trees is the statement asserting that any infinite subtree of $\mathbb{N}^{<\mathbb{N}}$ has an infinite path or an infinite antichain. In this paper, we study the computational strength of this theorem from a reverse mathematical viewpoint. We prove that TAC for trees is robust, that is, there exist several characterizations, some of which already appear in the literature, namely, the tre… ▽ More CAC for trees is the statement asserting that any infinite subtree of $\mathbb{N}^{<\mathbb{N}}$ has an infinite path or an infinite antichain. In this paper, we study the computational strength of this theorem from a reverse mathematical viewpoint. We prove that TAC for trees is robust, that is, there exist several characterizations, some of which already appear in the literature, namely, the tree antichain theorem (TCAC) introduced by Conidis, and the statement SHER introduced by Dorais et al. We show that CAC for trees is computationally very weak, in that it admits probabilistic solutions. △ Less

Submitted 26 April, 2023; v1 submitted 1 June, 2022; originally announced June 2022.

Comments: 28 pages

Sofic Trace of a Cellular Automaton

Authors: Julien Cervelle, Enrico Formenti, Pierre Guillon

Abstract: The trace subshift of a cellular automaton is the subshift of all possible columns that may appear in a space-time diagram, ie the infinite sequence of states of a particular cell of a configuration; in the language of symbolic dynamics one says that it is a factor system. In this paper we study conditions for a sofic subshift to be the trace of a cellular automaton. The trace subshift of a cellular automaton is the subshift of all possible columns that may appear in a space-time diagram, ie the infinite sequence of states of a particular cell of a configuration; in the language of symbolic dynamics one says that it is a factor system. In this paper we study conditions for a sofic subshift to be the trace of a cellular automaton. △ Less

Submitted 8 March, 2007; originally announced March 2007.

Comments: 10 pages + 6 for included proofs

MSC Class: 37B15