3
$\begingroup$

Note: I come from a mathematics background.


The Thue-Morse sequence $t_n$ is a binary sequence that takes the value $0$ at the positive integer $n$ if the number of $1$s in its binary expansion is even, $1$ otherwise.

A definition that is closer to computer science states that $t_n$ is the binary sequence obtained by starting with $0$ and successively appending the boolean complement of the sequence obtained so far.

Thus, $t_n$ begins $0,1,1,0,1,0,0,1,\ldots$

This sequence is of much interest in mathematics, but so far I have not come across any applications in computer science. This surprises me, for the two following reasons:

  • The Thue-Morse sequence is automatic, i.e., the sequence is fully characterized by a finite automaton,
  • It is a binary sequence.

What theoretic or practical applications of the Thue-Morse sequence are there in computer science?

$\endgroup$
1
  • $\begingroup$ Regarding your comment here, the answer is actually "no". See my profile. $\endgroup$ – user114441 Mar 15 '20 at 15:13
3
$\begingroup$

The problem of computing $t_N$ given $N$ is famous in theoretical computer science as the PARITY problem and is a well-known example of a decision language that can be recognized by linear-size $O(\log n)$-depth circuits but cannot be recognized by polynomial-size circuits of constant depth; here $n$ is the length of the binary expansion of $N$.

Parity computation finds application in error-correction codes, to calculate a check bit to append to data (example). It is also useful in multiplying 0/1 matrices in the binary field GF(2) (where the add operation is $\oplus$ and the multiply operation is $\wedge$), since the inner product of, for example, $(a_1, a_2, a_3, a_4)$ with $(b_1, b_2, b_3, b_4)$ is $$ (a_1 \wedge b_1) \oplus (a_2 \wedge b_2) \oplus (a_3 \wedge b_3) \oplus (a_4 \wedge b_4), $$ which is just the parity of the bit-by-bit conjunction $a \wedge b$.

$\endgroup$
3
+25
$\begingroup$

I don't know if this counts as an application but at least it shows up. When using a polynomial rolling hash, it's tempting to do it modulo $2^{32}$ or $2^{64}$ (depending on the word size of the computer) since on most modern architectures addition and multiplication of integers just handle overflows this way, saving time. This method will fail often on Thue-Morse-like strings (like ABBABAAB...), as explained here. I remember not understanding the factorization of $T$ a few years ago, the key is the recurrence relation $t_{2n} = t_n$, $t_{2n+1} = 1-t_n$

Alternative explanation of the factorization: from the "append the negated sequence" definition one can directly see $\Pi_n (1-x^{2^n})$ , since each each term does exactly that.

$\endgroup$
1
  • $\begingroup$ That's an interesting example. $\endgroup$ – Klangen Feb 25 '20 at 8:16
1
$\begingroup$

This is not an answer, but too long for a comment.

so far I have not come across any applications in computer science. This surprises me, for the two following reasons:

  • The Thue-Morse sequence is automatic, i.e., the sequence is fully characterized by a finite automaton,

  • It is a binary sequence.

You may want to refine your criteria for what makes something applicable in computer science. These two properties don't seem like very good criteria:

  • The fact that this sequence is automatic is true and does suggest studying it in the domain of computer science, but it's a very weak statement; most sequences (almost all that I am aware of) are computable.

    Also, this sequence is not regular, so your statement that it is "characterized by a finite automaton" seems misleading.

  • The fact that the sequence is binary means nothing, I don't see that as relevant to its applicability.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.