What is the subword complexity function of this infinite word?

Claim 1. For any word $x\in\{0,1\}^*$, ($x$ is not a subword of $w$) iff ($11$ is a subword of $x$); i.e., the only words that are not subwords of $w$ are those that contain the subword $11$.

Proof:

  1. $x$ is not a subword of $w$ if $11$ is a subword of $x$

    Let $suffix(w_i)$ and $prefix(w_i)$ denote any suffix and prefix, respectively, of any of the $w_i$. Now, a word $x$ occurs as a subword of $w$ iff it is formed at the junction of some concatenation $(+)$ of $suffix(w_i) + prefix(w_i)$ during some iteration of the rewrite rule in the recursive definition of $w$. E.g., all length-$2$ words occur, except for $11$ -- the latter never occurs because $..1+1..$ cannot occur, as $1..$ is never a $prefix(w_i)$. Since $11$ doesn't occur as a subword in $w$, neither does any word in which $11$ occurs as a subword.

  2. $x$ is not a subword of $w$ only if $11$ is a subword of $x$

    (--to be completed--)

Claim 2. The number of words in $\{0,1\}^n$ that do not contain the subword $11$ is equal to the Fibonacci number $F_{n+2}=F_{n+1} + F_n$, with $F_0=0, F_1=1$.

Proof: See How many $N$ digits binary numbers can be formed where $0$ is not repeated. The same argument applies when $1$ (rather than $0$) is not repeated.

Claim 3. $\sigma_w(n) = F_{n+2}.$

Proof: Immediate from Claim 1 & Claim 2.

Claim 4. $\sigma_w^\mathrm{abelian}(n) = \left\lfloor\frac{n+3}{2}\right\rfloor.$

Proof: This follows from Claim 1 & Claim 2, together with the observation that for each $k$ in $\{0,1,2,...\left\lfloor\frac{n}{2}\right\rfloor\}$, there is a word in $\{0,1\}^n$ containing exactly $k$ $1$s and no $11$-subword, but that for any larger $k$ there is no such word.

Computations using Sage confirm these claims for small $n$, but the first-occurrence times of some relatively short words are infeasibly large, as suggested by the following table of results:

\begin{array}{|c|c||c|} n & \sigma_w(n) & \sigma_w^\mathrm{abelian}(n) & \mathrm{index\ of\ the\ 1st\ occurrence\ of\ }0^n \\ \hline 1&2&2&0 \\ 2&3&2&2 \\ 3&5&3&2 \\ 4&8&3&39 \\ 5&13&4&40360461 \\ 6&21^*&4^*&> 7854933623 \end{array}

$(^*)$ The longest prefix that my system can directly compute is $w_{55}$, which has length $7854933628$. Except for $0^6$, it contains all of the $21$ length-$6$ subwords that do not contain $11$.


Not a full answer, but probably a useful reference.

You mention that the integer sequence $$(0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, \ldots)$$ given by the consecutive entries in $w$ is not currently in OEIS. However, the sequence of positions of $1$ in this sequence, namely: $$ 1, 5, 7, 10, 14, 18, 20, 24, 26, 29, 33, 35, \dotsm $$ appears as A020942, First column of 3rd-order Zeckendorf array, in OEIS. Quoting OEIS

Any number $n$ has unique representation as a sum of terms from $\{1, 2, 3, 4, 6, 9, 13, 19, ...\}^{*}$ such that no two terms are adjacent or pen-adjacent; e.g., $7=6+1$. Sequence gives all $n$ where that representation involves $1$.

$^{(*)}\scriptsize\text{ These terms obey the recurrence equation $a(n) = a(n-1) + a(n-3)$.}$

Two references are given

[1] Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly 50, February 2012.

[2] C. Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly 33 (1995) 3-8.

Reference [1] gives interesting connections with the sequence of words $w_k$ on a $k$-letter alphabet defined as follows: \begin{align} w_0 &= a_0,\\ w_1 &= a_0a_1,\\ &\ \vdots\\ w_{k-1} &= a_0a_1 \dotsm a_{k-1} \end{align} and $w_i = w_{i-1}w_{i-k}$ for $i \geqslant k$. This makes this article a reasonable approach towards the solution of your problem.