SBSebastián Barbieri

Sebastián Barbieri

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Sebastián Barbieri has a total of 30 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • A remark on inverse limits of effective subshifts

    by Sebastián Barbieri, Leo Poirier

    We show that, for every finitely generated group with decidable word problem and undecidable domino problem, there exists a sequence of effective subshifts, whose inverse limit is not the topological factor of any effective dynamical system. This follows from considerations on the universality under topological factors for this class of dynamical systems.


  • Self-simulable groups

    by Sebastián Barbieri, Mathieu Sablik, Ville Salo

    We say that a finitely generated group Γ \Gamma is self-simulable if every effectively closed action of Γ \Gamma on a closed subset of { 0 , 1 } N \{\mathtt {0},\mathtt {1}\}^{\mathbb {N}} is the topological factor of a Γ \Gamma -subshift of finite type. We show that self-simulable groups exist, that any direct product of non-amenable finitely generated groups is self-simulable, that under technical conditions self-simulability is inherited from subgroups, and that the subclass of self-simulable groups is stable under commensurability and quasi-isometries of finitely presented groups. Some notable examples of self-simulable groups obtained are the direct product F k × F k F_k \times F_k of two free groups of rank k ≥ 2 k \geq 2 , non-amenable finitely generated branch groups, the simple groups of Burger and Mozes, Thompson’s V V , the groups GL n ⁡ ( Z ) \operatorname {GL}_n(\mathbb {Z}) , SL n ⁡ ( Z ) \operatorname {SL}_n(\mathbb {Z}) , A u t ( F n ) Aut(F_n) and O u t ( F n ) Out(F_n) for n ≥ 5 n \geq 5 ; The braid groups B m B_m for m ≥ 7 m \geq 7 , and certain classes of RAAGs. We also show that Thompson’s F F is self-simulable if and only if F F is non-amenable, thus giving a computability characterization of this well-known open problem. We also exhibit a few applications of self-simulability on the dynamics of these groups, notably, that every self-simulable group with decidable word problem admits a non-empty strongly aperiodic subshift of finite type.


  • Open Access

    The group of reversible turing machines: subgroups, generators, and computability

    by Sebastian Barbieri, Jarkko Kari, Ville Salo

    We study an abstract group of reversible Turing machines. In our model, each machine is interpreted as a homeomorphism over a space which represents a tape filled with symbols and a head carrying a state. These homeomorphisms can only modify the tape at a bounded distance around the head, change the state, and move the head in a bounded way. We study three natural subgroups arising in this model: the group of finite-state automata, which generalizes the topological full groups studied in topological dynamics and the theory of orbit-equivalence; the group of oblivious Turing machines whose movement is independent of tape contents, which generalizes lamplighter groups and has connections to the study of universal reversible logical gates, and the group of elementary Turing machines, which are the machines which are obtained by composing finite-state automata and oblivious Turing machines. We show that both the group of oblivious Turing machines and that of elementary Turing machines are finitely generated, while the group of finite-state automata and the group of reversible Turing machines are not. We show that the group of elementary Turing machines has undecidable torsion problem. From this, we also obtain that the group of cellular automata (more generally, the automorphism group of any uncountable one-dimensional sofic subshift) contains a finitely generated subgroup with undecidable torsion problem. We also show that the torsion problem is undecidable for the topological full group of a full $\mathbb {Z}^d$ -shift on a nontrivial alphabet if and only if $d \geq 2$ .


  • Open Access

    A geometric obstruction to self-simulation for groups

    by Sebastián Barbieri, Kanéda Blot, Mathieu Sablik, Ville Salo

    We introduce a new quasi-isometry invariant for finitely generated groups and show that every group with this property admits a subshift which is effectively closed by patterns and that cannot be realized as the topological factor of any subshift of finite type. We provide several examples of groups with the property, such as amenable groups, multi-ended groups, generalized Baumslag-Solitar groups, fundamental groups of surfaces, and cocompact Fuchsian groups.

  • Open Access

    A remark on inverse limits of effective subshifts

    by Sebastián Barbieri, Leo Poirier

    We show that, for every finitely generated group with decidable word problem and undecidable domino problem, there exists a sequence of effective subshifts whose inverse limit is not the topological factor of any effective dynamical system. This follows from considerations on the universality under topological factors for this class of dynamical systems.

  • Soficity of free extensions of effective subshifts

    by Sebastián Barbieri, Mathieu Sablik, Ville Salo

    Let $ G $ be a group and $ H\leqslant G $ a subgroup. The free extension of an $ H $-subshift $ X $ to $ G $ is the $ G $-subshift $ \widetilde{X} $ whose configurations are those for which the restriction to every coset of $ H $ is a configuration from $ X $. We study the case of $ G = H \times K $ for infinite and finitely generated groups $ H $ and $ K $. On the one hand, we show that if $ K $ is nonamenable and $ H $ has decidable word problem, then the free extension to $ G $ of any $ H $-subshift which is effectively closed is a sofic $ G $-subshift. On the other hand, we prove that if both $ H $ and $ K $ are amenable, there are always $ H $-subshifts which are effectively closed by patterns whose free extension to $ G $ is non-sofic. We also present a few applications in the form of a new simulation theorem and a new class of groups which admit strongly aperiodic SFTs.


  • Effective dynamical systems beyond dimension zero and factors of SFTs

    by Sebastián Barbieri, Nicanor Carrasco-Vargas, Cristóbal Rojas

    Using tools from computable analysis, we develop a notion of effectiveness for general dynamical systems as those group actions on arbitrary spaces that contain a computable representative in their topological conjugacy class. Most natural systems one can think of are effective in this sense, including some group rotations, affine actions on the torus and finitely presented algebraic actions. We show that for finitely generated and recursively presented groups, every effective dynamical system is the topological factor of a computable action on an effectively closed subset of the Cantor space. We then apply this result to extend the simulation results available in the literature beyond zero-dimensional spaces. In particular, we show that for a large class of groups, many of these natural actions are topological factors of subshifts of finite type.


  • Indistinguishable asymptotic pairs and multidimensional Sturmian configurations

    by Sebastián Barbieri, Sébastien Labbé

    Two asymptotic configurations on a full $\mathbb {Z}^d$ -shift are indistinguishable if, for every finite pattern, the associated sets of occurrences in each configuration coincide up to a finitely supported permutation of $\mathbb {Z}^d$ . We prove that indistinguishable asymptotic pairs satisfying a ‘flip condition’ are characterized by their pattern complexity on finite connected supports. Furthermore, we prove that uniformly recurrent indistinguishable asymptotic pairs satisfying the flip condition are described by codimension-one (dimension of the internal space) cut and project schemes, which symbolically correspond to multidimensional Sturmian configurations. Together, the two results provide a generalization to $\mathbb {Z}^d$ of the characterization of Sturmian sequences by their factor complexity $n+1$ . Many open questions are raised by the current work and are listed in the introduction.


  • Open Access

    Indistinguishable asymptotic pairs and multidimensional Sturmian configurations

    by Sebastián Barbieri, Sébastien Labbé

    Two asymptotic configurations on a full $\mathbb{Z}^d$-shift are indistinguishable if for every finite pattern the associated sets of occurrences in each configuration coincide up to a finitely supported permutation of $\mathbb{Z}^d$. We prove that indistinguishable asymptotic pairs satisfying a "flip condition" are characterized by their pattern complexity on finite connected supports. Furthermore, we prove that uniformly recurrent indistinguishable asymptotic pairs satisfying the flip condition are described by codimension-one (dimension of the internal space) cut and project schemes, which symbolically correspond to multidimensional Sturmian configurations. Together the two results provide a generalization to $\mathbb{Z}^d$ of the characterization of Sturmian sequences by their factor complexity $n+1$. Many open questions are raised by the current work and are listed in the introduction.