5
$\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?

Improve this question
$\endgroup$
2

5 Answers 5

Reset to default
4
+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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's an interesting example. $\endgroup$
    – Klangen
    Feb 25, 2020 at 8:16
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$.

Improve this answer
$\endgroup$
3
$\begingroup$

In the paper https://arxiv.org/abs/1408.5963 Thue-Morse sequence was used to construct a distributed algorithm which is non-local but halts on every finite network (input).

Improve this answer
$\endgroup$
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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Your observation that the sequence is not regular is right. But it is "automatic" in the following sense: each symbol of the sequence can be calculated by a finite state automaton based on the representation of the position in binary. (Actually in a very simple way, determining the parity the number of 1 bits.) In that way it is a stronger statement than "computable" (by a Turing machine). $\endgroup$
    – Hendrik Jan
    Sep 1, 2021 at 18:15
0
$\begingroup$

For coding test like this one :D. Using breadth first search could solve this but it soon eats up memory as pos grows large. Binary search works but Thue-Morse has the best runtime.

Consider a special family of Engineers and Doctors. This family has the following rules:

  • Everybody has two children.
  • The first child of an Engineer is an Engineer and the second child is a Doctor.
  • The first child of a Doctor is a Doctor and the second child is an Engineer. All generations of Doctors and Engineers start with an Engineer.

We can represent the situation using this diagram:

            E
       /         \
      E           D
    /   \        /  \
   E     D      D    E
  / \   / \    / \   / \
 E   D D   E  D   E E   D

Given the level and position of a person in the ancestor tree above, find the profession of the person. Note: in this tree first child is considered as left child, second - as right.

Example: For level = 3 and pos = 3, the output should be findProfession(level, pos) = "Doctor".

Constraints:

  • 1 ≤ level ≤ 30
  • 1 ≤ pos ≤ 2^(level - 1)

Note: this test is from codesignal.com

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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