1
$\begingroup$

This may be a very basic question, but I have not found an answer to it so far in my search. The question is whether there is an "algorithmic" way to check unique-composition/recognizability of a tiling coming from a substitution. I am interested to know if one can reasonably check for any FLC substitution tiling whether it is aperiodic.

For example, if we take the symbolic case with $\mathcal{A}=\{ a,b,c,d \}$ and consider a substitution

$$ a\to ab, \quad b\to bc, \quad c\to da \quad \text{and} \quad d\to cd. $$

Is this substitution recognizable? And is there a method to build the unique composition?

$\endgroup$
4
  • $\begingroup$ The example is primitive, so recognizable. ("Of course" recognizability must be decidable in general, but I don't know a proof/reference.) $\endgroup$
    – Ville Salo
    Commented Oct 4, 2023 at 13:44
  • $\begingroup$ @VilleSalo But doesn't recognizability imply aperiodicity? I think I encountered an example of a primitive periodic substitution. Though I am probably missing something. $\endgroup$ Commented Oct 4, 2023 at 13:50
  • $\begingroup$ For example, I think a constant substitution $a,b,c,d\to abcd$ is a primitive substitution, but should definitely be periodic. $\endgroup$ Commented Oct 4, 2023 at 14:19
  • 1
    $\begingroup$ Yes sorry you are right, you need also aperiodicity. Aperiodicity is decidable, look up the HD0L ultimate periodicity problem $\endgroup$
    – Ville Salo
    Commented Oct 4, 2023 at 15:36

1 Answer 1

0
$\begingroup$

Following Ville Salo's comments I came across upon Pansiot's paper, DECIDABILITY OF PERIODICITY FOR INFINITE WORDS. The papers shows an algorithm to decide whether an infinite word fixed by a substitution is aperiodic relying heavily on the Coven-Hedlund theorem regarding complexity of an infinite word.

If I am not mistaken, the crux of the paper is Lemma 2 discussing whether finite subwords have unique extension to a larger words. If I am not mistaken, in the case I am interested the lemma simplifies to the following:

Let $S:A\to A^+$ be an injective substition such that $\vert S^n(a)\vert\to \infty$ for all $a\in A$. Then $\omega=\lim_{n\to > \infty} S^n(a)$ is aperiodic if and only if $c_2(\omega)>c_1(\omega)$, where $c_k(\omega)$ is the number of $k$-subwords in $\omega$.

The original statement talks about having unique-extension\prolongablity of sub-words of the form $au\in A^+$, where $a\in A$ satisfies $\vert S^n(a)\vert\to \infty$ and $u\in A^*$. Since I assume every letter is growing, I can take the lemma with $u$ being the empty word.

I post this as an answer since I don't think I should add this in an edit to the original question. I would welcome and appreciate any corrections or pointing out if this argument is incorrect.

$\endgroup$
2
  • $\begingroup$ (Just for context, the decidability of HD0L periodicity which I mentioned is a vast generalization of this result.) $\endgroup$
    – Ville Salo
    Commented Oct 9, 2023 at 13:03
  • $\begingroup$ @VilleSalo I didn't want to diminish from the actual result, but for my purpose this was very easy to check and simple condition. $\endgroup$ Commented Oct 9, 2023 at 13:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .