One-sided Hom shifts

Marie-Pierre Béal ID, Alexi Block Gorman · 2025

Read One-sided Hom shifts by Marie-Pierre Béal ID, Alexi Block Gorman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-24754.txt.

Introduction

Béal and Block Gorman settled two decision problems about symbolic sequence systems in twenty twenty-five. Hom shifts are sets of sequences generated by labeling edges of a directed graph. They asked whether one can always decide if a one-sided shift of finite type, a sequence system defined by forbidden blocks, is conjugate to a Hom shift. The answer is yes for one-sided shifts, and also yes for the tree version, where sequences branch like trees. Their proof builds on Williams's classical theory of one-sided shifts.

Catalog record

CREATORMarie-Pierre Béal ID, Alexi Block Gorman
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-24754

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

One-sided Hom shifts Marie-Pierre Béal ID, Alexi Block Gorman Abstract We prove that it is decidable whether a one-sided shift of finite type is conjugate to a one-sided Hom-shift, and whether a tree-shift of finite type is conjugate to a Hom tree-shift. The proof uses Williams’s theory for one-sided shifts. 1 Introduction We consider two types of shift spaces, shifts of sequences and tree-shifts. A shift of sequences is a set of one- or two-sided infinite sequences of symbols defined by a collection of finite words called forbidden blocks. A tree-shift is a set of infinite trees defined by a collection of forbidden blocks. A shift space of sequences is equipped with a shift transformation, whereas a tree-shift is equipped with multiple directional shift transformations. A conjugacy between shift spaces is a continuous bijection that commutes with the shift transformations. Shifts spaces defined by a finite set of forbidden blocks are called shifts of finite type. Note that a one-sided shift of sequences can be seen as a tree-shift with arity 1 . The problem of deciding whether two-sided finite-type shifts of sequences are conjugate remains open (see, for example, [ LindMarcus1995 ] ). By contrast, the situation is significantly simpler for one-sided shifts: Williams [ Williams1973 ] proved that conjugacy is decidable for one-sided shifts of finite type. This decidability also extends to tree-shifts [ AubrunBeal2012 ] , a consequence of the inherently one-sided structure of trees. Tree-shifts are, however, more complex than one-sided shifts. Petersen and Salama [ PetersenSalama2018 ] , [ PetersenSalama2020 ] introduced the topological entropy for such spaces as an analog to topological entropy for traditional shift spaces to investigate their complexity. Their results were generalized to asymptotic pressure for a broad class of systems in [ PetersenSalama2023 ] . Properties of tree-shifts like entropy, transitivity, Hausdorff dimensions have been explored in [ BanCHW22 ] , [ BanEtal2025a ] , [ BanEtal2025b ] . In this paper, we consider a particular class of shifts called Hom shifts. A Hom shift is defined by an undirected, simple graph G (where self-loops are allowed). We also consider the class of directed Hom tree-shifts defined by a simple directed graph G (again with self-loops). Directed Hom tree-shifts are called hom tree-SFT in [ BanEtAl2021 ] . A Hom shift (resp. a directed Hom shift) of sequences is the set of all sequences of symbols where the consecutive pair ab is forbidden whenever (a,b) is not an edge in the undirected (resp. directed) graph G . A Hom shift of trees (resp. a directed Hom tree-shift) is the set of all trees avoiding all blocks of height 2 with a root labeled a and having at least one child labeled b such that (a,b) is not an edge in the undirected (resp. directed) graph G . Alternatively, a Hom shift can be described as a nearest neighbour shift of finite type that is symmetric and isotropic. Hom shifts can be defined and studied in the multidimensional context (see [ CHANDGOTIA_2017 ] , [ ChandgotiaMarcus2018 ] , [ GangloffHellouinOpocha2024 ] ). They form a natural subclass of shifts of finite type that arise in various contexts. For example, the hard square shift and the n -coloured chessboard shifts are both two-dimensional Hom shifts. Chandgotia and Marcus [ ChandgotiaMarcus2018 ] studied the mixing properties of Hom shifts and related them to some questions in graph theory therein. In this paper, we prove that it is decidable whether a one-sided shift of finite type is conjugate to a one-sided Hom shift, and whether a tree-shift of finite type is conjugate to a Hom tree-shift. The proof uses Williams’s theory for one-sided shifts. The total amalgamation of a directed multi-graph is the unique directed multi-graph obtained after a sequence of out-merging operations. In [ Williams1973 ] , Williams proved that if G and H are irreducible directed graphs that define irreducible one-sided edge shifts, then these shifts are conjugate if and only if G and H have the same total amalgamation. We prove that a one-sided shift of finite type, or a tree-shift of finite type, is conjugate to a one-sided Hom shift if and only if its total amalgamation satisfies some regularity conditions that are decidable. For tree-shifts, it was proved in [ AubrunBeal2012 ] that two irreducible edge tree shifts defined by a bottom-up tree automaton are conjugate if and only if they have the same total amalgamation (a bottom-up tree automaton obtained through merging operations). We give another proof of this result using trim top-down tree automata, and we define the total amalgamation of a top-down edge tree automaton similarly. A top-down tree automaton is trim if there is at least one (top-down) transition starting at any state. The irreducibility is not required. We prove that, if \mathcal{A} and \mathcal{B} are trim top-down edge tree automata defining two tree-shifts of finite type, then these shifts are conjugate if and only if \mathcal{A} and \mathcal{B} have the same total amalgamation. We prove that a tree-shift of finite type defined by a trim edge tree automaton is conjugate to a Hom tree-shift if the total amalgamation of this tree automaton satisfies some regularity conditions. The property is decidable in polynomial space and time. We also show that if two Hom tree shifts defined by undirected graphs G and H , respectively, are conjugate, then G is equal to H , up to a graph isomorphism. We prove that a tree-shift of finite type defined by a trim edge tree automaton is conjugate to a directed Hom tree-shift if the total amalgamation of this tree automaton satisfies some symmetry conditions. The property is also decidable in polynomial space and time. The paper is organized as follows. We recall basic definitions of symbolic dynamics in Section 2 , including Williams’s results on one-sided shifts of sequences. Basic definitions on tree shifts and the decidability of conjugacy for this class of shifts are presented in Section 4 . One-sided Hom shifts of sequences and Hom tree-shifts are studied in Section 3 and . Directed Hom tree shifts are studied in Section . 2 Symbolic dynamics We briefly recall some basic definitions of symbolic dynamics. For a more complete presentation, see [ LindMarcus1995 ] , [ Kitchens1998 ] , and [ BealBerstelEilersPerrin2010 ] . 2.1 Words and sequences Let A be a finite set, called the alphabet . The elements of A are called letters . A word on A is a finite sequence of elements of A . The set of words on A is denoted by A^{*} . We consider the set A^{\mathbb{Z}} of two-sided infinite sequences of elements of A , equipped with the product of the discrete topology on A . For x=(x_{n})_{n\in\mathbb{Z}}\in A^{\mathbb{Z}} with x_{n}\in A and i\leq j , we write x_{[i,j)}=x_{i}x_{i+1}\cdots x_{j-1} . A word u occurs in a sequence x if u=x_{[i,j)} for some i,j . One also says that u is a block of x . Let S denote the shift transformation defined for x\in A^{\mathbb{Z}} by S(x)=y if y_{n}=x_{n+1} for n\in\mathbb{Z} . It is continuous and one-to-one from A^{\mathbb{Z}} to itself. We also consider the corresponding sets A^{\mathbb{N}} of right-infinite sequences. The one-sided shift transformation is

Read the complete text