# Solutions of certain meta-Fibonacci recurrences

Bartosz Sobolewski and Maciej Ulas

###### Abstract.

In this note we investigate the solutions of certain meta-Fibonacci
recurrences of the form $f(n)=f(n-f(n-1))+f(n-2)$ for various sets of initial
conditions. In the case when $f(n)=1$ for $n\leq 1$, we prove that the
resulting integer sequence is closely related to the function counting binary
partitions of a certain type.

###### Key words and phrases:

meta-Fibonacci sequence, recurrence sequence, automatic sequence, binary
partitions

The research of the authors is supported by the grant of the National Science
Centre (NCN), Poland, no. UMO-2019/34/E/ST1/00094

##  1\. Introduction

The Fibonacci sequence $(F_{n})_{n\in\mathbb{N}}$, defined as
$F_{0}=0,F_{1}=1$ and $F_{n}=F_{n-1}+F_{n-2},n\geq 2$, has many diverse
applications and is still investigated from different points of view. In the
literature, there are many various generalizations of this sequence, many of
which can be seen as subclasses of the class of so-called meta-Fibonacci
sequences. What is a meta-Fibonacci sequence? In the most general terms, it is
a solution of a recurrence relation of the form

(1) $f(n)=f(p(n))+f(q(n)),$

where $p(n),q(n)$ are certain expressions involving $n,f(n-1),\ldots,f(n-k)$
for some $k$. To get a sequence, we also need to specify certain initial
conditions $f(1),\ldots,f(i)$ (where $i$ depends on $p,q$). We note that the
class of sequences defined in this way is larger than the one introduced by
Conolly in [7].

The class of meta-Fibonacci sequences is very broad and (trivially) contains
the Fibonacci sequence (take $p(n)=n-1,q(n)=n-2$), the sequence of powers of
$2$ (take $p(n)=q(n)=n-1$ with $f(1)=1$), but also many exotic sequences. One
striking example is the Hofstadter sequence, which is defined in the following
way: $Q(1)=Q(2)=1$ and for $n\geq 3$ we have

$Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)).$

This sequence first appeared in the book [9] and since its invention has
attracted much attention.

In contrast to usual linear recurrence sequences, for certain initial
conditions, the corresponding meta-Fibonacci sequence may not be well defined
for all $n\in\mathbb{N}_{+}$. Indeed, if for some $n$ we have $p(n)\leq 0$ or
$q(n)\leq 0$ then the term with index $n$ can not be computed. Then we say
that the sequence dies. We get a typical example for
$p(n)=n-f(n-1),q(n)=n-f(n-2)$ with initial conditions $f(1)=2,f(2)=1$. Then
$f(3)=3,f(4)=5$ but we can not compute the value of $f(5)$ because $5-f(4)=0$
and $f(0)$ is not defined. The question if a given meta-Fibonacci sequence
dies is in general hard to answer. For example, it is still not known whether
the Hofstadter sequence $Q$ will live forever or die at some $n$. A common
belief is that the sequence is well defined for each $n\in\mathbb{N}_{+}$,
which is supported by calculations for $n\leq 10^{10}$. In order to eliminate
the problem with dying sequences, one can use the convention that the values
at negative indices are fixed. For example, Ruskey [16] discovered a solution
to Hofstadter’s $Q$-recurrence (with appropriate initial conditions and the
convention that $Q(n)=0$ for $n<0$) that includes the Fibonacci along indexes
lying in certain arithmetic progression.

An interesting variant of the Hofstadter sequence with perfectly predictable
behavior was proposed by Tanny [17]. The sequence starts with
$T(0)=T(1)=T(2)=1$ and for $n\geq 3$ we have

$T(n)=T(n-1-T(n-1))+T(n-2-T(n-2)).$

Tanny proved that this sequence is slow, well-defined for all $n\in\mathbb{N}$
and each positive integer appears as a value of $T(n)$. We say that a sequence
$(f(n))_{n\in\mathbb{N}}$ is slow if for each $n\in\mathbb{N}$ we have
$f(n+1)-f(n)\in\\{0,1\\}$. Some other constructions of slow meta-Fibonacci
sequences were presented in the literature (see for example [10]).

Browsing the literature concerning meta-Fibonacci recurrences, we have
observed that in every case studied so far both expressions $p(n),q(n)$ used
in the definition of the recurrence (1) contain at least one term of the form
$f(n-k)$ for some $k$. Moreover, in each case when the sequence is well-
understood, there is some $a\in\mathbb{N}_{+}$ such that for each
$b\in\\{0,\ldots,a-1\\}$, the subsequence $(f(an+b))_{n\in\mathbb{N}}$ is
bounded from above by a linear function in $n$ or is governed by a specific
linear recurrence sequence with exponential growth (with algebraic base).

This motivated us to ask the following question. Consider the recurrence (1)
with $p(n)=n-f(n-u)$ and $q(n)=n-v$, where $u,v$ are fixed positive integers,
namely

(2) $f(n)=f(n-f(n-u))+f(n-v).$

######  Question 1.1.

Can we expect the existence of a solution such that at least one of its
subsequences along some arithmetic progression is not a linear recurrence
sequence, neither is slow, nor unpredictable (chaotic)?

In general, any initial condition can be considered
$f(0),f(1),\ldots,f(u-1)\in\mathbb{N}_{+}$. The assumption that these values
are positive ensures that $n-f(n-u)<n$, which is necessary to compute $f(n)$
recursively. To avoid the situation in which the resulting sequence dies, we
assign a fixed value $c\in\mathbb{N}$ to terms with indices $n<0$.

The case $v=1$ is rather uninteresting in view of Question 1.1. Indeed, if
$c\geq 1$, then for any $u\geq 1$ the resulting sequence
$(f(n))_{n\in\mathbb{N}}$ is eventually an arithmetic progression. To see
this, note that the recurrence relation (2) implies that this sequence is
strictly increasing. If $f(n-u)\leq n$ for all $n\geq u$, then we must have
$f(n)=f(n-1)+1$ for sufficiently large $n$. On the other hand, if
$f(n_{0}-u)>n_{0}$ for some $n_{0}\in\mathbb{N}$, then it is easy to
inductively prove that $f(n)=f(n-1)+c$ for all $n\geq n_{0}$. The description
for $c=0$ is more complicated; however, experimental computations strongly
indicate that there exists some $d\geq 1$ (depending on the initial conditions
$f(0),f(1),\ldots,f(u-1)$) such that for $e=0,1,\ldots,d-1$ the subsequences
$(f(dn+e))_{n\in\mathbb{N}}$ are eventually arithmetic progressions.

Based on the above discussion, we investigate the problem stated for the next
“smallest” case, namely $u=1,v=2$. More precisely, let $a,b\in\mathbb{N}_{+}$
and consider the sequence ${\bf h}_{a,b}=(h_{a,b}(n))_{n\in\mathbb{N}}$, where

$h_{a,b}(n)=\begin{cases}\begin{array}[]{lcc}a&&n\leq 0,\\\ b&&n=1,\\\
h_{a,b}(n-h_{a,b}(n-1))+h_{a,b}(n-2)&&n>1.\end{array}\end{cases}$

We also define a related sequence ${\bf
g}_{a,b}=(g_{a,b}(n))_{n\in\mathbb{N}}$, where

$g_{a,b}(n)=\begin{cases}\begin{array}[]{lcc}0&&n<0,\\\ a&&n=0,\\\ b&&n=1,\\\
g_{a,b}(n-g_{a,b}(n-1))+g_{a,b}(n-2)&&n>1.\end{array}\end{cases}$

As we see the sequence ${\bf g}_{a,b}$ is governed by the same recurrence as
${\bf h}_{a,b}$ but with different initial conditions. There are striking
differences in the behavior between the sequences ${\bf h}_{a,b}$ and ${\bf
g}_{a,b}$ for various values of $a,b$. In particular, it turns out that for
$a=1$ (and any $b\geq 1$) the solution ${\bf h}_{a,b}$ satisfies the
requirements listed in Question 1.1.

Let us describe the contents of the paper in more detail. Section 2 provides
the necessary background information on automatic and regular sequences.

In Sections 3–5 we offer a detailed description of the sequence ${\bf
h}_{a,b}$.

Section 3 is devoted to the study of the particularly interesting case
$a=b=1$. We obtain $h_{1,1}(2n+1)=n+1$ but the solution along even indices can
be presented as a sum of functions counting certain partitions into powers of
two (a rather surprising property, given the definition of ${\bf h}_{1,1}$).
In particular, the sequence ${\bf h}_{1,1}$ does not satisfy a linear
recurrence equation and its ordinary generating function is transcendental
over the rational function field. Moreover, we also prove that the sequence
obtained by reduction modulo 2 of the sequence ${\bf h}_{1,1}$ is 2-automatic.

In Section 4 we analyze the case $a=1,b>1$. The sequence $h_{1,b}$ displays
similar behavior as $h_{1,1}$. The main result is that $h_{1,b}(2n)=n+1$ and
that $h_{1,b}(2n+1)$ is a linear combination of the sequence
$(bin(n))_{n\in\mathbb{N}}$ (which counts partitions into power of two) and
the sequence ${\bf h}_{1,1}$. Section 5 deals with the remaining case $a>1$.
We prove for all $b\in\mathbb{N}_{+}$ the subsequences $h_{a,b}(2n)$ and
$h_{a,b}(2n+1)$ are eventually arithmetic progressions.

In Section 6 we focus on the sequence ${\bf g}_{a,b}$. We prove that for any
initial conditions $a,b\in\mathbb{N}_{+}$, the behavior of ${\bf g}_{a,b}$ is
completely predictable. More precisely, depending on the parity of $a,b$ the
subsequences $g_{a,b}(2n)$ and $g_{a,b}(2n+1)$ are eventually: constant,
linear or satisfy linear recurrence equation of order bounded by
$\operatorname{max}\\{a,b\\}$. Finally, in the last section we formulate some
questions and problems which may stimulate further research.

##  2\. Preliminaries on automatic and regular sequences

In this section, we recall the definition and some properties of automatic and
regular sequences, which will be useful later in the paper. These sequences
appear naturally in various branches of mathematics, such as number theory,
theoretical computer science, symbolic dynamics, etc. For a detailed treatment
of this topic, we refer the reader to the monograph by Allouche and Shallit
[1] and their papers [2, 3].

Let $k\geq 2$ be a fixed integer. A sequence
$\mathbf{a}=(a_{n})_{n\in\mathbb{N}}$ is called $k$-automatic if its
$k$-kernel, namely

$K_{k}(\mathbf{a})=\\{(a_{k^{j}n+i})_{n\in\mathbb{N}}:j\in\mathbb{N},0\leq
i<k^{j}\\},$

is a finite set. Equivalently, $\mathbf{a}$ is $k$-automatic if there exists a
deterministic finite automaton with output (DFAO) which reads the canonical
base-$k$ representation of $n$ and outputs $a_{n}$.

One of the most famous automatic sequences is the Prouhet-Thue-Morse sequence
$\mathbf{t}=(t_{n})_{n\in\mathbb{N}}$ (the PTM sequence for short). It is
2-automatic sequence defined in the following way: $t_{0}=1$ and

$t_{2n}=t_{n},\quad t_{2n+1}=-t_{n},\quad n\in\mathbb{N}.$

From this description it is clear that
$K_{k}(\mathbf{t})=\\{\mathbf{t},-\mathbf{t}\\}$. Equivalently, the sequence
is generated by the DFAO in Figure 1. To generate $t_{n}$, one moves between
the states (symbolized by nodes) according to subsequent digits in the binary
representation of $n$. After the last digit has been read, the DFAO returns
the output corresponding to the final state.

$1$start$-1$0110 Figure 1. A DFAO generating the PTM sequence.

A famous result of Christol [5] relates the automaticity of sequences and the
algebraicity of generating functions over finite fields.

######  Theorem 2.1.

Let $p$ be a prime number and $\mathbb{F}_{q}$ a finite field of order
$q=p^{k}$, where $k\in\mathbb{N}_{+}$. Let
$\mathbf{a}=(a_{n})_{n\in\mathbb{N}}$ be a sequence with values in
$\mathbb{F}_{q}$ and $A(X)=\sum_{n=0}^{\infty}a_{n}X^{n}$ be its generating
function. Then $\mathbf{a}$ is $p$-automatic if and only if $A(X)$ is
algebraic over the field of rational functions $\mathbb{F}_{q}(X)$.

A natural generalization of $k$-automatic sequences are so-called $k$-regular
sequences. More precisely, assume that a sequence
$\mathbf{a}=(a_{n})_{n\in\mathbb{N}}$ takes values in a $\mathbb{Z}$-module
$R$. Then $\mathbf{a}$ is $k$-regular if there exist finitely many sequences
$\mathbf{a}_{i}=(a_{i}(n))_{n\in\mathbb{N}}$ with values in $R$ such that each
sequence in $K_{k}(\mathbf{a})$ is a $\mathbb{Z}$-linear combination of the
$\mathbf{a}_{i}$. In other words, the $\mathbb{Z}$-submodule generated by
$K_{k}(\mathbf{a})$ is finitely generated.

It is rather easy to check that $k$-automatic sequences are precisely
$k$-regular sequences taking only finitely many values. The following result
[2, Theorem 2.10] asserts that the growth of a $k$-regular sequence is at most
polynomial.

######  Theorem 2.2.

Let $(a_{n})_{n\in\mathbb{N}}$ be a $k$-regular sequence with values in
$\mathbb{C}$. Then there exists a constant $C$ such that $a_{n}=O(n^{C})$.

##  3\. Analysis of the sequence ${\bf h}_{1,1}$

In this section, we analyze the behavior of the sequence
$(h_{1,1}(n))_{n\in\mathbb{N}}$. We write $h(n)=h_{1,1}(n)$ and in the sequel,
we consider the sequence ${\bf h}=(h(n))_{n\in\mathbb{N}}$. The terms $h(n)$
for $n=0,1,2,\ldots,25$ are as follows:

$1,1,2,2,4,3,6,4,10,5,13,6,19,7,23,8,33,9,38,10,51,11,57,12,76,13,\ldots.$

To begin, we prove that the terms $h(2n)$ and $h(2n+1)$ satisfy simple
formulas, eliminating the need to calculate the nested term $h(n-h(n-1))$.

######  Theorem 3.1.

The sequence $\mathbf{h}$ satisfies the following recurrence relations:
$h(0)=h(1)=1$ and for all $n\in\mathbb{N}$ we have

$\displaystyle h(2n+1)$ $\displaystyle=n+1,$ $\displaystyle h(2n+2)$
$\displaystyle=h(2n)+h(n+1)$

###### Proof.

We first use induction on $n$ to simultaneously prove that $h(2n)\geq 2n$ and
$h(2n+1)=n+1$. It is clear that this claim is true for $n=0,1,2$. Let us
suppose that this holds for all numbers $<2n$. Then we have

$h(2n)=h(2n-h(2n-1))+h(2n-2)=h(n)+h(2n-2).$

We also see that the result will follow as soon as our claim is proved.

If $2|n$, then from our assumption $h(n)\geq n$, and thus for $n\geq 2$ we get

$h(2n)\geq n+2(n-1)=3n-2\geq 2n.$

If $2\nmid n$, then for $n\geq 2$ we have

$h(2n)\geq\frac{n+1}{2}+2n-2\geq 2n,$

and we obtain the first part of our claim. To obtain the second part, we note
that

$h(2n+1)=h(2n+1-h(2n))+h(2n-1)=1+n$

because $2n+1-h(2n)\leq 1$. The result follows. ∎

Although very simple, the above result has several nice applications. We start
with the following.

######  Corollary 3.2.

For all $n\in\mathbb{N}$ we have

$h(2n)=\sum_{i=0}^{n}h(i).$

Furthermore, we obtain interesting identities involving the terms of the
Prouhet-Thue-Morse sequence. For $k\in\mathbb{N}$ and $n\geq 2^{k+1}-2$ let us
define

(3) $F(k,n)=\sum_{i=0}^{2^{k}-1}t_{i}h(n-2i).$

######  Theorem 3.3.

For all $k\in\mathbb{N}$ and $n\geq 2^{k+1}-2$ we have the following
relations:

$\displaystyle F(k,2n)$ $\displaystyle=\begin{cases}h(2n)&\text{if }k=0,\\\
F(k-1,n)&\text{if }k\geq 1,\end{cases}$ $\displaystyle F(k,2n+1)$
$\displaystyle=\begin{cases}n+1&\text{if }k=0,\\\ 1&\text{if }k=1,\\\
0&\text{if }k\geq 2.\end{cases}$

In particular, for any $n\in\mathbb{N}_{+}$, we get the identity

(4) $\sum_{i=0}^{2^{k}-1}t_{i}h(2^{k+1}n+2^{k}-2i)=n+1.$

###### Proof.

The formula $F(0,2n)=h(2n)$ follows from the definition. Now, fix
$n\in\mathbb{N}$ and write $f(n,i)=h(n-2i)$. Theorem 3.1 implies that we have

$f(2n,2i)=f(2n,2i+1)+f(n,i).$

Therefore, for $k\geq 1$ we get

$\displaystyle F(k,2n)$
$\displaystyle=\sum_{i=0}^{2^{k}-1}t_{i}f(2n,i)=\sum_{i=0}^{2^{k-1}-1}\left[t_{2i}f(2n,2i)+t_{2i+1}f(2n,2i+1)\right]$
$\displaystyle=\sum_{i=0}^{2^{k-1}-1}t_{i}\left[f(2n,2i)-f(2n,2i+1)\right]=\sum_{i=0}^{2^{k-1}-1}t_{i}f(n,i)=F(k-1,n).$

Moving on to $F(k,2n+1)$, we have $F(0,2n+1)=h(2n+1)=n+1$ by Theorem 3.1.
Similarly,

$F(1,2n+1)=h(2n+1)-h(2n-1)=n+1-n=1.$

For $k\geq 2$ we have

$F(k,2n+1)=\sum_{i=0}^{2^{k}-1}t_{i}h(2(n-i)+1)=\sum_{i=0}^{2^{k}-1}t_{i}(n-i+1)=0,$

where the last equality follows from the following identity [4], valid for all
$m<k$:

(5) $\sum_{i=0}^{2^{k}-1}t_{i}i^{m}=0.$

Finally, (4) is obtained by applying $k$ times the relation
$F(k,2n)=F(k-1,n)$. ∎

As an immediate consequence, we get the following corollary.

######  Corollary 3.4.

There is no polynomial $P\in\mathbb{Z}[x]$ such that $h(2n)=P(n)$ for
infinitely many $n\in\mathbb{N}$.

###### Proof.

As a consequence of (5), for each polynomial $P\in\mathbb{Z}[x]$ of degree
$<k$ we get that $\sum_{i=0}^{2^{k}-1}t_{i}P(x+i)=0$.

Let us suppose that there is a polynomial $P\in\mathbb{Z}[x]$ of degree
$d\in\mathbb{N}_{+}$ satisfying $h(2n)=P(n)$ for $n\in\mathbb{N}$. However,
from (4) for fixed $n\in\mathbb{N}$ and $k>d$ we would have

$n+1=\sum_{i=0}^{2^{k-1}-1}t_{i}Q(i)=0,$

where $Q\in\mathbb{Z}[x]$ satisfies $Q(x)=P(2^{k+1}n+2^{k}-2x)$. We get a
contradiction. ∎

In the next result, we establish a functional equation for the ordinary
generating function of the sequence ${\bf h}$, namely

$H(x)=\sum_{n=0}^{\infty}h(n)x^{n}.$

######  Theorem 3.5.

The series $H$ satisfies a Mahler-type functional equation of the form

$\frac{1}{1-x^{2}}H(x^{2})-H(x)+\frac{x}{(1-x^{2})^{2}}=0.$

###### Proof.

We have the identities

$\displaystyle\frac{1}{2}(H(x)+H(-x))$
$\displaystyle=\sum_{n=0}^{\infty}h(2n)x^{2n}=\sum_{n=0}^{\infty}\left(\sum_{i=0}^{n}h(i)\right)x^{2n}=\frac{1}{1-x^{2}}H(x^{2}),$
$\displaystyle\frac{1}{2}(H(x)-H(-x))$
$\displaystyle=\sum_{n=0}^{\infty}h(2n+1)x^{2n+1}=\sum_{n=0}^{\infty}(n+1)x^{2n+1}=\frac{x}{(1-x^{2})^{2}}.$

If we add side-by-side of the above equalities, we obtain the statement. ∎

As an immediate consequence, we get the following corollary.

######  Corollary 3.6.

The generating function $H(x)$ of the sequence ${\bf h}$ is transcendental
over $\mathbb{Q}(x)$. In particular, neither the sequence ${\bf h}$ nor its
subsequence $(h(2n))_{n\in\mathbb{N}}$ are linear recurrence sequences.

###### Proof.

We treat the series $H$ as a element of
$\mathbb{Z}[[x]]\subset\mathbb{C}[[x]]$. Let us recall the Nishioka theorem
[14] (see also [15]) which says that if $f\in\mathbb{C}[[x]]$ satisfies a
functional equation of the form $f(x^{d})=\varphi(x,f(x))$, where
$\varphi\in\mathbb{C}(x,y)$, then $f$ is either rational or transcendental. In
our case, $d=2$ and

$\varphi(x,y)=(1-x^{2})y-\frac{x}{1-x^{2}}.$

Thus, to get the result, it is enough to prove that the series $H$ is not
rational. To see this, it suffices to consider the reduction modulo 2 of $H$,
i.e., the series $G(x)=H(x)\mkern 4.0mu({\operator@font mod}\mkern 6.0mu2)$.
The series $G$ is an element of $\mathbb{F}_{2}[[x]]$ and satisfies the
algebraic equation

(6) $(1-x^{2})G(x)^{2}+(1-x^{2})^{2}G(x)+x=0$

(this is consequence a of the congruence $G(x^{2})\equiv G(x)^{2}\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)$). However, it is easy to check that
the polynomial $P(x,y)=(1-x^{2})y^{2}+(1-x^{2})^{2}y+x$ is irreducible in
$\mathbb{F}_{2}[x,y]$. We thus see that the series $G$ is not rational over
$\mathbb{F}_{2}(x)$ and thus $H$ can not be rational. The Nishioka theorem
implies its transcendentality over $\mathbb{C}(x)$ and our theorem is proved.
∎

Before we prove our next result, we recall some basic facts about the binary
partition function. Let us write

$B(x)=\prod_{n=0}^{\infty}\frac{1}{1-x^{2^{n}}}=\sum_{n=0}^{\infty}bin(n)x^{n}.$

The number $bin(n)$ counts the representations of an integer $n$ in the form
$n=\sum_{i=1}^{k}2^{r_{i}}$, where $r_{i}\in\mathbb{N}$ for $i=1\ldots,k$ and
$r_{1}\leq r_{2}\leq\ldots\leq r_{k}$. In other words, $bin(n)$ counts the
number of partitions of $n$ with parts in the set
$\\{2^{i}:\;i\in\mathbb{N}\\}$. We can deduce that $B$ satisfies the
functional equation $(1-x)B(x)=B(x^{2})$ and the sequence
$(bin(n))_{n\in\mathbb{N}}$ can be defined recursively as follows:

$bin(0)=1,\quad bin(2n)=bin(2n-1)+bin(n),\quad bin(2n+1)=bin(2n).$

This sequence was introduced by Euler but it seems that the first non-trivial
results were proved by Churchhouse in [6]. The most important fact for our
purposes is that the value of $bin(n)$ grows exponentially. More precisely,
Mahler proved that $\log_{2}bin(n)\sim\frac{1}{2}(\log_{2}n)^{2}$. For a proof
of this fact, see [12].

On a related note, $B$ is the multiplicative inverse of the generating
function $T$ for the PTM sequence:

$T(x)=\sum_{n=0}^{\infty}t_{n}x^{n}=\prod_{n=0}^{\infty}(1-x^{2^{n}})=\frac{1}{B(x)}.$

We are ready to prove the following

######  Theorem 3.7.

The subsequence $(h(2n))_{n\in\mathbb{N}}$ and thus the whole sequence ${\bf
h}$ is not $k$-regular for any $k\in\mathbb{N}_{\geq 2}$.

###### Proof.

The functional equation for $H$ can be rewritten as

$H(x)=\frac{1}{1-x^{2}}H(x^{2})+\frac{x}{(1-x^{2})^{2}}.$

Iterating this equation by induction on $k$ one can easily prove that

$H(x)=\left(\prod_{i=1}^{k}\frac{1}{1-x^{2^{i}}}\right)H(x^{2^{k}})+\sum_{i=1}^{k}\frac{x^{2^{i-1}}}{\prod_{j=1}^{i}(1-x^{2^{j}})}\cdot\frac{1}{1-x^{2^{i}}}.$

Thus, taking the limit $k\rightarrow+\infty$, we get the equality
$H(x)=\overline{H}(x)+\sum_{i=1}^{\infty}\overline{H}_{i}(x)$, where

$\displaystyle\overline{H}(x)$
$\displaystyle=\prod_{i=1}^{\infty}\frac{1}{1-x^{2^{i}}}=B(x^{2}),$
$\displaystyle\overline{H}_{i}(x)$
$\displaystyle=\frac{x^{2^{i-1}}}{\prod_{j=1}^{i}(1-x^{2^{j}})}\cdot\frac{1}{1-x^{2^{i}}}.$

Let us note that $n$-th coefficient in the power series expansion of
$\overline{H}$ is equal to 0 if $n$ is odd and is just $bin(n/2)$ if the
number $n$ is even. In particular, the growth of the coefficients is
exponential.

On the other hand, it is clear that coefficients of the power series expansion
of the second part in the above sum are non-negative. More precisely, write
$\overline{H}_{i}(x)=\sum_{n=0}^{\infty}c_{i}(n)x^{i}$, where $c_{i}(n)$ is
the number of partitions of $n-2^{i-1}$ into elements of the set
$\\{2,\ldots,2^{i}\\}$, where the last element $2^{i}$ can take two colors.
Therefore, if we write

$\sum_{k=1}^{\infty}\overline{H}_{i}(x)=\sum_{n=0}^{\infty}d(n)x^{n},$

then $d(n)=\sum_{i=1}^{\lfloor\log_{2}n\rfloor+1}c_{i}(n-2^{i-1})$. Therefore,
we have $h(2n)=bin(n)+d(2n)\geq bin(n)$ and the sequence
$(h(2n))_{n\in\mathbb{N}}$ has exponential growth and can not be $k$-regular
for any $k$. It is clear that the same is true for the whole sequence ${\bf
h}$. ∎

To conclude this section, we consider the sequence $(h(n))_{n\in\mathbb{N}}$
reduced modulo $2$. Let us write $r(n)=h(n)\mkern 4.0mu({\operator@font
mod}\mkern 6.0mu2)$. As a consequence of the functional equation for $H$ we
immediately deduce that this sequence is $2$-automatic.

######  Theorem 3.8.

The sequence $(r(n))_{n\in\mathbb{N}}$ is 2-automatic.

###### Proof.

The generating function (over $\mathbb{F}_{2}(x))$ of the sequence
$(r(n))_{n\in\mathbb{N}}$ is just $G(x)=H(x)\mkern 4.0mu({\operator@font
mod}\mkern 6.0mu2)$ and satisfies the algebraic equation (6) over
$\mathbb{F}_{2}(x)$. From Christol’s theorem, we get the result. ∎

By following the proof of Christol’s theorem, one can derive from equation (6)
a DFAO generating the sequence $(r(n))_{n\in\mathbb{N}}$. We are going to
achieve the same goal through a more direct approach. Since $r(2n+1)\equiv
n+1\pmod{2}$, we are going to focus on the more interesting subsequence
$(r(2n))_{n\in\mathbb{N}}$.

######  Theorem 3.9.

We have $(r(8n+4))_{n\in\mathbb{N}}=\overline{0,1,1,0}$ and
$(r(16n+8))_{n\in\mathbb{N}}=\overline{0,0,1,1}$. Moreover, for all
$n\in\mathbb{N}$ we have the following relations:

$\displaystyle r(8n+2)$ $\displaystyle=1-r(8n),$ $\displaystyle r(8n+6)$
$\displaystyle=r(8n+4),$ $\displaystyle r(32n)$ $\displaystyle=r(16n),$
$\displaystyle r(32n+16)$ $\displaystyle=1-r(16n+8).$

###### Proof.

We are going to apply the relations

(7) $\displaystyle r(2n+1)$ $\displaystyle\equiv n+1\pmod{2},$ (8)
$\displaystyle r(2n+2)$ $\displaystyle\equiv r(2n)+r(n+1)\pmod{2},$

which follow directly from Theorem 3.1.

We obtain the congruences

$\displaystyle r(8n+2)$ $\displaystyle\equiv r(8n)+r(4n+1)\equiv
r(8n)+2n+1\equiv r(8n)+1\pmod{2},$ $\displaystyle r(8n+6)$
$\displaystyle\equiv r(8n+4)+r(4n+3)\equiv r(8n+4)+2n+2\equiv
r(8n+4)\pmod{2},$

which immediately give the first two claimed equalities.

We move on to the periodicity of $(r(8n+4))_{n\in\mathbb{N}}$ and
$(r(16n+8))_{n\in\mathbb{N}}$. Applying (8) repeatedly, we get for
$n\in\mathbb{N}$ and $j\in\\{0,1,2,3\\}$, the congruence

$r(32(n+1)+8j+4)\equiv r(32n+8j+4)+\sum_{i=0}^{15}r(16(n+1)+4j+2-i)\pmod{2}.$

Using the notation $F(k,n)$ as in (3), by Theorem 3.3 we get

$\displaystyle\sum_{i=0}^{15}r(16(n+1)+4j+2-i)$ $\displaystyle\equiv
F(3,16(n+1)+4j+2)+F(3,16(n+1)+4j+1)$ $\displaystyle\equiv
F(2,8(n+1)+2j+1)\equiv 0\pmod{2}.$

This proves that $(r(8n+4))_{n\in\mathbb{N}}$ has period $4$ and direct
computation shows that $(r(8n+4))_{n\in\mathbb{N}}=\overline{0,1,1,0}$.
Therefore, we also have $(r(8n+6))_{n\in\mathbb{N}}=\overline{0,1,1,0}$ so the
congruence $r(16n+8)\equiv r(16n+6)+r(8n+4)$ implies
$(r(16n+8))_{n\in\mathbb{N}}=\overline{0,0,1,1}$.

It remains to show the last two equalities. For $n=0$ we obviously have
$r(32n)=r(16n)$, while for $n\geq 1$ we get

$r(32n)\equiv r(32n-2)+r(16n)\equiv r(8(4n-1)+6)+r(16n)\equiv r(16n)\pmod{2}.$

Similarly, for all $n\in\mathbb{N}$ we have

$r(32n+16)\equiv r(32n+14)+r(16n+8)\equiv 1+r(16n+8)\pmod{2},$

and the proof is complete. ∎

From these relations, we can derive a DFAO generating the sequence
$(r(2n))_{n\in\mathbb{N}}$ (reading the input starting with the least
significant digit of $n$). By a simple modification one can also obtain a DFAO
that generates the whole sequence $(r(n))_{n\in\mathbb{N}}$.

$1$start$1$$0$$1$$0$$0$$1$$0$$0$$1$$1$$0$$0$$1$$0$$1$$0$$1$$0$$1$$0$$1$$0$$1$$0$$1$$0$$1$$0$$1$$0$$1$$0,1$$0,1$$0$$1$$0,1$$0,1$
Figure 2. A DFAO that generates the sequence $(r(2n))_{n\in\mathbb{N}}$.

##  4\. Analysis of the sequence ${\bf h}_{1,b}$ with $b\geq 2$

The analysis performed in Section 3 (more precisely, Theorem 3.7) revealed a
strong connection of an even indexed subsequence of ${\bf h}$ with sequences
counting certain binary partitions. Moreover, we proved that the sequence
${\bf h}$ is neither $k$-regular for any $k$ nor a linear recurrence sequence.
We show that a similar phenomenon holds for the sequence ${\bf h}_{1,b}$ with
$b\geq 2$. Based on our experience with the sequence ${\bf h}$ and numerical
computations, we have observed the following generalization of Theorem 3.1.

######  Theorem 4.1.

For all $n\in\mathbb{N}$ we have the recurrence relations

$\displaystyle h_{1,b}(2n)$ $\displaystyle=n+1,$ $\displaystyle h_{1,b}(2n+1)$
$\displaystyle=h_{1,b}(n)+h_{1,b}(2n-1),\quad n\geq 1$

and the identity

$h_{1,b}(2n+1)=b-1+\sum_{i=0}^{n}h_{1,b}(i).$

###### Proof.

The proof is by induction on $n$ and is very similar to the proof of Theorem
3.1. More precisely, we first simultaneously prove that $h_{1,b}(2n)=n+1$ and
$h_{1,b}(2n-1)\geq 2n$. This is clearly true for $n=0,1,2$. Suppose that this
is true for all positive integers $\leq n-1$. We then have

$h_{1,b}(2n)=h_{1,b}(2n-h_{1,b}(2n-1))+h_{1,b}(2n-2)=1+n$

and

$h_{1,b}(2n+1)=h_{1,b}(2n+1-h_{1,b}(2n))+h_{1,b}(2n-1)=h_{1,b}(n)+h_{1,b}(2n-1).$

If $n$ is odd then we have

$h_{1,b}(2n+1)\geq h_{1,b}\left(2\frac{n+1}{2}-1\right)+2n\geq
2\frac{n+1}{2}+2n=3n+1\geq 2n+2.$

If $n$ is even then

$h_{1,b}(n)+h_{1,b}(2n-1)\geq\frac{n}{2}+1+2n\geq 2n+2$

and we are done.

To get an expression for $h_{1,b}(2n+1)$ in the form of a sum, we again use
induction. The statement is true for $n=0$. Suppose that it holds for $n-1$,
where $n\geq 1$. Then

$\displaystyle h_{1,b}(2n+1)$
$\displaystyle=h_{1,b}(2n+1-h_{1,b}(2n))+h_{1,b}(2n-1)=h_{1,b}(n)+h_{1,b}(2n-1)$
$\displaystyle=h_{1,b}(n)+\sum_{i=0}^{n-1}h_{1,b}(i)+b-1=\sum_{i=0}^{n}h_{1,b}(i)+b-1,$

and the result follows. ∎

Using the recurrence relation satisfied by the sequence ${\bf h}_{1,b}$ and
performing the same type of reasoning as in the proof of Theorem 3.5 we get
the following.

######  Theorem 4.2.

Let $b\in\mathbb{N}_{\geq 2}$ and put
$H_{b}(x)=\sum_{n=0}^{\infty}h_{1,b}(n)x^{n}$. Then the series $H_{b}$
satisfies the functional equation

$H_{b}(x)=\frac{x}{1-x^{2}}H_{b}(x^{2})+\frac{(b-1)x}{1-x^{2}}+\frac{1}{(1-x^{2})^{2}}.$

Analogously to Corollary 3.6, we get that $H_{b}$ is transcendental.

######  Corollary 4.3.

The generating function $H_{b}(x)=\sum_{n=0}^{\infty}h_{1,b}(n)x^{n}$ of the
sequence ${\bf h}_{1,b}$ is transcendental over $\mathbb{Q}(x)$.

###### Proof.

The proof goes exactly as in the case of Corollary 3.6. This time, to apply
the Nishioka theorem, we note that $\varphi_{b}(x,H_{b}(x))=H_{b}(x^{2})$,
where

$\varphi_{b}(x,y)=\frac{1-x^{2}}{x}y+1-b-\frac{1}{x(1-x^{2})}.$

As before, it is enough to prove non-rationality of the series $H_{b}$. Again,
we consider $G_{b}=H_{b}\mkern 4.0mu({\operator@font mod}\mkern 6.0mu2)$. Note
that $G_{b}$ satisfies $f_{b}(x,G_{b}(x))=0$ (in $\mathbb{F}_{2}[[x]]$) for

$f_{b}(x,y)=x(1-x^{2})y^{2}-(1-x^{2})^{2}y+(b-1)x(1-x^{2})+1.$

However, one can easily check that the polynomials $f_{b}$ are irreducible in
$\mathbb{F}_{2}[x,y]$ and thus $G_{b}$ is not a rational function in
$\mathbb{F}_{2}(x)$ for any value of $b\in\mathbb{N}_{+}$. Thus, $H_{b}$
cannot be a rational function over $\mathbb{Q}(x)$. ∎

As an application of Corollary 4.2 we get the following (a bit) unexpected
result, linking the sequences $\mathbf{h}_{1,b}$ for various $b$.

######  Theorem 4.4.

For all $n\in\mathbb{N}$ we have

$h_{1,2}(n)=h_{1,1}(n+1)$

More generally, for $b\in\mathbb{N}_{\geq 2}$ and $n\in\mathbb{N}$ we have the
identity

$h_{1,b}(2n+1)=(b-2)bin(n+1)+h_{1,1}(2n+2).$

###### Proof.

The first claim holds for $n=0,1$ by definition, while for $n\geq 2$ it
follows from the fact that the sequences $\mathbf{h}_{1,1}$ and
$\mathbf{h}_{1,2}$ are defined by the same recurrence.

To obtain the second required equality, we use the generating function
approach and first prove that $h_{1,b+1}(2n+1)-h_{1,b}(2n+1)=bin(n+1)$. Let us
note that by Corollary 4.2, the series $W(x)=H_{b+1}(x)-H_{b}(x)$ satisfies
the functional equation

$W(x)=\frac{x}{1-x^{2}}W(x^{2})+\frac{x}{1-x^{2}}.$

Due to the equality $h_{1,b}(2n)=n+1$ we get that $W(x)=-W(-x)$. Next, let us
denote $U(x)=\sum_{n=0}^{\infty}bin(n+1)x^{2n+1}$ and consider
$B(x)=\sum_{n=0}^{\infty}bin(n)x^{n}$. Note that $B(x^{2})=xU(x)+1$ and recall
the functional equation for $B$ has the form $(1-x)B(x)=B(x^{2})$. Thus, the
series $U(x)$ satisfies the functional equation

$U(x)=\frac{x}{1-x^{2}}U(x^{2})+\frac{x}{1-x^{2}},$

which is precisely the equation satisfied by $W(x)$. Because $W(0)=U(0)=1$ we
have $W(x)=U(x)$ and hence the coefficients in both series are equal.

To get the general statement, we sum the equalities
$h_{1,k+1}(2n+1)-h_{1,k}(2n+1)=bin(n+1)$ from $k=2$ to $k=b-1$, and get

$h_{1,b}(2n+1)-h_{1,2}(2n+1)=\sum_{k=2}^{b-1}(h_{1,k+1}(2n+1)-h_{1,k}(2n+1))=(b-2)bin(n+1).$

Using the equality $h_{1,2}(2n+1)=h_{1,1}(2n+2)$ proved earlier, we get the
result.

∎

##  5\. Analysis of the sequence ${\bf h}_{a,b}$ with $a\geq 2$

The behavior of the sequence $\mathbf{h}_{a,b}$ in the remaining case $a\geq
2$ is rather trivial, as in each case the subsequences $h_{a,b}(2n)$ and
$h_{a,b}(2n+1)$ are eventually arithmetic progressions. In the following, we
provide explicit formulas depending on $a,b$.

######  Theorem 5.1.

Assume that $a\geq 2$ and $b\geq 2$. Then for all $n\in\mathbb{N}$ we have

$\displaystyle h_{a,b}(2n)$ $\displaystyle=(n+1)a,$ $\displaystyle
h_{a,b}(2n+1)$ $\displaystyle=na+b.$

###### Proof.

We prove both equalities simultaneously by induction on $n$. The case $n=0$ is
contained in the definition of $\mathbf{h}_{a,b}$. For $n\geq 1$ we have

$h_{a,b}(2n)=h_{a,b}(2n-h_{a,b}(2n-1))+h_{a,b}(2n-2)=a+na=(n+1)a,$

where we have used

$2n-h_{a,b}(2n-1)=2n-(n-1)a-b\leq 0.$

Similarly,

$h_{a,b}(2n+1)=h_{a,b}(2n+1-h_{a,b}(2n))+h_{a,b}(2n-1)=a+(n-1)a+b=na+b.$

∎

In the following results, the proofs also rely on easy induction and are
omitted.

######  Theorem 5.2.

Assume that $a\geq 3$ and $b=1$. Then $h_{a,1}(0)=a$ and for all
$n\in\mathbb{N}_{+}$ we have

$h_{a,1}(n)=\left\lfloor\frac{n}{2}\right\rfloor a+1.$

######  Theorem 5.3.

We have $h_{2,1}(0)=2,h_{2,1}(1)=1,h_{2,1}(2)=h_{2,1}(3)=3$ and for all
$n\in\mathbb{N}_{\geq 2}$ the equalities

$\displaystyle h_{2,1}(2n)$ $\displaystyle=3n-2,$ $\displaystyle
h_{2,1}(2n+1)$ $\displaystyle=2n.$

##  6\. Analysis of the sequence $\mathbf{g}_{a,b}$

In this section, we consider the sequence
$\mathbf{g}_{a,b}=(g_{a,b}(n))_{n\in\mathbb{N}}$. It turns out that in each
case, one of the subsequences $(g_{a,b}(2n))_{n\in\mathbb{N}}$ and
$(g_{a,b}(2n+1))_{n\in\mathbb{N}}$ is eventually constant, while the other
eventually satisfies a linear recurrence.

We first state a useful observation, which is an immediate consequence of the
recursive definition of $g_{a,b}$.

######  Lemma 6.1.

The sequences $(g_{a,b}(2n))_{n\in\mathbb{N}}$ and
$(g_{a,b}(2n+1))_{n\in\mathbb{N}}$ are nondecreasing.

In the following series of results we succesively consider various cases
$a,b$.

######  Theorem 6.2.

Assume that either $a=b\geq 2$ are even or $a>b\geq 2$. Then for all
$n\in\mathbb{N}$ we have

$\displaystyle g_{a,b}(2n+1)$ $\displaystyle=b,$ $\displaystyle g_{a,b}(2n+2)$
$\displaystyle=g_{a,b}(2n+2-b)+g_{a,b}(2n).$

In particular, we have

$g_{a,b}(2n)=\begin{cases}a&\text{if }n<\lfloor b/2\rfloor,\\\
a+\left(n-\lfloor b/2\rfloor\right)b&\text{if }b\text{ is odd and
}n\geq\lfloor b/2\rfloor,\\\ 2^{n}a&\text{if }b=2.\end{cases}$

###### Proof.

Treating $a,b$ as fixed values, for simplicity, we will write $g=g_{a,b}$. We
will prove by induction on $n$ that $g(2n+1)=b$ and $g(2n)>2n+1$ for all
$n\in\mathbb{N}$, from which the first part of the assertion follows. The case
$n=0$ is contained in the definition of $g$. For $n\geq 1$ we have

$g(2n+1)=g(2n+1-g(2n))+g(2n-1)=b,$

where we used the induction hypothesis $g(2n)>2n+1$.

At the same time, when $2n<b$, we get $a>2n+1$, which implies

(9) $g(2n)\geq g(0)=a>2n+1.$

When $2n\geq b$, we use the induction hypothesis to obtain

$g(2n)=g(2n-g(2n-1))+g(2n-2)>g(2n-b)+2n-1.$

Since $g(2n-b)\geq 2$ by Lemma 6.1, our claim is proved.

The expressions for $g(2n)$ in particular cases quickly follow from the
general one. ∎

######  Theorem 6.3.

Assume that either $b=a\geq 3$ are odd or $b>a\geq 2$. Then for all
$n\in\mathbb{N}$ we have

$\displaystyle g_{a,b}(2n)$ $\displaystyle=a,$ $\displaystyle g_{a,b}(2n+3)$
$\displaystyle=g_{a,b}(2n+3-a)+g_{a,b}(2n+1).$

In particular, we have

$g_{a,b}(2n+1)=\begin{cases}b&\text{if }n<\lfloor a/2\rfloor,\\\
b+\left(n+1-\lfloor a/2\rfloor\right)a&\text{if }a\text{ is odd and
}n\geq\lfloor a/2\rfloor,\\\ 2^{n}b&\text{if }a=2.\end{cases}$

###### Proof.

The reasoning is based on showing that $g(2n)=a$ and $g(2n+1)>2n+2$ for all
$n\in\mathbb{N}$. This is done in the same way as in the proof of Theorem 6.2.
∎

By comparing the formulas in Theorem 6.2 and 6.3, we find that for $a>b\geq 2$
the sequences $(g_{a,b}(n))_{n\in\mathbb{N}}$ and
$(g_{b,a}(n))_{n\in\mathbb{N}}$ are a shift of one another, where the
direction of the shift depends on the parity of $b$. We will, however, prove
this corollary in a different way, which exhibits a more intrinsic reason
behind this connection.

######  Corollary 6.4.

Assume that $a>b\geq 2$. If $b$ is even, then for all $n\in\mathbb{N}$ we have

$g_{b,a}(n+1)=g_{a,b}(n).$

If $b$ is odd, then for all $n\in\mathbb{N}$ we have

$g_{b,a}(n)=g_{a,b}(n+1).$

###### Proof.

We first deal with the case where $b$ is even. We have
$g_{b,a}(n+1)=g_{a,b}(n)$ for all integers $n\leq 1$ except for $n=-1$, in
which case $g_{b,a}(0)=b$ and $g_{a,b}(-1)=0$. As both considered sequences
satisfy the same recurrence relation, it is sufficient to check that the term
$g_{a,b}(-1)$ never actually occurs in the computation of $g_{a,b}(n)$ for
$n>1$. In other words, we need to show that

$g_{a,b}(n-1)\neq n+1$

for $n>1$. If $n=2m$ is even, this follows from $g_{a,b}(2m-1)=b\equiv
0\pmod{2}$. If $n=2m+1$ is odd, we use the assumption $a>b$ ($b$ even) to
strengthen the inequality (9) to $g_{a,b}(2m)>2m+2$, and our claim follows.

Along the same lines, reasoning for $b$ odd reduces to showing that
$g_{a,b}(n)\neq n+1$ for $n>1$. The proof in this case is analogous. ∎

We are left with the case where at least one of $a,b$ is equal to $1$.

######  Theorem 6.5.

Assume that $a\geq 3$ and $b=1$. If $a$ is even, then for all $n\in\mathbb{N}$
we have

$\displaystyle g_{a,1}(2n)$ $\displaystyle=\begin{cases}a+n&\text{if
}n<a+1,\\\ g_{a,1}(2n-2-a)+g_{a,1}(2n-2)&\text{if }n\geq a+1,\end{cases}$
$\displaystyle g_{a,1}(2n+1)$ $\displaystyle=\begin{cases}1&\text{if
}n<a-1,\\\ a+1&\text{if }n=a-1,\\\ a+2&\text{if }n>a-1.\end{cases}$

If $a$ is odd, then for all $n\in\mathbb{N}$ we have

$\displaystyle g_{a,1}(2n)$ $\displaystyle=\begin{cases}a+n&\text{if }n<a,\\\
g_{a,1}(2n-1-a)+g_{a,1}(2n-2)&\text{if }n\geq a,\end{cases}$ $\displaystyle
g_{a,1}(2n+1)$ $\displaystyle=\begin{cases}1&\text{if }n<a-1,\\\ a+1&\text{if
}n\geq a-1.\end{cases}$

###### Proof.

Since the reasoning in both cases is similar, we show that the assertion holds
for $a$ even and leave the verification for $a$ odd to the reader. Again,
since $a,b$ are fixed, we omit them in the subscript. To begin, we
simultaneously prove both formulas for $g(2n)$ and $g(2n+1)$ for $n<a-1$ by
induction. The base case $n=0$ follows from the definition. For $1\leq n<a-1$
we have

$g(2n)=g(2n-g(2n-1))+g(2n-2)=g(2n-1)+a+n-1=a+n,$

as well as

$g(2n+1)=g(2n+1-g(2n))+g(2n-1)=g(n+1-a)+1=1.$

For $n=a-1,a$ the values $g(2n)$ and $g(2n+1)$ can be calculated directly.

In the case $n\geq a+1$ we check by induction that $g(2n)>2n+1$, which
immediately implies $g(2n+1)=a+2$. The inequality holds for $n=a+1$, as

$g(2a+2)=g(2a+2-g(2a+1))+g(2a)=g(a)+2a=\frac{7}{2}a>2a+3,$

by the assumption $a\geq 3$. For $n\geq a+2$ we have

$g(2n)=g(2n-g(2n-1))+g(2n-2)>g(2n-2-a)+2n-1>2n+1,$

using the fact that $(g(2n))_{n\in\mathbb{N}}$ does not decrease. The result
follows. ∎

######  Theorem 6.6.

Assume that $a=1$ and $b\geq 3$. Then for all $n\in\mathbb{N}$ we have

$\displaystyle g_{1,b}(2n)$ $\displaystyle=\begin{cases}1&\text{if }n<b-1,\\\
2&\text{if }n\geq b-1,\end{cases}$ $\displaystyle g_{1,b}(2n+1)$
$\displaystyle=\begin{cases}b+n&\text{if }n<b-1,\\\ 2^{n-b+3}(b-1)&\text{if
}n\geq b-1.\end{cases}$

###### Proof.

The argument is similar to the proof of Theorem 6.5. The values of $g(2n)$ and
$g(2n+1)$ for $n<b-1$ can easily be derived by induction.

For $n\geq b-1$ we again use induction to prove that $g(2n)=2$ and
$g(2n+1)>2n+2$, from which the result follows. ∎

To finish the investigation of $\mathbf{g}_{a,b}$, we deal with the remaining
cases $(a,b)\in\\{(1,1),(1,2),(2,1)\\}$. The proof is very similar to the
previous ones and is omitted.

######  Theorem 6.7.

For all $n\in\mathbb{N}$ we have

$\displaystyle g_{1,1}(2n+6)$ $\displaystyle=g_{1,1}(2n+4)+g_{1,1}(2n+2),$
$\displaystyle g_{1,1}(2n+7)$ $\displaystyle=4,$

and

$\displaystyle g_{1,2}(2n+6)$ $\displaystyle=4,$ $\displaystyle g_{1,2}(2n+5)$
$\displaystyle=g_{1,2}(2n+3)+g_{1,2}(2n+1),$

and

$\displaystyle g_{2,1}(2n+8)$ $\displaystyle=g_{2,1}(2n+6)+g_{2,1}(2n+2),$
$\displaystyle g_{2,1}(2n+7)$ $\displaystyle=6.$

##  7\. Questions and problems

In this final section, we formulate some questions and problems related to the
results of this paper which may be of interest.

To begin, it is well-known that a linear combination of linear recurrence
sequences is again a linear recurrence sequence. It is natural to ask whether
the same property holds for meta-Fibonacci sequences (with values in
$\mathbb{N}_{+}$).

######  Question 7.1.

Assume that $\mathbf{f}=(f(n))_{n\in\mathbb{N}}$ is $\mathbb{Z}$-linear
combination of meta-Fibonacci sequences such that $f(n)\in\mathbb{N}_{+}$ for
all $n$. Is $\mathbf{f}$ a meta-Fibonacci sequence?

In the proof of Theorem 4.4 we have shown that the sequences
$\mathbf{h}_{1,b}$ are closely related to the binary partition sequence by the
relation $h_{1,b+1}(2n+1)-h_{1,b}(2n+1)=bin(n+1)$ for any $b\geq 2$. An
affirmative answer to question 7.1 would automatically mean that the binary
partition sequence is a subsequence of a meta-Fibonacci sequence.

######  Question 7.2.

Can the sequence $(bin(n))_{n\in\mathbb{N}}$ be realized as a subsequence of a
meta-Fibonacci sequence along an arithmetic progression?

If this is not the case, we may further generalize the class of sequences
considered.

######  Question 7.3.

Can the sequence $(bin(n))_{n\in\mathbb{N}}$ be realized as a subsequence of a
recurrence sequence defined by the recurrence

$w(n)=\sum_{i=1}^{p}w(n-w(n-u_{i}))+\sum_{i=1}^{q}w(n-v_{i}),$

with the initial conditions chosen correctly, where $u_{i},v_{j}$ are positive
integers?

We now move on to the sequence $(r(n))_{n\in\mathbb{N}}=(h_{1,1}(n)\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2))_{n\in\mathbb{N}}$. We have shown
that this sequence is 2-automatic. It is natural to ask whether a similar
property holds for the reduction modulo any positive integer.

######  Question 7.4.

Let $m$ be a positive integer. Is $(h(n)\mkern 4.0mu({\operator@font
mod}\mkern 6.0mum))_{n\in\mathbb{N}}$ a $2$-automatic sequence?

We have performed experimental calculations in Mathematica 13 with the help of
the IntegerSequences package by Eric Rowland, available at

https://ericrowland.github.io/packages.html

The results indicate that the answer is affirmative when $m$ is a power of
$2$. On the other hand, when $m$ is not a power of $2$, the sequence
$(h(n)\mkern 4.0mu({\operator@font mod}\mkern 6.0mum))_{n\in\mathbb{N}}$ is
apparently not $k$-automatic for any $k$. In particular $2$-automaticity would
imply that the subsequence $(h(2^{n})\mkern 4.0mu({\operator@font mod}\mkern
6.0mum))_{n\in\mathbb{N}}$ is periodic, which does not appear to be the case
(at least for small values of $m$).

Another interesting problem concerns the $k$-regularity of the sequence of
indices $n$ such that the value of $r(n)=h_{1,1}(n)\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)$ is fixed.

######  Question 7.5.

Let ${\bf u}_{i}=(u_{i}(n))$ for $i=0,1$ be the increasing sequence of non-
negative integers such that $r(u_{i}(n))=i$. Is the sequence ${\bf u}_{i}$ is
$k$-regular for some $k$?

According to our numerical computations (using the mentioned package) both
sequences ${\bf u}_{0},{\bf u}_{1}$ are $2$-regular.

Finally, motivated by the results in this paper, one may try to study the
behavior of meta-Fibonacci sequences defined by the general recurrence (2). In
particular, it seems interesting to consider a direct generalization of the
sequence $\mathbf{h}_{a,b}$.

######  Problem 7.6.

Let $u,v$ be fixed positive integers. Let us put $f(n)=a_{0}$ for $n\leq 0$
and for given initial conditions $f(1),\ldots,f(k-1)\in\mathbb{N}_{+}$
investigate the behavior of the sequence $\mathbf{f}=(f(n))_{n\in\mathbb{N}}$,
where

$f(n)=f(n-f(n-u))+f(n-v)\quad\text{for}\quad n\geq k.$

As discussed in the introduction, the case $u\geq 1$ and $v=1$ is rather easy.
Next, if $u=2,v=1$, then without much of effort one can obtain the following
characterization of the sequence $\mathbf{f}$ for $k=2$:

  1. (1)

$f(n)=n+b+1$ for $a=1,b=1,2$ and $n\geq 4$;

  2. (2)

$f(n)=n+2a_{1}-2$ for $a=1,b\geq 3$ and $n\geq 4$;

  3. (3)

$f(n)=2n-b$ for $a=2,b=1,2$ and $n\geq 4$;

  4. (4)

$f(n)=an+b-a$ for $a\geq 2,b\geq 3$ and $n\geq 4$.

The case $u=1,v=2,k=2,a_{0},a_{1}\in\mathbb{N}_{+}$, is investigated in the
present paper.

For general $u,v,$ experimental results suggest that it is reasonable to split
the sequence $\mathbf{f}$ into $v$ subsequences $(f(vn+i))_{n\in\mathbb{N}}$,
where $i=0,1\ldots,v-1$. Apparently, each of these subsequences eventually
grows either linearly or exponentially. However, we expect that in some case a
new non-trivial phenomena arises.

For example, in the case $u=1,v=3,k=2$ with $a_{0}=f(1)=1$, numerical
computations suggest that $f(3n+1)=n+29871990902013037527$ for $n\geq 9673$
and $f(3n+2)=n+19162$ for $n\geq 120$. At the same time, assuming that these
observations are true, we have that

$f(3n)=f(2n-19161)+f(3(n-1))$

or equivalently

$f(3n)=211+\sum_{i=1}^{n}f(2i-19162)\quad\text{for}\quad n\geq 30.$

The growth of the subsequence $(f(3n))_{n\in\mathbb{N}}$ seems to be
eventually exponential. A question arises whether the subsequence
$(f(3n))_{n\in\mathbb{N}}$ can be described in terms of known functions.

## References

  * [1] J.-P. Allouche, J. Shallit, Automatic sequences. Theory, applications, generalizations., Cambridge University Press, Cambridge, 2003.
  * [2] J.-P. Allouche, J. Shallit, The ring of $k$-regular sequences, Theoret. Comput. Sci. 98 (1992), no. 2, 163–197.
  * [3] J.-P. Allouche, J. Shallit, The ring of $k$-regular sequences II, Theoret. Comput. Sci. 307 (2003), no. 1, 3–29.
  * [4] A. Černý, On Prouhet’s solution to the equal powers problem, Theoret. Comp. Sci., 491 (2013), 33–46.
  * [5] G. Christol, Ensembles presque periodiques $k$-reconnaissables, Theoret. Comput. Sci. 9 (1979), no. 1, 141–145.
  * [6] R. F. Churchhouse, Binary partitions, Computers in Number Theory, Proc. Atlas Sympos. No. 2, Oxford 1969, 397-400 (1971).
  * [7] B. W. Conolly, Meta-Fibonacci sequences, in S. Vajda, editor, Fibonacci and Lucas Numbers and the Golden Section. Halstead Press, NY, 1989, pp. 127–138.
  * [8] S. W. Golomb, Discrete chaos: sequences satisfying ”strange” recursions, unpublished manuscript. Available at:

         https://oeis.org/A005185/a005185_1.pdf

  * [9] D. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, New York, NY, USA, 1979.
  * [10] A. Isgur, R. Lech, S. Moore, S. Tanny, Y. Verberne, and Y. Zhang, Constructing New Families of Nested Recursions with Slow Solutions, SIAM J. Discrete Math., 30(2), 2016, 1128–1147.
  * [11] T. Kubo, R. Vakil, On Conway’s recursive sequence, Discrete Math. 152 (1996) 225–252.
  * [12] K. Mahler, On a special functional equation, J. London Math. Soc. 1 (1940), 115–123
  * [13] C. L. Mallows, Conway’s challenge sequence, Amer. Math. Monthly, 98 (1991), 5–20.
  * [14] Ke. Nishioka, Algebraic function solutions of a certain class of functional equations, Arch. Math., 44 (1985), 330–335.
  * [15] Ku. Nishioka, Mahler Functions and Transcendence, Lecture Notes in Mathematics Vol. 1631, Springer-Verlag, 1996.
  * [16] F. Ruskey, Fibonacci Meets Hofstadter, The Fibonacci Quarterly 49 (2011), no. 3, 227-230.
  * [17] S. M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discrete Math. 105 (1992), 227–239.

Bartosz Sobolewski, Jagiellonian University, Faculty of Mathematics and
Computer Science, Institute of Mathematics, Łojasiewicza 6, 30 - 348 Kraków,
Poland
e-mail<EMAIL_ADDRESS>
Maciej Ulas, Jagiellonian University, Faculty of Mathematics and Computer
Science, Institute of Mathematics, Łojasiewicza 6, 30 - 348 Kraków, Poland
e-mail<EMAIL_ADDRESS>


# A weakly supervised sequence tagging and grammar induction approach to
semantic frame slot filling

Janneke van de Loo^1 Guy De Pauw^1,2 Walter Daelemans^1 ^1CLiPS - University
of Antwerp ^2TEXTGAIN Belgium Belgium<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper describes continuing work on semantic frame slot filling for a
command and control task using a weakly-supervised approach. We investigate
the advantages of using retraining techniques that take the output of a
hierarchical hidden markov model as input to two inductive approaches: (1)
discriminative sequence labelers based on conditional random fields and
memory-based learning and (2) probabilistic context-free grammar induction.
Experimental results show that this setup can significantly improve F-scores
without the need for additional information sources. Furthermore, qualitative
analysis shows that the weakly supervised technique is able to automatically
induce an easily interpretable and syntactically appropriate grammar for the
domain and task at hand.

##  1 Introduction

The basic task of a command and control (C&C) interface is to convert a
language user’s unstructured input into some structured format that can be
unambiguously interpreted by a controller. Except for the simplest of devices,
this requires at some point in the processing chain some kind of syntactic
component that is aware of such issues as compositionality and word order. For
example, in the home automation C&C phrase turn on the lights, the system
needs to at least be aware that the input language is SVO to trigger the
difference between action and patient. In many cases, this is done through the
use of a context-free grammar in the decoding process [Jurafsky et al., 1995],
as illustrated in Figure 1 for the task of controlling a television using
natural language.

$<$sentence$>$ | = $<$volume_command$>$ $|$ $<$channel_command$>$
---|---
$<$volume_command$>$ | = (set $|$ change) volume [VOL] to $<$number$>$
$<$channel_command$>$ | = (select $|$ change to) channel [CH] ($<$number$>$ | $<$name$>$)
$<$number$>$ | = one [1] $|$ two [2] $|$ three [3] $|$ four [4] $|$ five [5]
$<$name$>$ | = BBC [4] $|$ CNN [2] $|$ EuroSports [1]
Figure 1: Context-free grammar for a television command & control interface.

While this approach has proved to be quite effective for many applications,
such devices are limited in the sense that they require the user to adhere to
the grammar and lexicon as predefined by the designers of the device. This
paper describes research conducted in the context of the ALADIN project, which
investigates a command and control interface that is not bound by predefined
linguistic constraints, but rather adapts to the user in a language and domain
independent way. The aim of the project is to find techniques that minimize
the training phase for such a self-learning system, so that it can be easily
deployed as a home automation C&C system for people with a physical
impairment, who are often challenged by (progressively aggravating) speech
impediments. A self-learning C&C interface that is able to automatically learn
and adapt to an individual user’s linguistic characteristics, can provide an
important means for a physically impaired person to regain some independence
in a domestic setting.

In this paper, we will investigate the syntactic component of the ALADIN-
system, where we define “syntax” loosely as a means to interface between the
surface utterance and its underlying semantic representation. Our semantic
representation of choice is that of a semantic frame with slots that need to
be filled with values (Section 2). Previous research efforts show that this
can be done with a fair degree of accuracy using a hierarchical hidden markov
model architecture (Section 3) under a minimal amount of supervision. The
research described in this paper improves on this accuracy, through means of
retraining using two different techniques: a shallow approach using sequence
labeling (Section 4.1) and a more traditional parsing approach employing
stochastic context-free grammar induction (Section 4.2). We will
quantitatively and qualitatively evaluate these techniques on the basis of
comparative experiments (Section 5) and finish with a discussion of the
results and pointers to future work (Section 6).

##  2 The patcor Corpus

The experiments described in this paper were conducted on the patcor
corpus111https://github.com/clips/patcor. patcor is a collection of command
and control utterances for the single-player card game Patience. This control
task was chosen because the disambiguation of these types of sentences
requires awareness of compositionality and word order, while at the same time
the domain and vocabulary are fairly restricted. The corpus contains audio
recordings of nine players, totaling around 3000 spoken commands (Belgian
Dutch) and their associated action in the game (represented as a semantic
frame; cf. infra). All of the spoken commands were manually transcribed.

patcor consists of a core data set of eight speakers, for which around 250
utterances were collected. We will refer to this core set as the p1-8 set.
Additional data was gathered for one player to study the effect of increasing
training sizes. This data set, referred to as the p9 set contains over 1,000
utterances. In the experiments below, p1-8 is used for development purposes,
while p9 is used for evaluation in learning curve experiments. More details
about the data set and the command structures that were used by the speakers
are described in ?).

The semantic representation of the controls in patcor takes the form of
semantic frames. This is illustrated in Figure 2: the semantic frame describes
the card that is moved (as a suit/value pair), the card that it is moved onto,
as well as the respective columns that are involved in the move. Additional
slots are available for moves from the hand and the foundation (respectively
at the bottom and top of Figure 2). An action on the playing field is thus
described as a collection of slot-value pairs. There are two types of semantic
frames: the movecard frame exemplified in Figure 2 and an additional dealcard
frame that denotes the action of asking for a new hand of cards. The latter
frame has no slots or values to be filled.

Note that the automatically generated semantic frame is overspecified with
respect to the command: in the command in Figure 2, columns are not mentioned,
although this information is included in the automatically generated frame. We
will use the utterances and their associated frames as training material to
trigger the mapping from words onto slot-value pairs. The difficulty for the
induction task therefore lies in identifying which words can be linked to
which slots and associated values. Furthermore, a word might underspecify its
slot-value in the semantic frame: for instance in Figure 2, the word “rood”
(red) can refer to suits hearts and diamonds alike, while only the former is
represented in the associated semantic frame.

Put the jack of clubs on the red queen movecard Slot value $<$FS$>$ c $<$FV$>$
11 $<$FF$>$ - $<$FC$>$ 3 $<$FH$>$ - $<$TS$>$ h $<$TV$>$ 12 $<$TF$>$ - $<$TC$>$
4

Figure 2: Example of a Patience command in patcor, the corresponding action on
the playing field and the associated semantic frame. A move is defined as a
combination of a from slot ($<$F?$>$) and a to slot ($<$T?$>$). A card is
defined as the combination of a suit ($<$?S$>$) and a value ($<$?V$>$). Also
defined are slots for the ‘hand’ at the bottom ($<$FH$>$), the seven columns
($<$?C$>$) in the playing field and the four foundation stacks at the top
right ($<$?F$>$).

##  3 Related Research

In this section we will provide some pointers to related research on mapping
tokens to semantic frames in C&C interfaces. We will also discuss previous
research efforts on the patcor data using two different techniques.

###  3.1 Semantic frame induction

There are many studies in spoken language understanding that use semantic
frames or an equivalent to encode the meaning of utterances. Mapping new
utterances to these semantic representations has been attempted using a
variety of techniques, such as generatively associating word sequences with
concept sequences [Pieraccini et al., 1991, Wang et al., 2011], using a
discriminative technique to perform concept tagging [Hahn et al., 2011], or
applying alignment techniques from the field of statistical machine
translation to relate words with semantic concepts [Epstein et al., 1996,
Macherey et al., 2001].

The research described in this paper differs from these previous approaches in
that our semantic representation is overspecified with respect to the
utterance and that we do not assume the ready availability of gold-standard
alignments between tokens and concepts. With respect to the latter issue, our
research is more akin to the unsupervised alignment of utterances and concepts
in the atis corpus, as described in ?). The patcor task itself on the other
hand, is more similar to that of the ROBOCUP data [Chen and Mooney, 2008], for
which a variety of approaches have been coined, ranging from learning the
alignment between utterances and frames [Liang et al., 2009] to learning
semantic parsers [Chen et al., 2010].

###  3.2 Supervised concept tagging

Previous work on patcor data is described in ?) and ?). These papers approach
the problem of inducing semantic frame slots from (transcribed) utterances as
a concept/sequence labeling task that can be learned by a machine learning
classifier. To this end, the transcriptions of patcor were manually annotated
with IOB-concept tags, where each word is associated with a concept tag that
denotes its association to a specific type of frame slot and its relative
position in the text chunk (Inside, Outside or at the Beginning). This is
illustrated in the following command (English: put the hearts five on the
clubs six) which denotes a move from a $<$From_Suit$>$ $<$From_Value$>$ card
to a $<$Target_Suit$>$ $<$Target_Value$>$ card.

legO deO hartenI_FS vijfI_FV opO deO klaverenI_TS zesI_TS

The eight data sets of the p1-8 set were each used individually as training
data for a memory-based concept tagger and learning curves were plotted using
the last 50 utterances in the respective data sets. Almost all of the data
sets achieve an I-chunk F-score between 95% and 100% after around 130 training
utterances, underlining the learnability of the task. However, this approach
relies on the existence of a gold-standard mapping between the observed tokens
and their relevant frame slots and values. This type of supervision is not
available in a C&C interface that is to be trained through the association of
an utterance in its entirety with an (overspecified) semantic frame.
Furthermore, [van de Loo et al., 2012a, van de Loo et al., 2012b] only report
tag and chunk accuracy scores, which only gives us an indirect indication of
how well semantic frame slots and values can be filled by this technique. In
the experiments below, we consider this supervised sequence labeler as the
upperbound of the level of performance that can be expected for this data set.

###  3.3 FramEngine

Research on the acoustic part of patcor focuses on finding descriptive word
units in the utterances, using non-negative matrix factorization. To map
observed units to frame slots (frame decoding), early research [Gemmeke et
al., 2012] employed a hand-crafted grammar, which encoded expected word order
patterns. This approach obtained slot-value recall scores between 37% and 85%
on the p1-8 set. One of the major bottlenecks in achieving higher accuracies
was the method’s limited ability to build a robust acoustic representation on
the basis of a limited amount of training data.

To streamline frame decoding, a semantic frame induction engine was developed
(FramEngine) that uses a combination of non-negative matrix factorization and
a hierarchical hidden markov model (HHMM) to simultaneously detect recurring
patterns in commands (words, morphemes, acoustic units) and relate them to
their relevant slots and values in semantic frames. This is a weakly
supervised induction task, as there is only supervision at the utterance level
and no relations between the components of the utterances and the semantic
frame slots are specified in advance.

Previous work [Ons et al., 2013] demonstrated the performance of an early
implementation of this system on pathological speech input for a simple home
automation command & control task and non-pathological patcor speech data. The
results show that the system has a promising learning potential even with
small amounts of training data, but that enhancements are needed in order to
produce practically usable accuracies for more complex utterances, such as the
ones found in patcor. Work described in ?) focused on improvements with
respect to the system architecture. Extensions regarding the HMM structure and
a technique called “expression sharing” were added to FramEngine’s workings
and were shown to significantly improve on the frame-slot filling abilities on
transcribed patcor data.

?) describes parameter selection experiments on p1-8, while a final evaluation
was conducted on the basis of learning curve experiments on the p9 set.
FramEngine was able to score over 95% frame-slot F-score using around 200
utterances as training data. While these results are encouraging, there are
reasons to believe we can still increase accuracy by means of retraining.
FramEngine’s slot-value allocation technique is limited in the context that it
can consider during disambiguation. And while word order is indirectly modeled
through the structural setup of the hierarchical hidden markov model, a
further explicitation of the syntactic properties of the observed utterances
may provide additional insights into the induction process proper.

In the context of this paper, we refer to retraining as the process of using
an automatically labeled data set as input data for another inductive
processing step. Typically, retraining techniques attempt to label large
volumes of unlabeled data to increase the volume of available training data
(self-training [McClosky et al., 2006]) or adapt a classifier to a new domain
(co-training [Blum and Mitchell, 1998]). The work in this paper investigates
retraining as the process of using successive classifiers on the same training
data to improve results. This approach has been successfully applied to a
variety of problems, including morphological analysis [De Pauw and de
Schryver, 2008] and spoken language understanding [Wu et al., 2006].

##  4 Retraining

This paper explores two different retraining techniques: inductive sequence
labeling (Section 4.1) and stochastic context-free grammar induction (Section
4.2). As described in ?), FramEngine can be shown to exhibit a more than
decent performance on the task of frame-slot filling for the patcor data. For
retraining purposes, we can use FramEngine to decode its own training set,
linking each word in the training set with a frame slot/value label through
Viterbi decoding of the utterance. This means we can now also associate each
word with an automatically assigned IOB-tag, expressing its frame-slot and in
addition also its value:

legO deO hartenI_FS=h vijfI_FV=5 opO deO klaverenI_TS=c zesI_TS=6

This information is consequently used as source data for retraining purposes.

###  4.1 Sequence Labeling

The first type of retraining technique recalls the research described in
Section 3.2: words annotated with IOB-tags are considered as training material
for a discriminative sequence tagger. Fully supervised (i.e. with manually
attributed IOB-tags), this approach can be observed to obtain near perfect
accuracy scores on the patcor data. Using training data labeled by a weakly
supervised technique (i.e. FramEngine), a sequence labeler can be expected to
perform less accurately than the fully supervised approach, but more
accurately than FramEngine itself, since it can take into account more
contextual information. We consider two different machine learning techniques
driving the sequence labeler: we compare a memory-based tagger (mbt [Daelemans
et al., 2010]) with one based on conditional random fields (wapiti [Lavergne
et al., 2010]).

Figure 3: Learning curves for p9 data FramEngine vs Single-Step Sequence
labeling.

Figure 3 displays learning curves for exploratory experiments, in which we
compared fully supervised sequence labeling (using gold-standard labels),
weakly supervised decoding using FramEngine, and retrained sequence labelers.
As expected, the accuracy of the retrained sequence labeler eventually ends up
somewhere between that of the supervised labeler and that of FramEngine. But
this result is not obtained until rather late in the learning curve, and even
the fully supervised labeler trails compared to the weakly supervised
FramEngine until training data hits around 400 utterances.

This is due to the fact that the sequence labelers consider the IOB-tags
holistically. FramEngine as described in ?), uses the method of expression
sharing, in which the hidden markov model is aware of the fact that certain
frame slots (such as the suit or value of a card) may be expressed using the
same tokens, regardless of whether it occurs in a from-clause or a target-
clause. This means that if a certain value has only occurred in one particular
context in the training set (e.g. vijfI_FV=5), the tagger would not be able to
predict the correct tag when it occurs in the other context in held-out data
(e.g. vijfI_TV=5), as it is simply unaware this tag even exists.

Figure 4: Illustration of the two-step tagging approach.

We therefore implement a two-step tagging approach that implicitly introduces
expression sharing in the workings of the sequence labelers. The process is
illustrated in Figure 4. The tags are decomposed into two parts: first a
tagger attributes to the words slot-value tags that generalize over slots of
the same type (in this case: ignoring ‘from’ and ‘target’ information). In the
second step, a tagger is trained using the slot-portion of the tag from step 1
as the token to be tagged and the remainder of the original tag as the target
tag. The original word in the utterance is used as an extra information layer
towards disambiguation. The tags of both steps are then combined into the
conglomerate tag. In case of incompatible tag-parts, the word is attributed
the O-tag. We will use the two-step tagging approach in the experiments
described in Section 5.

###  4.2 PCFG Induction

The utterances tagged automatically by FramEngine (cf. Example 4) can also be
transformed into tree-structures, given information about which expressions
can be shared. Slot-values (=? in Example 4) can be considered as terminals,
while suit/value and from/target indicators can function as nonterminals. Two
consecutive clauses headed by the same nonterminal are joined. As such, the
tagged sentence in Example 4 can be algorithmically transformed into the
phrase structure in Figure 5. These phrase structures can then be transformed
into a (probabilistic) context free grammar (Figure 6), by observing the
productions used to construct the tree structures for the utterances in the
training set. Finally, a Viterbi parser is used to assign tree structures to
new utterances and a reversal of the tree construction process outlined above,
can be used to assign IOB-labels that refer to frame slot/value pairs.

ROOT O leg de F S h harten V 5 vijf O op de T S c klaveren V 6 zes

Figure 5: Phrase-Structure tree derived from Example 4.

##  5 Experimental Results

ROOT | $\rightarrow$ | O F O T
---|---|---
F | $\rightarrow$ | S V
T | $\rightarrow$ | S V
S | $\rightarrow$ | h $|$ c
V | $\rightarrow$ | 5 $|$ 6
O | $\rightarrow$ | leg de $|$ op de
h | $\rightarrow$ | harten
c | $\rightarrow$ | klaveren
5 | $\rightarrow$ | vijf
6 | $\rightarrow$ | zes
Figure 6: Context-free grammar sample and lexicon derived from Figure 5. |
---|---
(a) | (b)
Figure 7: Learning curve experiments for the original FramEngine labeling,
supervised and retrained sequence labeling (a) and retraining using PCFG
induction (B)

###  5.1 Experimental Setup

We compare four different approaches on the basis of their ability to fill
slots with the correct values in semantic frames:

  1. 1.

Fully supervised sequence labeling (mbt and wapiti)

  2. 2.

FramEngine

  3. 3.

Retraining using sequence labeling (mbt and wapiti)

  4. 4.

Retraining using PCFG-induction

FramEngine fills frame slots by choosing slot-value tags with the highest
summed probability observed during decoding, exceeding a certain threshold
(established during development experiments). If no slot value tag with
sufficient probability mass occurs in the utterance, the slot remains empty.
Approaches 1, 3 and 4 fill frames in a similar vein, except that these
techniques predict for each token in the utterance a single slot-value tag
without a probability score (i.e. probability = 1). To solve ties, we add a
small bias proportional to the time index to each single tag probability (t *
10-5).

###  5.2 Evaluation

An important requirement for the ALADIN system is that the amount of effort
involved for the user in training the system be kept to a minimum. To evaluate
our techniques in this vein, we perform learning curve experiments to see
which techniques learn the required task the fastest with the least amount of
training data. The experiments were performed on the p9 set, which consists of
1142 commands and corresponding action frames of one single speaker. The last
third of the data set is used as evaluation data, while the remaining training
data is divided into partitions of 50 utterances. We preserve the order of the
training utterances as they have been recorded, to mimic how the actual system
would be trained in practice.

The training partitions in the p9 set are used incrementally as training data
for FramEngine. Optimal parameters and information sources for FramEngine were
obtained during expansive experiments on the p1-8 [van de Loo et al., 2019].
The trained hierarchical hidden markov model is then used to transcode the
training utterances into slot-value tag sequences. These automatically tagged
utterances, derived through a weakly supervised induction process, are then
used to train the memory-based and CRF-based sequence taggers and to induce a
PCFG respectively. Finally, the retrained techniques are evaluated on the
held-out data, creating a data point on the learning curve.

We evaluate against gold-standard semantic frames in which only the slots
mentioned in the utterance have been specified (in contrast to the
overspecified frame in Figure 2) and which slot values can be ambiguous: e.g.
in the case of ’aas opzij leggen’ (‘put ace aside’), the reference frame
includes all four possible foundation values (target_foundation=1,2,3,4),
because no specific value is specified in the command. We use frame slot
F-score as our metric of choice, which is calculated as follows:

  * •

slot precision: #correctly filled slots / #total filled slots in predicted
frame

  * •

slot recall: #correctly filled slots / #total filled slots in reference frame

  * •

slot Fβ=1-score: 2* slot precision * slot recall /(slot precision + slot
recall)

Finally, as FramEngine’s performance is affected by random initializations of
the system, the experiments with FramEngine and the retrained systems are
carried out ten times, with different random initializations. Scores are
averaged across the ten runs and 95% confidence levels for the scores are
reported as well.

###  5.3 Results

Figure 7 displays the learning curves for the p9 data. We consider the fully
supervised sequence labelers as the upper bound, since they are trained on
gold-standard data. We notice that they achieve optimal F-score at around 250
utterances. Before that, their accuracy scores are marred by unseen words in
the evaluation set, something that the weakly supervised FramEngine approach
is able to overcome through its looser generalization properties. Retraining
using the sequence labelers (Figure 7(a)), trained on the automatically tagged
data, improves F-scores for nearly all training sizes over FramEngine. For
this task, retraining using conditional random fields generally yields more
favorable learning curves than using memory-based learning.

The large leaps in the curves in Figure 7 are to a great extent related to a
shift in the user’s lexicon over time. In the test set (featuring recordings
during the end of the data collection process), the card value ‘king’ is
always referred to as ’heer’ (English: Sir), whereas initially, this card
value is always referred to as ’koning’ (English: ‘king’). The word ’heer’
starts to appear in the training set after the 200th utterance, thereby
causing a significant leap for all of the approaches.

Retraining through PCFG induction (Figure 7(b)) similarly suffers from out-of-
vocabulary words and, additionally, unseen grammatical productions in the
evaluation set on smaller training sizes. Its continuing performance is fairly
constant, although it seldom outperforms FramEngine in a convincing manner.
Figure 7(b) shows two PCFG-curves: one that expresses performance of 10
individual PCFGs for each FramEngine initialization (single run) and one that
joins the data from all the runs and induces one single PCFG (all runs).
Joining data over initializations dramatically improves the number of
structures in the evaluation set that are covered by the grammars, while
precision does not seem to suffer, thereby yielding higher F-scores for most
training set sizes over 250.

These experiments show that, although FramEngine achieves workable F-scores
using a weakly supervised approach, we can automatically increase F-scores
through retraining. For this task, sequence labeling is the recommended
retraining technique, although PCFGs can also be observed to increase F-scores
for this task. The latter result is encouraging, since it allows for the
weakly supervised induction of a classic command & control interface that
restricts the acoustic search space by means of a context-free grammar.

###  5.4 PCFG induction: a qualitative analysis

ROOT | $\rightarrow$ |  DC [0.0824324]
---|---|---
ROOT | $\rightarrow$ |  O DC [0.331081]
ROOT | $\rightarrow$ |  F O T [0.586486]
DC | $\rightarrow$ |  kaarten omdraaien [0.593054]
DC | $\rightarrow$ |  nieuwe kaarten omdraaien [0.131062]
DC | $\rightarrow$ |  omdraaien [0.275885]
F | $\rightarrow$ |  S V [1.0]
T | $\rightarrow$ |  TF [0.0909515]
T | $\rightarrow$ |  S V [0.909049]
S | $\rightarrow$ |  c [0.249707]
S | $\rightarrow$ |  d [0.264478]
S | $\rightarrow$ |  h [0.233763]
S | $\rightarrow$ |  s [0.252052]
V | $\rightarrow$ |  1 [0.0763444]
V | $\rightarrow$ |  2 [0.0617492]
V | $\rightarrow$ |  3 [0.0617492]
V | $\rightarrow$ |  4 [0.084428]
V | $\rightarrow$ |  5 [0.0911643]
V | $\rightarrow$ |  6 [0.0862243]
V | $\rightarrow$ |  7 [0.0739868]
V | $\rightarrow$ |  8 [0.0817335]
V | $\rightarrow$ |  9 [0.086112]
V | $\rightarrow$ |  10 [0.0793758]
V | $\rightarrow$ |  11 [0.0673627]
V | $\rightarrow$ |  12 [0.0718536]
V | $\rightarrow$ |  13 [0.0779162]
O | $\rightarrow$ |  kaarten [0.13268]
O | $\rightarrow$ |  nieuwe [0.252725]
O | $\rightarrow$ |  op [0.614595]
1 | $\rightarrow$ |  aas [1.0]
2 | $\rightarrow$ |  twee [1.0]
3 | $\rightarrow$ |  drie [1.0]
4 | $\rightarrow$ |  vier [1.0]
5 | $\rightarrow$ |  vijf [1.0]
6 | $\rightarrow$ |  zes [1.0]
7 | $\rightarrow$ |  zeven [1.0]
8 | $\rightarrow$ |  acht [1.0]
9 | $\rightarrow$ |  negen [1.0]
10 | $\rightarrow$ |  tien [1.0]
11 | $\rightarrow$ |  boer [1.0]
12 | $\rightarrow$ |  dame [1.0]
c | $\rightarrow$ |  klaveren [1.0]
d | $\rightarrow$ |  ruiten [1.0]
h | $\rightarrow$ |  harten [1.0]
s | $\rightarrow$ |  schoppen [1.0]
Figure 8: Probabilistic Context-Free Grammar and lexicon (induced in a weakly
supervised manner). For display purposes, only productions that occur more
than 0.5% of the time were used to compile the PCFG. The non-terminals are
ROOT, DealCard, From, Target, Suit, Value, O. (induced in run-1 at training
set size 761)

While the F-scores of the PCFG-retraining approach trail compared to those of
the retrained sequence labelers, the former presents an interesting
opportunity for interpretability. Looking at the induced PCFGs can provide us
with further insight into how the structural properties of the language are
being modeled.

The grammar in Figure 8 corresponds rather well with our intuitions for this
task. Apart from an artifact (production T$\rightarrow$TF cannot reach
terminal nodes) and a needlessly ambiguous handling of the tokens nieuwe
(new), kaarten (cards) and omdraaien (turn over), the induced PCFG presents a
clean description of the grammar used in the utterances of the training set.
The probabilities for the different card suits are evenly distributed, as are
their card values. The two different frame types are triggered by three ROOT
rules, two for the dealcard frame, one for the movecard frame. Interestingly,
while the grammar in Figure 8 excludes infrequent rules (such as ROOT
$\rightarrow$ F T O T O F O T), applying this kind of filtering in practice
yields significantly lower F-scores during the experiments, as these
productions provide coverage for idiosyncratic utterances containing repairs
and the like.

##  6 Conclusion and Future work

This paper described research on data collected for a command & control
interface for the card game Patience. The task of associating components of a
command to slots in semantic frame representations of the intended control was
already established with a fair degree of accuracy using a semantic frame
induction technique based on non-negative matrix factorization and a
hierarchical hidden markov model (FramEngine). This paper improves on this
result by applying retraining using a discriminative sequence labeler as a
post-processing step. Additional retraining experiments using probabilistic
context-free grammar induction likewise show improvements when used as a post-
processing step.

Next steps in this research should investigate whether these retraining
techniques can yield similar accuracy increases when applied on the acoustic
portion of the patcor data. It will be particularly interesting to see whether
the PCFG induction technique can yield a similarly transparent collection of
productions as displayed in Figure 8, when confronted with a noisy set of
observations.

We will also investigate the advantage of the retraining techniques on other
data sets, such as the grammatically less complex home automation data,
collected in the context of the ALADIN project [Ons et al., 2013], but also
the ROBOCUP data [Chen and Mooney, 2008], which in recent years has become an
interesting benchmark to gauge advances in this field. Finally, further
research efforts should investigate whether the retraining techniques, now
used as a post-processing step, can be compiled into FramEngine so that
decoding can be achieved in a single processing sweep.

##  7 Acknowledgments*

This research described in this paper was funded by IWT-SBO grant 100049
(ALADIN). The patcor dataset is available from
https://github.com/clips/patcor. We would like to thank Jort Gemmeke, Hugo Van
hamme and Bart Ons for their valued input on the research described in this
paper.

## References

  * [Blum and Mitchell, 1998]  Avrim Blum and Tom Mitchell.  1998\.  Combining labeled and unlabeled data with co-training.  In Proceedings of the Eleventh Annual Conference on Computational Learning Theory, COLT’ 98, pages 92–100, New York, NY, USA. ACM.
  * [Chen and Mooney, 2008]  David L Chen and Raymond J Mooney.  2008\.  Learning to sportscast: a test of grounded language acquisition.  In Proceedings of the 25th international conference on Machine learning, pages 128–135. ACM.
  * [Chen et al., 2010]  David L Chen, Joohyun Kim, and Raymond J Mooney.  2010\.  Training a multilingual sportscaster: Using perceptual context to learn language.  Journal of Artificial Intelligence Research, 37(1):397–436.
  * [Daelemans et al., 2010]  W. Daelemans, J. Zavrel, A. van den Bosch, and K. Van der Sloot.  2010\.  MBT: Memory-based tagger, version 3.2, reference guide.  Technical Report 10-04, University of Tilburg.
  * [De Pauw and de Schryver, 2008]  G. De Pauw and G-M de Schryver.  2008\.  Improving the computational morphological analysis of a Swahili corpus for lexicographic purposes.  Lexikos, 18:303–318.
  * [Epstein et al., 1996]  Mark Epstein, T Ward, S Della Pietra, K Papineni, and S Roukos.  1996\.  Statistical natural language understanding using hidden clumpings.  In IEEE International Conference on Acoustics, Speech, and Signal Processing 1996 (ICASSP-96), volume 1, pages 176–179. IEEE.
  * [Gemmeke et al., 2012]  Jort F. Gemmeke, J. van de Loo, G. De Pauw, J. Driesen, H. Van hamme, and W. Daelemans.  2012\.  A self-learning assistive vocal interface based on vocabulary learning and grammar induction.  In Proc. INTERSPEECH, pages 1–4.
  * [Hahn et al., 2011]  Stefan Hahn, Marco Dinarelli, Christian Raymond, Fabrice Lefevre, Patrick Lehnen, Renato de Mori, Alessandro Moschitti, Hermann Ney, and Giuseppe Riccardi.  2011\.  Comparing stochastic approaches to spoken language understanding in multiple languages.  IEEE Transactions on Audio, Speech & Language Processing, 19(6):1569–1583.
  * [Huet and Lefèvre, 2011]  Stéphane Huet and Fabrice Lefèvre.  2011\.  Unsupervised alignment for segmental-based language understanding.  In Proceedings of the First Workshop on Unsupervised Learning in NLP, EMNLP ’11, pages 97–104, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * [Jurafsky et al., 1995]  D. Jurafsky, Ch. Wooters, J. Segal, A. Stolcke, E. Fosler, G. Tajchman, and N. Morgan.  1995\.  Using a stochastic context-free grammar as a language model for speech recognition.  In Proceedings, IEEE Conference on Acoustics, Speech and Signal Processing, pages 189–192, Detroit, Michigan.
  * [Lavergne et al., 2010]  Thomas Lavergne, Olivier Cappé, and François Yvon.  2010\.  Practical very large scale CRFs.  In Proceedings the 48th Annual Meeting of the Association for Computational Linguistics (ACL), pages 504–513. Association for Computational Linguistics, July.
  * [Liang et al., 2009]  Percy Liang, Michael I. Jordan, and Dan Klein.  2009\.  Learning semantic correspondences with less supervision.  In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 1 - Volume 1, ACL ’09, pages 91–99, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * [Macherey et al., 2001]  Klaus Macherey, Franz Josef Och, and Hermann Ney.  2001\.  Natural language understanding using statistical machine translation.  In INTERSPEECH, pages 2205–2208.
  * [McClosky et al., 2006]  David McClosky, Eugene Charniak, and Mark Johnson.  2006\.  Effective self-training for parsing.  In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, pages 152–159, New York City, USA, June. Association for Computational Linguistics.
  * [Ons et al., 2013]  Bart Ons, Netsanet Tessema, Janneke van de Loo, and Jort F Gemmeke.  2013\.  A self learning vocal interface for speech-impaired users.  Proceedings SLPAT 2013, pages 1–9.
  * [Pieraccini et al., 1991]  Roberto Pieraccini, Esther Levin, and Chin-Hui Lee.  1991\.  Stochastic representation of conceptual structure in the atis task.  In HLT, pages 121–124. Morgan Kaufmann.
  * [van de Loo et al., 2012a]  J. van de Loo, G. De Pauw, J.F. Gemmeke, P. Karsmakers, B. Van Den Broeck, W. Daelemans, and H. Van hamme.  2012a.  Towards shallow grammar induction for an adaptive assistive vocal interface: a concept tagging approach.  In Proceedings NLP4ITA, pages 27–34.
  * [van de Loo et al., 2012b]  J. van de Loo, J.F Gemmeke, G. De Pauw, J. Driesen, H. Van hamme, and W. Daelemans.  2012b.  Towards a self-learning assistive vocal interface: Vocabulary and grammar learning.  In Proceedings of the 1st Workshop on Speech and Multimodal Interaction in Assistive Environments (SMIAE), pages 34–42, Jeju, Republic of Korea, 07/2012. Association for Computational Linguistics.
  * [van de Loo et al., 2019]  Janneke van de Loo, Jort F. Gemmeke, Guy De Pauw, Bart Ons, Walter Daelemans, and Hugo Van hamme.  2019\.  Effective weakly supervised semantic frame induction using expression sharing in hierarchical hidden markov models.  Computing Research Repository, arXiv:1901.10680.
  * [Wang et al., 2011]  Y. Wang, L. Deng, and A. Acero.  2011\.  Semantic frame-based spoken language understanding.  In G. Tur and R. De Mori, editors, Spoken Language Understanding: Systems for Extracting Semantic Information from Speech, chapter 3, pages 41–91. Wiley, West-Sussex, UK.
  * [Wu et al., 2006]  Wei-Lin Wu, Ru-Zhan Lu, Jian-Yong Duan, Hui Liu, Feng Gao, and Yu-Quan Chen.  2006\.  A weakly supervised learning approach for spoken language understanding.  In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, pages 199–207, Sydney, Australia, July. Association for Computational Linguistics.