1
$\begingroup$

I have been looking online for how or if one can compute the language of an $S$-adic subshift generated by finitely many substitutions. I know that one can compute the language of a substitution subshift. However, since I don't have a good grasp on $S$-adic subshifts whether one can compute their languages, as was answered by Dan Rust here. However, I am unsure of an analog in the $S$-adic setting for this sort of algorithm.

More concretely, say I want to compute all words/factors of length $k$ in the $S$-adic subshift. I assume that I have $\rho_1,...,\rho_r$ substitions on a single alphabet $A$ and that the subshift corresponds to a closed nonempty subset $S\subseteq\{ 1,...,r \}^{\mathbb{N}}$. I think I can assume that there exists an $\ell_k\in \mathbb{N}$

$$ 2k \leq \vert \rho_{w_m}\circ ... \circ \rho_{w_{m+\ell_k-1}}(a) \vert $$

for all $a\in A$, all $(w_n)_{n=1}^\infty\in S$ and all $m\in \mathbb{N}$. This is an assumption on a minimal growth rate.

I can then consider all $\ell_k$-strings appearing in $S$, and they correspond to a composition of $\ell_k$ many substitutions from $\{ \rho_1,...,\rho_r \}$. I'll denote the obtained maps by $R_{\ell_k}(S)$. If I consider subwords $v$ occurring in $\phi(a)$ for some $\phi\in R_{\ell_k}(S)$, and then keep tracking $k$-words in $\phi'(v)$ for $\phi'\in R_{\ell_k}(S)$, will this give me a list of the $k$-words in the $S$-adic subshift?

I would appreciate any insights on this topic, as I don't think I understand the concept of a language of an $S$-adic subshift.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ An S-adic subshift also has a directive sequence as a part of its definition. Unless you want to consider the union over all directive sequences? In any case, the desubstitution method is probably the easiest method. Start with a word and try desubstituting until you either can't any more of one of the branches of the tree of choices ends up at a single letter. Just remember that you now have to desubstitute according to the directive sequence (with respect to the last substitution first). $\endgroup$
    – Dan Rust
    Commented Sep 14 at 21:25
  • $\begingroup$ Of course, once you have some words already in your list, you can stop when you reach one of them instead of when reaching a single letter. $\endgroup$
    – Dan Rust
    Commented Sep 14 at 21:34

0

Reset to default

You must log in to answer this question.