You will find below all the article I participated to write until today, by year.

Parametrized complexity of relations between multidimensional subshifts

Co-author: Nicanor CARRASCO-VARGAS, Benjamin HELLOUIN DE MENIBUS

Year: 2026

Link: https://hal.science/hal-05499852v1

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 SFT, 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.

Multidimensional Tilings and MSO Logic

Co-author: Ilkka TÖRMÄ

Year: 2025

Link: https://hal.science/hal-05137647v1

Abstract: We define sets of coulourings 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

Co-author: Benjamin HELLOUIN DE MENIBUS

Year: 2024

Link: https://hal.science/hal-04265421v2

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.

To be continued…

Complexity of determining Medvedev degrees of Pi01 sets