Submitted or in preparation

• Complexity of determining Medvedev degrees of $\Pi^0_1$ sets.
  Rémi Pallen.
  Abstract

  The Medvedev lattice is a tool used to classify the complexities of effective closed sets. Here we are interested in the complexity of using this tool. For instance, for a fixed Medvedev degree $d$, how hard is it, given an effective closed set $X$, to determine whether $X$ has Medvedev degree $d$. We show that this problem and other related problems (being below $d$, above $d$ or incomparable with $d$) are naturally $\Sigma^0_3$ or $\Pi^0_3$ and reach this maximal complexity in most cases. However, a different behaviour appears depending on the meet-reducibility of the degree. The complexity of having maximal degree is paricularly difficult to establish, but we obtain a lower bound that almost matches the upper bound.

• Parametrized complexity of relations between multidimensional subshifts.
  Nicanor Carrasco-Vargas, Benjamin Hellouin De Menibus, Rémi Pallen.
  [arXiv]
  Abstract

  We study the parametrized complexity of fundamental relations between multidimensional subshifts, such as equality, conjugacy, inclusion, and embedding, for subshifts of finite type (SFTs) and effective subshifts. We build on previous work of E. Jeandel and P. Vanier on the complexity of these relations as two-input problems, by fixing one subshift as parameter and taking the other subshift as input. We study the impact of various dynamical properties related to periodicity, minimality, finite type, etc. on the computational properties of the parameter subshift, which reveals interesting differences and asymmetries.

  Among other notable results, we find choices of parameter that reach the maximum difficulty for each problem; we find nontrivial decidable problems for multidimensional SFTs, where most properties are undecidable; and we find connections with recent work relating having computable language and being minimal for some property, showing in particular that this property may not always be chosen conjugacy-invariant.

Published

• Multidimensional Tilings and MSO Logic.
  Rémi Pallen, Ilkka Törmä.
  Computability in Europe 2025.
  [HAL]

  Abstract

  We define sets of colourings of the infinite discrete plane using monadic second order (MSO) formulas. We determine the complexity of deciding whether such a formula defines a subshift, parametrized on the quantifier alternation complexity of the formula. We also study the complexities of languages of MSO-definable sets, giving either an exact classification or upper and lower bounds for each quantifier alternation class.

• Two-player Domino games.
  Benjamin Hellouin De Menibus, Rémi Pallen.
  Computability in Europe 2024.
  [HAL]

  Abstract

  We introduce a 2-player game played on an infinite grid, initially empty, where each player in turn chooses a vertex and colours it. The first player aims to create some pattern from a target set, while the second player aims to prevent it. We study the problem of deciding which player wins, and prove that it is undecidable. We also consider a variant where the turn order is not alternating but given by a balanced word, and we characterise the decidable and undecidable cases.