11 citations · 17 across the 7 of their papers we have counts for
7 papers
The Reverse Mathematics of CAC for trees
Julien Cervelle, William Gaudelier, Ludovic Patey
CAC for trees is the statement asserting that any infinite subtree of has an infinite path or an infinite antichain. In this paper, we study the computat…
Entropy Games and Matrix Multiplication Games
Eugene Asarin, Julien Cervelle, Aldric Degorre +3
Two intimately related new classes of games are introduced and studied: entropy games (EGs) and matrix multiplication games (MMGs). An EG is played on a finite arena by two-and-a-h…
Turing degrees of limit sets of cellular automata
Alex Borello, Julien Cervelle, Pascal Vanier
Cellular automata are discrete dynamical systems and a model of computation. The limit set of a cellular automaton consists of the configurations having an infinite sequence of pre…
Acceptance conditions for omega-languages and the Borel hierarchy
Julien Cervelle, Alberto Dennunzio, Enrico Formenti +1
This paper investigates acceptance conditions for finite automata recognizing omega-regular languages. As a first result, we show that, under any acceptance condition that can be d…
Ultimate Traces of Cellular Automata
Julien Cervelle, Enrico Formenti, Pierre Guillon
A cellular automaton (CA) is a parallel synchronous computing model, which consists in a juxtaposition of finite automata (cells) whose state evolves according to that of their nei…
Sofic Trace of a Cellular Automaton
Julien Cervelle, Enrico Formenti, Pierre Guillon
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…