Universität Siegen<EMAIL_ADDRESS>Moses Ganardi [500]Theory
of computation Streaming models The author is supported by the DFG project LO
748/13-1. Rolf Niedermeier and Christophe Paul 2 36th International Symposium
on Theoretical Aspects of Computer Science (STACS 2019) STACS 2019 STACS 2019
March 13–16, 2019 Berlin, Germany 126 27

# Visibly Pushdown Languages over Sliding Windows

Moses Ganardi

###### Abstract

We investigate the class of visibly pushdown languages in the sliding window
model. A sliding window algorithm for a language $L$ receives a stream of
symbols and has to decide at each time step whether the suffix of length $n$
belongs to $L$ or not. The window size $n$ is either a fixed number (in the
fixed-size model) or can be controlled by an adversary in a limited way (in
the variable-size model). The main result of this paper states that for every
visibly pushdown language the space complexity in the variable-size sliding
window model is either constant, logarithmic or linear in the window size.
This extends previous results for regular languages.

###### keywords:

visibly pushdown languages, sliding windows, rational transductions

##  1 Introduction

### The sliding window model.

A sliding window algorithm (SWA) is an algorithm which processes a stream of
data elements $a_{1}a_{2}a_{3}\cdots$ and computes at each time instant $t$ a
certain value that depends on the suffix $a_{t-n+1}\cdots a_{t}$ of length $n$
where $n$ is a parameter called the window size. This streaming model is
motivated by the fact that in many applications data elements are outdated or
become irrelevant after a certain time. A general goal in the area of sliding
window algorithms is to avoid storing the window content explicitly (which
requires $\Omega(n)$ bits) and to design space efficient algorithms, say using
polylogarithmic many bits in the window size $n$.

A prototypical example of a problem considered in the sliding window model is
the Basic Counting problem. Here the input is a stream of bits and the task is
to approximate the number of 1’s in the last $n$ bits (the active window). In
[15], Datar, Gionis, Indyk and Motwani present an approximation algorithm
using $O(\frac{1}{\epsilon}\log^{2}n)$ bits of space with an approximation
ratio of $\epsilon$. They also prove a matching lower bound of
$\Omega(\frac{1}{\epsilon}\log^{2}n)$ bits for any deterministic (and even
randomized) algorithm for Basic Counting. Other works in the sliding window
model include computing statistics [2, 3, 8], optimal sampling [9] and various
pattern matching problems [10, 12, 13, 14].

There are two variants of the sliding window model, cf. [2]. One can think of
an adversary who can either insert a new element into the window or remove the
oldest element from the window. In the fixed-size sliding window model the
adversary determines the window size $n$ in the beginning and the initial
window is set to $a^{n}$ for some default known element $a$. At every time
step the adversary inserts a new symbol and then immediately removes the
oldest element from the window. In the variable-size sliding window model the
window size is initially set to $n=0$. Then the adversary is allowed to
perform an arbitrary sequence of insert- and remove-operations. A remove-
operation on an empty window leaves the window empty. We also mention the
timestamp-based model where every element carries a timestamp (many elements
may have the same timestamp) and the active window at time $t$ contains only
those elements whose timestamp is at least $t-t_{0}$ for some parameter
$t_{0}$ [9]. Both the fixed-size and the timestamp-based model can be
simulated in the variable-size model.

### Regular languages.

In a recent series of works we studied the membership problem to a fixed
regular language in the sliding window model. It was shown in [20] that in
both the fixed-size and the variable-size sliding window model the space
complexity of any regular language is either constant, logarithmic or linear
(a space trichotomy). In a subsequent paper [18] a characterization of the
space classes was given: A regular language has a fixed/variable-size SWA with
$O(\log n)$ bits if and only if it is a finite Boolean combination of regular
left ideals and regular length languages. A regular language has a fixed-size
SWA with $O(1)$ bits if and only if it is a finite Boolean combination of
suffix testable languages and regular length languages. A regular language has
a variable-size SWA with $O(1)$ bits if and only if it is empty or universal.

### Context-free languages.

A natural question is whether the results above can be extended to larger
language classes, say subclasses of the context-free languages. More
precisely, we pose the questions: (i) Which language classes have a “simple”
hierarchy of space complexity classes (like the space trichotomy for the
regular languages), and (ii) are there natural descriptions of the space
classes? A positive answer to question (i) seems to be necessary to answer
question (ii) positively. In [21] we presented a family of context-free
languages $(L_{k})_{k\geq 1}$ which have space complexity $\Theta(n^{1/k})$ in
the variable-size model and $O(n^{1/k})\setminus o(n^{1/k})$ in the fixed-size
model, showing that there exists an infinite hierarchy of space complexity
classes inside the class of context-free languages. Intuitively, this result
can be explained with the fact that a language and its complement have the
same sliding window space complexity; however, the class of context-free
languages is not closed under complementation (in contrast to the regular
languages) and the analysis of co-context-free languages in this setting seems
to be very difficult. Even in the class of deterministic context-free
languages, which is closed under complementation, there are example languages
which have sliding window space complexity $\Theta((\log n)^{2})$ [21].

### Visibly pushdown languages.

Motivated by these observations in this paper we will study the class of
visibly pushdown languages, introduced by Alur and Madhusudan [1]. They are
recognized by visibly pushdown automata where the alphabet is partitioned into
call letters, return letters and internal letters, which determine the
behavior of the stack height. Since visibly pushdown automata can be
determinized, the class of visibly pushdown languages turns out to be very
robust (it is closed under Boolean operations and other language operations)
and to be more tractable in many algorithmic questions than the class of
context-free languages [1]. In this paper we prove a space trichotomy for the
class of visibly pushdown languages in the variable-size sliding window model,
stating that the space complexity of every visibly pushdown language is either
$O(1)$, $\Theta(\log n)$ or $O(n)\setminus o(n)$. The main technical result is
a growth theorem (Theorem 4.7) for rational transductions. A natural
characterization of the $O(\log n)$-class as well as a study of the fixed-size
model are left as open problems.

Let us mention some related work in the context of streaming algorithms for
context-free languages. Randomized streaming algorithms were studied for
subclasses of context-free languages (DLIN and LL$(k)$) [4] and for Dyck
languages [25]. A streaming property tester for visibly pushdown languages was
presented by François et al. [17].

##  2 Preliminaries

We define $\log n=\lfloor\log_{2}n\rfloor$ for all $n\geq 1$, which is the
minimum number $k$ of bits required to encode $n$ elements using bit strings
of length at most $k$. If $w=a_{1}\cdots a_{n}$ is a word then any word of the
form $a_{i}\cdots a_{n}$ ($a_{1}\cdots a_{i}$) is called suffix (prefix) of
$w$. A prefix (suffix) $v$ of $w$ is proper if $v\neq w$. A factor of $w$ is
any word of the form $a_{i}\cdots a_{j}$. A factorization of $w$ is formally a
sequence of possibly empty factors $(w_{0},\dots,w_{m})$ with $w=w_{0}\cdots
w_{m}$. We call $w_{0}$ the initial factor and $w_{1},\dots,w_{m}$ the
internal factors. The reversal of $w$ is $w^{\mathsf{R}}=a_{n}a_{n-1}\cdots
a_{1}$. For a language $L\subseteq\Sigma^{*}$ we denote by $\mathsf{Suf}(L)$
the set of suffixes of words in $L$. If $L=\mathsf{Suf}(L)$ then $L$ is
suffix-closed.

### Automata.

An automaton over a monoid $M$ is a tuple $A=(Q,M,I,\Delta,F)$ where $Q$ is a
finite set of states, $I\subseteq Q$ is a set of initial states,
$\Delta\subseteq Q\times M\times Q$ is the transition relation and $F\subseteq
Q$ is the set of final states. A run on $m\in M$ from $q_{0}$ to $q_{n}$ is a
sequence of transitions of the form
$\pi=(q_{0},m_{1},q_{1})(q_{1},m_{2},q_{2})\cdots(q_{n-1},m_{n},q_{n})\in\Delta^{*}$
such that $m=m_{1}\cdots m_{n}$. We usually depict $\pi$ as
$q_{0}\xrightarrow{m_{1}}q_{1}\xrightarrow{m_{2}}q_{2}\,\cdots\,q_{n-1}\xrightarrow{m_{n}}q_{n}$,
or simply $q_{0}\xrightarrow{m}q_{n}$. It is initial if $q_{0}\in I$ and
accepting if $q_{n}\in F$. The language defined by $A$ is the set
$\mathsf{L}(A)$ of all elements $m\in M$ such that there exists an initial
accepting run on $m$. A subset $L\subseteq M$ is rational if $L=\mathsf{L}(A)$
for some automaton $A$. We only need the case where $M$ is the free monoid
$\Sigma^{*}$ over an alphabet $\Sigma$ or where $M$ is the product
$\Sigma^{*}\times\Omega^{*}$ of two free monoids. In these cases we change the
format and write $(Q,\Sigma,I,\Delta,F)$ and $(Q,\Sigma,\Omega,I,\Delta,F)$,
respectively. Subsets of $\Sigma^{*}$ are called languages and subsets of
$\Sigma^{*}\times\Omega^{*}$ are called transductions. Rational languages are
usually called regular languages.

In this paper we will also use right automata, which read the input from right
to left. Formally, a right automaton $A=(Q,M,F,\Delta,I)$ has the same format
as a (left) automaton where the sets of initial and final states are swapped.
Runs in right automata are defined from right to left, i.e. a run on $m\in M$
from $q_{n}$ to $q_{0}$ is a sequence of transitions of the form
$(q_{0},m_{1},q_{1})(q_{1},m_{2},q_{2})\cdots(q_{n-1},m_{n},q_{n})\in\Delta^{*}$
such that $m=m_{1}\cdots m_{n}$. In the graphic notation we write the arrows
from right to left. It is initial (accepting) if $q_{n}\in I$ ($q_{0}\in F$).

### Right congruences.

For any equivalence relation $\sim$ on a set $X$ we write $[x]_{\sim}$ for the
$\sim$-class containing $x\in X$ and $X/{\sim}=\\{[x]_{\sim}\mid x\in X\\}$
for the set of all $\sim$-classes. The index of $\sim$ is the cardinality of
$X/{\sim}$. We denote by $\nu_{\sim}\colon X\to X/{\sim}$ the function with
$\nu_{\sim}(x)=[x]_{\sim}$. A subset $L\subseteq X$ is saturated by $\sim$ if
$L$ is a union of $\sim$-classes. An equivalence relation $\sim$ on the free
monoid $\Sigma^{*}$ over some alphabet $\Sigma$ is a right congruence if
$x\sim y$ implies $xz\sim yz$ for all $x,y,z\in\Sigma^{*}$. The Myhill-Nerode
right congruence $\sim_{L}$ of a language $L\subseteq\Sigma^{*}$ is the
equivalence relation on $\Sigma^{*}$ defined by $x\sim_{L}y$ if and only if
$x^{-1}L=y^{-1}L$ where $x^{-1}L=\\{z\mid xz\in L\\}$. It is indeed the
coarsest right congruence on $\Sigma^{*}$ which saturates $L$. We usually
write $\nu_{L}$ instead of $\nu_{\sim_{L}}$. A language $L\subseteq\Sigma^{*}$
is regular iff $\sim_{L}$ has finite index.

### Rational transductions.

Rational transductions are accepted by automata over
$\Sigma^{*}\times\Omega^{*}$, which are called finite state transducers. In
this paper, we will use a slightly extended but equivalent definition. A
transducer is a tuple $A=(Q,\Sigma,\Omega,I,\Delta,F,o)$ such that
$(Q,\Sigma^{*}\times\Omega^{*},I,\Delta,F)$ is an automaton over
$\Sigma^{*}\times\Omega^{*}$ and a terminal output function $o\colon
F\to\Omega^{*}$. To omit parentheses we write runs $p\xrightarrow{(x,y)}q$ in
the form $p\xrightarrow{x\mid y}q$ and depict $o(q)=y$ by a transition
$q\xrightarrow{\mid y}$ without input word and target state. If $\pi$ is a run
$p\xrightarrow{x\mid y}q$ we define $\mathsf{out}(\pi)=y$ and
$\mathsf{out}_{F}(\pi)=y\,o(q)$. The transduction defined by $A$ is the set
$\mathsf{T}(A)$ of all pairs $(x,\mathsf{out}_{F}(\pi))$ such that $\pi$ is an
initial accepting run $p\xrightarrow{x\mid y}q$. Since the terminal output
function can be eliminated by $\varepsilon$-transitions, a transduction is
rational if and only if it is of the form $\mathsf{T}(A)$ for some transducer
$A$. In this paper we will mainly use rational functions, which are partial
functions $t\colon\Sigma^{*}\to\Omega^{*}$ whose graph $\\{(x,t(x))\mid
x\in\mathrm{dom}(t)\\}$ is a rational transduction.

A transducer $A$ is trim if every state occurs on some accepting run. If every
word $x\in\Sigma^{*}$ has at most one initial accepting run
$p\xrightarrow{x\mid y}q$ for some $y\in\Omega^{*}$ then $A$ is unambiguous.
If $\Delta\subseteq Q\times\Sigma\times\Omega^{*}\times Q$ then $A$ is real-
time. It is known that every rational function is defined by a trim
unambiguous real-time transducer [6, Corollary 4.3]. If $A$ is unambiguous and
trim then for every word $x\in\Sigma^{*}$ and every pair of states $(p,q)\in
Q^{2}$ there exists at most one run from $p$ to $q$ with input word $x$.
Therefore, the state pair $(p,q)$ and the input word $x$ uniquely determine
the run (if it exists) and we can simply write $p\xrightarrow{x}q$. Similarly
to [28], we define for a real-time transducer $A$ the parameter
$\mathsf{iml}(A)=\max\left(\\{|y|\mid(q,a,y,p)\in\Delta\\}\cup\\{|o(q)|\mid
q\in Q\\}\right)$. For every run $\pi$ on a word $x\in\Sigma^{*}$ we have
$|\mathsf{out}(\pi)|\leq\mathsf{iml}(A)\cdot|x|$ and
$|\mathsf{out}_{F}(\pi)|\leq\mathsf{iml}(A)\cdot(|x|+1)$.

The following closure properties for rational transductions are known [6]: The
class of rational transductions is closed under inverse, reversal and
composition where the inverse of $T$ is $T^{-1}=\\{(y,x)\mid(x,y)\in T\\}$,
the reversal of $T$ is
$T^{\mathsf{R}}=\\{(x^{\mathsf{R}},y^{\mathsf{R}})\mid(x,y)\in T\\}$, and the
composition of two transductions $T_{1},T_{2}$ is $T_{1}\circ
T_{2}=\\{(x,z)\mid\exists y:(x,y)\in T_{1}\text{ and }(y,z)\in T_{2}\\}$. If
$T\subseteq\Sigma^{*}\times\Omega^{*}$ is rational and $L\subseteq\Sigma^{*}$
is regular then the restriction $\\{(x,y)\in T\mid x\in L\\}$ is also
rational. If $K\subseteq\Sigma^{*}$ is regular (context-free) and
$T\subseteq\Sigma^{*}\times\Omega^{*}$ is rational then
$TK=\\{y\in\Omega^{*}\mid(x,y)\in T\text{ for some }x\in K\\}$ is also regular
(context-free).

A right transducer is a tuple $A=(Q,\Sigma,\Omega,F,\Delta,I,o)$ such that
$(Q,\Sigma^{*}\times\Omega^{*},F,\Delta,I)$ is a right automaton over
$\Sigma^{*}\times\Omega^{*}$ and a terminal output function $o\colon
F\to\Omega^{*}$. We depict $o(q)=y$ by a transition $\xleftarrow{\mid y}q$. If
$\pi$ is a run $q\xleftarrow{x\mid y}p$ we define $\mathsf{out}(\pi)=y$ and
$\mathsf{out}_{F}(\pi)=o(q)\,y$. All other notions on transducers are defined
for right transducers in a dual way.

### Growth functions.

A function $\gamma\colon\mathbb{N}\to\mathbb{N}$ grows polynomially if
$\gamma(n)\in O(n^{k})$ for some $k\in\mathbb{N}$; we say that $\gamma$ grows
exponentially if there exists a number $c>1$ such that $\gamma(n)\geq c^{n}$
for infinitely many $n\in\mathbb{N}$. A function $\gamma(n)$ grows
exponentially if and only if $\log\gamma(n)\notin o(n)$.

We will define a generalized notion of growth. Let $t\colon\Sigma^{*}\to Y$ be
a partial function and let $X\subseteq\mathrm{dom}(t)$ be a language. The
$t$-growth of $X$ is the function $\gamma(n)=|t(X\cap\Sigma^{\leq n})|$, i.e.
it counts the number of output elements on input words from $X$ of length at
most $n$. The growth of $X$ is simply the $\mathrm{id}_{X}$-growth of $X$,
i.e. $\gamma(n)=|X\cap\Sigma^{\leq n}|$. It is known that every context-free
language has either polynomial or exponential growth [22]. Furthermore, a
context-free language $L$ has polynomial growth if and only if it is bounded,
i.e. $L\subseteq w_{1}^{*}\cdots w_{k}^{*}$ for some words $w_{1},\dots,w_{k}$
[22]. We need the fact that if $L$ is a bounded language and $K$ is a set of
factors of words in $L$ then $K$ is bounded [23, Lemma 1.1(c)].

##  3 Visibly pushdown languages

A pushdown alphabet is a triple
$\tilde{\Sigma}=(\Sigma_{c},\Sigma_{r},\Sigma_{\mathit{int}})$ consisting of
three pairwise disjoint alphabets: a set of call letters $\Sigma_{c}$, a set
of return letters $\Sigma_{r}$ and a set of internal letters
$\Sigma_{\mathit{int}}$. We identify $\tilde{\Sigma}$ with the union
$\Sigma=\Sigma_{c}\cup\Sigma_{r}\cup\Sigma_{\mathit{int}}$. The set of well-
matched words $W$ over $\Sigma$ is defined as the smallest set which contains
$\\{\varepsilon\\}\cup\Sigma_{\mathit{int}}$, is closed under concatenation,
and if $w$ is well-matched, $a\in\Sigma_{c}$, $b\in\Sigma_{r}$ then also $awb$
is well-matched. A word is called descending (ascending) if it can be
factorized into well-matched factors and return (call) letters. The set of
descending words is denoted by $D$. A visibly pushdown automaton (VPA) has the
form $A=(Q,\tilde{\Sigma},\Gamma,\bot,q_{0},\delta,F)$ where $Q$ is a finite
state set, $\tilde{\Sigma}$ is a pushdown alphabet, $\Gamma$ is the finite
stack alphabet containing a special symbol $\bot$ (representing the empty
stack), $q_{0}\in Q$ is the initial state, $F\subseteq Q$ is the set of final
states and $\delta=\delta_{c}\cup\delta_{r}\cup\delta_{\mathit{int}}$ is the
transition function where $\delta_{c}\colon
Q\times\Sigma_{c}\to(\Gamma\setminus\\{\bot\\})\times Q$, $\delta_{r}\colon
Q\times\Sigma_{r}\times\Gamma\to Q$ and $\delta_{\mathit{int}}\colon
Q\times\Sigma_{\mathit{int}}\to Q$. The set of configurations $\mathrm{Conf}$
is the set of all words $\alpha q$ where $q\in Q$ is a state and
$\alpha\in\bot(\Gamma\setminus\\{\bot\\})^{*}$ is the stack content. We define
$\delta\colon\mathrm{Conf}\times\Sigma\to\mathrm{Conf}$ for each $p\in Q$ and
$a\in\Sigma$ as follows:

  * •

If $a\in\Sigma_{c}$ and $\delta(p,a)=(\gamma,q)$ then $\delta(\alpha
p,a)=\alpha\gamma q$.

  * •

If $a\in\Sigma_{\mathit{int}}$ and $\delta(p,a)=q$ then $\delta(\alpha
p,a)=\alpha q$.

  * •

If $a\in\Sigma_{r}$, $\delta(p,a,\gamma)=q$ and
$\gamma\in\Gamma\setminus\\{\bot\\}$ then $\delta(\alpha\gamma p,a)=\alpha q$.

  * •

If $a\in\Sigma_{r}$ and $\delta(p,a,\bot)=q$ then $\delta(\bot p)=\bot q$.

As usual we inductively extend $\delta$ to a function
$\delta\colon\mathrm{Conf}\times\Sigma^{*}\to\mathrm{Conf}$ where
$\delta(c,\varepsilon)=c$ and $\delta(c,wa)=\delta(\delta(c,w),a)$ for all
$w\in\Sigma^{*}$ and $a\in\Sigma$. The initial configuration is $\bot q_{0}$
and a configuration $c$ is final if $c\in\Gamma^{*}F$. A word $w\in\Sigma^{*}$
is accepted from a configuration $c$ if $\delta(c,w)$ is final. The VPA $A$
accepts $w$ if $w$ is accepted from the initial configuration. The set of all
words accepted by $A$ is denoted by $\mathsf{L}(A)$; the set of all words
accepted from $c$ is denoted by $\mathsf{L}(c)$. A language $L$ is a visibly
pushdown language (VPL) if $L=\mathsf{L}(A)$ for some VPA $A$. To exclude some
pathological cases we assume that $\Sigma_{c}\neq\emptyset$ and
$\Sigma_{r}\neq\emptyset$. In fact, if $\Sigma_{c}=\emptyset$ or
$\Sigma_{r}=\emptyset$ then any VPL over that pushdown alphabet would be
regular.

One can also define nondeterministic visibly pushdown automata in the usual
way, which can always be converted into deterministic ones [1]. This leads to
good closure properties of the class of all VPLs, as closure under Boolean
operations, concatenation and Kleene star.

The set $W$ of well-matched words forms a submonoid of $\Sigma^{*}$. Notice
that a VPA can only see the top of the stack when reading return symbols.
Therefore, the behavior of a VPA on a well-matched word is determined only by
the current state and independent of the current stack content. More
precisely, there exists a monoid homomorphism $\varphi\colon W\to Q^{Q}$ into
the finite monoid of all state transformations $Q\to Q$ such that
$\delta(\alpha p,w)=\alpha\varphi(w)(p)$ for all $w\in W$ and $\alpha
p\in\mathrm{Conf}$.

##  4 Sliding window algorithms and main results

In our context a streaming algorithm is a deterministic algorithm $A$ which
reads an input word $a_{1}\cdots a_{m}\in\Sigma^{*}$ symbol by symbol from
left to right and outputs after every prefix either $1$ or $0$. We view $A$ as
a deterministic (possibly infinite) automaton whose states are encoded by bit
strings and thus abstract away from the actual computation, see [18] for a
formal definition. A variable-size sliding window algorithm for a language
$L\subseteq\Sigma^{*}$ is a streaming algorithm $A$ which reads an input word
$a_{1}\cdots a_{m}$ over the extended alphabet
$\overline{\Sigma}=\Sigma\cup\\{\downarrow\\}$. The symbol $\downarrow$ is the
operation which removes the oldest symbol from the window. At time $0\leq
t\leq m$ the algorithm has to decide whether the active window
$\mathrm{wnd}(a_{1}\cdots a_{t})$ belongs to $L$ which is defined by

$\displaystyle\mathrm{wnd}(\varepsilon)$ $\displaystyle=\varepsilon$
$\displaystyle\qquad\mathrm{wnd}(u\\!\downarrow)$
$\displaystyle=\varepsilon\text{ if }\mathrm{wnd}(u)=\varepsilon$
$\displaystyle\mathrm{wnd}(ua)$ $\displaystyle=\mathrm{wnd}(u)a$
$\displaystyle\mathrm{wnd}(u\\!\downarrow)$ $\displaystyle=v\text{ if
}\mathrm{wnd}(u)=av$

for $u\in\Sigma^{*}$, $a\in\Sigma$. For example, a variable-size sliding
window algorithm $A$ for the language $L_{a}=\\{w\in\\{a,b\\}^{*}\mid w\text{
contains }a\\}$ maintains the window length $n$ and the position $i$ (from the
right) of the most recent $a$-symbol in the window (if it exists): We
initialize $n:=0$ and $i:=\infty$. On input $a$ we increment $n$ and set
$i:=1$, on input $b$ we increment both $n$ and $i$. On input $\downarrow$ we
decrement $n$, unless $n=0$, and then set $i:=\infty$ if $i>n$.

The space complexity of $A$ is the function which maps $n$ to the maximum
number of bits used when reading an input $a_{1}\cdots a_{m}$ where the window
size never exceeds $n$, i.e. $|\mathrm{wnd}(a_{1}\cdots a_{t})|\leq n$ for all
$0\leq t\leq n$. Notice that this function is monotonic. For every language
$L$ there exists a space optimal variable-size sliding window algorithm [19,
Lemma 3.1] and we write $V_{L}(n)$ for its space complexity. Clearly we have
$V_{L}(n)\in O(n)$. For example the example language $L_{a}$ above satisfies
$V_{L_{a}}(n)\in O(\log n)$ because the algorithm above only maintains two
numbers using $O(\log n)$ bits. The main result of this paper states:

######  Theorem 4.1 (Trichotomy for VPL).

If $L$ is a visibly pushdown language then $V_{L}(n)$ is either $O(1)$,
$\Theta(\log n)$ or $O(n)\setminus o(n)$.

In the rest of this section we will give an overview of the proof of Theorem
4.1.

### Suffix expansions.

Let $\sim$ be an equivalence relation on $\Sigma^{*}$. The suffix expansion of
$\sim$ is the equivalence relation $\approx$ on $\Sigma^{*}$ defined by
$a_{1}\cdots a_{n}\approx b_{1}\cdots b_{m}$ if and only if $n=m$ and
$a_{i}\cdots a_{n}\sim b_{i}\cdots b_{n}$ for all $1\leq i\leq n$. Notice that
$\approx$ saturates each subset $\Sigma^{\leq n}$. Furthermore, if $\sim$ is a
right congruence then so is $\approx$ since $|u|=|v|$ implies $|ua|=|va|$ and
$a_{i}\cdots a_{n}\sim b_{i}\cdots b_{n}$ implies $a_{i}\cdots a_{n}a\sim
b_{i}\cdots b_{n}a$. We also define suffix expansions for partial functions
$t\colon\Sigma^{*}\to Y$ with suffix-closed domain $\mathrm{dom}(t)$. The
suffix expansion of $t$ is the total function $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
t\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}\colon\mathrm{dom}(t)\to Y^{*}$ defined by
$\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
t\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}(a_{1}\cdots a_{n})=t(a_{1}\cdots
a_{n})\,t(a_{2}\cdots a_{n})\,\cdots\,t(a_{n-1}a_{n})\,t(a_{n})$ for all
$a_{1}\cdots a_{n}\in\Sigma^{*}$. Here the range of
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern 3.0mu$}}$ is the
free monoid (alternatively, the set of all sequences) over $Y$. If $\sim$ is
an equivalence relation on $\Sigma^{*}$ then its suffix expansion $\approx$ is
the kernel of $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{\sim}$, i.e. $x\approx y$ if and only if
$\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{\sim}(x)=\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{\sim}(y)$. The space complexity in the variable-size
model is captured by the suffix expansion $\approx_{L}$ of the Myhill-Nerode
right congruence $\sim_{L}$ or alternatively by the suffix expansion
$\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{L}$ of $\nu_{L}$.

######  Theorem 4.2 ([18, Theorem 4.1]).

For all $\emptyset\subsetneq L\subsetneq\Sigma^{*}$ we have
$V_{L}(n)=\log|\Sigma^{\leq n}/{\approx_{L}}|=\log|\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{L}(\Sigma^{\leq n})|$. In particular,
$V_{L}(n)=\Omega(\log n)$ for every non-trivial language.

If $L$ is empty or universal, then $V_{L}(n)\in O(1)$ and otherwise
$V_{L}(n)=\Omega(\log n)$. Hence to prove Theorem 4.1 it suffices to show that
either $V_{L}(n)\in O(\log n)$ or $V_{L}(n)\notin o(n)$ holds for every VPL
$L$. If $L$ is a regular language and $A$ is the minimal DFA of $L$ with state
set $Q$, one can identify $\nu_{L}(x)$ with the state $q\in Q$ reached on
input $x$. Hence, $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{L}(x)$ is represented by a word over $Q$. Using the
transition monoid of $A$ one can show that $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{L}\colon\Sigma^{*}\to Q^{*}$ is rational (in fact
right-subsequential, see Section 6) and hence the image $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{L}(\Sigma^{*})\subseteq Q^{*}$ is regular [19, Lemma
4.2]. Since the growth of $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{L}(\Sigma^{*})$ is either polynomial or exponential
this implies that $V_{L}(n)\in O(\log n)$ or $V_{L}(n)\notin o(n)$.

### Restriction to descending words.

The approach above for regular languages can be extended to visibly pushdown
languages $L$ if we restrict ourselves to the set $D$ of descending words. If
a VPA with state set $Q$ reads a descending word $x\in D$ from the initial
configuration it reaches some configuration $\bot q$ with empty stack. Notice
that there may be distinct configurations $\bot p\neq\bot q$ with
$\mathsf{L}(\bot p)=\mathsf{L}(\bot q)$, in which case we need to pick a
single representative. Since every suffix of $x$ is again descending we can
represent $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{L}(x)$ by a word $\sigma_{0}(x)\in Q^{*}$ and in fact
we will prove that $S_{0}=\sigma_{0}(D)$ is a context-free language (Lemma
5.5). By the growth theorem for context-free languages the growth of $S_{0}$
is either polynomial or exponential. If $S_{0}$ grows exponentially we obtain
an exponential lower bound on $|\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{L}(\Sigma^{\leq n})|$ (Lemma 5.7). Hence, the
interesting case is that $S_{0}$ has polynomial growth, i.e. $S_{0}$ is
bounded.

### Representation by rational functions.

In order to simulate a VPA by a finite automaton on arbitrary words we will
“flatten” the input word in the following way. The input word $w$ is
factorized $w=w_{0}w_{1}\cdots w_{m}$ into a descending prefix $w_{0}$, and
call letters and well-matched factors $w_{1},\dots,w_{m}$. The descending
prefix $w_{0}$ is replaced by $\sigma_{0}(w_{0})$ and each well-matched factor
$w_{i}$ is replaced by a similar information $\sigma_{1}(w_{i})$ which
describes the behavior of the VPA on the factor $w_{i}$ and on each of its
suffixes. The set $\mathrm{Flat}$ of all flattenings is a context-free
language. Furthermore, there exists a rational function $\nu_{f}$ such that,
if a flattening $s$ represents a word $w\in\Sigma^{*}$ then $\nu_{f}(s)$ is a
configuration representing the Myhill-Nerode class $\nu_{L}(w)$ (Proposition
5.4). Hence, we can reduce proving the main theorem to the question whether
the $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{f}$-growth of $\mathrm{Flat}$ is always either
polynomial or exponential.

This question is resolved positively as follows. We prove that for every
rational function $t$ with suffix-closed domain $X=\mathrm{dom}(t)$ the
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern 3.0mu$}}$ -growth
of $X$ is either polynomial or exponential (Theorem 4.7). In the case that
$S_{0}$ has polynomial growth we can overapproximate $\mathrm{Flat}$ by a
regular superset $\mathrm{RegFlat}$. If the $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{f}$-growth of $\mathrm{RegFlat}$ is polynomial then
the same holds trivially for the subset $\mathrm{Flat}$. If the
$\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{f}$-growth of $\mathrm{RegFlat}$ is exponential then
the proper choice of $\mathrm{RegFlat}$ ensures that $\mathrm{Flat}$ also has
exponential $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{f}$-growth (Proposition 5.12).

### Dichotomy for rational functions.

The main technical result of this paper states that for every rational
function $t\colon\Sigma^{*}\to\Omega^{*}$ with suffix-closed domain
$X=\mathrm{dom}(t)$ the  $\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle
t\mkern 3.0mu$}}$ -growth of $X$ is either polynomial or exponential. We
emphasize that the range of
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern 3.0mu$}}$ is not
$\Omega^{*}$ but the free monoid over $\Omega^{*}$ (consisting of all finite
sequences of words over $\Omega$). There are in fact two reasons for
exponential  $\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$ -growth: (i) The image $t(X)$ has exponential growth, and (ii) $X$
contains a so called linear fooling set. We need these lower bounds in the
more general setting where $X\subseteq\mathrm{dom}(t)$ is a context-free
subset, namely $X=\mathrm{Flat}$.

######  Proposition 4.3.

Let $t\colon\Sigma^{*}\to\Omega^{*}$ be rational with suffix-closed domain. If
$X\subseteq\mathrm{dom}(t)$ is context-free and $t(X)$ has exponential growth
then $X$ has exponential $t$-growth and exponential
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern 3.0mu$}}$ -growth.

######  Example 4.4.

Consider the transduction $f\colon\\{a,b\\}^{*}\to a^{*}$ defined by

$f=\\{(a^{n},a^{n})\mid n\in\mathbb{N}\\}\cup\\{(a^{n}bw,a^{n})\mid
n\in\mathbb{N},w\in\\{a,b\\}^{*}\\},$

which projects a word over $\\{a,b\\}$ to its left-most (maximal) $a$-block
and is rational. Its image $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
f\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle f\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
f\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
f\mkern 2.0mu$}}$}\mkern-2.0mu}(\\{a,b\\}^{*})$ can be identified with the set
of all sequences of natural numbers which are concatenations of monotonically
decreasing sequences of the form $(k,k-1,\dots,0)$. There are exactly $2^{n}$
of such sequences of length $n$ and hence $\\{a,b\\}^{*}$ has exponential
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle f\mkern 3.0mu$}}$ -growth.

A linear fooling scheme for a partial function $t\colon\Sigma^{*}\to Y$ is a
tuple $(u_{2},v_{2},u,v,Z)$ where $u_{2},v_{2},u,v\in\Sigma^{*}$ and
$Z\subseteq\Sigma^{*}$ such that $u_{2}$ is a suffix of $u$ and $v_{2}$ is a
suffix of $v$, $|u_{2}|=|v_{2}|$,
$\\{u_{2},v_{2}\\}\\{u,v\\}^{*}Z\subseteq\mathrm{dom}(t)$ and for all
$n\in\mathbb{N}$ there exists a word $z_{n}\in Z$ of length $|z_{n}|\leq O(n)$
such that $t(u_{2}wz_{n})\neq t(v_{2}wz_{n})$ for all $w\in\\{u,v\\}^{\leq
n}$. The set $\\{u_{2},v_{2}\\}\\{u,v\\}^{*}Z$ is called a linear fooling set
for $t$. Notice that the definition implies that $u_{2}\neq v_{2}$ and hence
$u$ is not a suffix of $v$, and vice versa, i.e. $\\{u,v\\}$ is a suffix code.
Therefore $\\{u,v\\}^{n}$ contains $2^{n}$ words of length $O(n)$ and thus
$\\{u_{2},v_{2}\\}\\{u,v\\}^{*}$ has exponential growth.

######  Proposition 4.5.

Let $t\colon\Sigma^{*}\to\Omega^{*}$ be a partial function with suffix-closed
domain. If $X\subseteq\mathrm{dom}(t)$ contains a linear fooling set for $t$
then the  $\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$ -growth of $X$ is exponential.

######  Proof 4.6.

Let $(u_{2},v_{2},u,v,Z)$ be a linear fooling scheme with
$\\{u_{2},v_{2}\\}\\{u,v\\}^{*}Z\subseteq X$. Let $n\in\mathbb{N}$ and let
$z_{n}\in Z$ with the properties from the definition. Consider two distinct
words $w,w^{\prime}\in\\{u,v\\}^{n}$. Without loss of generality the words
have the form $w=w_{1}uw_{2}$ and $w^{\prime}=w_{3}vw_{2}$ for some
$w_{1},w_{2},w_{3}\in\\{u,v\\}^{*}$. Hence $w$ has the suffix $u_{2}w_{2}$ and
$w^{\prime}$ has the suffix $v_{2}w_{2}$, which are suffixes of the same
length. By assumption we have $t(u_{2}w_{2}z_{n})\neq t(v_{2}w_{2}z_{n})$ and
hence also $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
t\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}(wz_{n})\neq\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
t\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}(w^{\prime}z_{n})$. This implies that
$|\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
t\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}(u_{2}\\{u,v\\}^{n}z_{n})|\geq 2^{n}$ for all
$n\in\mathbb{N}$. Since all words in $u_{2}\\{u,v\\}^{n}z_{n}\subseteq X$ have
length $O(n)$ there exists a number $c>1$ such that $|\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
t\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}(X\cap\Sigma^{\leq cn})|\geq 2^{n}$ for
sufficiently large $n$.

The following dichotomy theorem will be proved in Section 6.

######  Theorem 4.7.

Let $t\colon\Sigma^{*}\to\Omega^{*}$ be rational and with suffix-closed domain
$X=\mathrm{dom}(t)$. If $X$ contains no linear fooling set for $t$ and $t(X)$
is bounded then the  $\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle
t\mkern 3.0mu$}}$ -growth of $X$ is polynomial. Otherwise the
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern 3.0mu$}}$ -growth
of $X$ is exponential.

##  5 Reduction to transducer problem

Fix a VPA $A=(Q,\tilde{\Sigma},\Gamma,\bot,q_{0},\delta,F)$ and let
$\emptyset\subsetneq L=\mathsf{L}(A)\subsetneq\Sigma^{*}$ for the rest of this
section.

### Monotonic factorization.

A factorization of $w=w_{0}w_{1}\cdots w_{m}\in\Sigma^{*}$ into factors
$w_{i}\in\Sigma^{*}$ is monotonic if $w_{0}$ is descending (possibly empty)
and for each $1\leq i\leq m$ the factor $w_{i}$ is either a call letter
$w_{i}\in\Sigma_{c}$ or a non-empty well-matched factor. If $w_{0}w_{1}\cdots
w_{m}$ is a monotonic factorization then $w_{i}^{\prime}w_{i+1}\cdots w_{j}$
is a monotonic factorization for any $0\leq i\leq j\leq m$ and suffix
$w_{i}^{\prime}$ of $w_{i}$. To see that every word $w\in\Sigma^{*}$ has at
least one monotonic factorization consider the set of non-empty maximal well-
matched factors in $w$ (maximal with respect to inclusion). Observe that two
distinct maximal well-matched factors in a word cannot overlap because the
union of two overlapping well-matched factors is again well-matched. Since
every internal letter is well-matched the remaining positions contain only
return and call letters. Furthermore, every remaining call letter must be to
the right of every remaining return letter, which yields a monotonic
factorization of $w$. Figure 1 shows a monotonic factorization
$w=w_{0}w_{1}\cdots w_{m}$ where the descending prefix $w_{0}$ is colored red
and call letters $w_{i}$ are colored green. The stack height function for the
word $w$ increases (decreases) by one on call (return) letters and stays
constant on internal letters.

$b$$c$$a$$b$$b$$c$$a$$b$$a$$a$$b$$c$$a$$a$$a$$b$$a$$b$$b$$a$

Figure 1: The stack height function for a word ($\Sigma_{c}=\\{a\\}$,
$\Sigma_{r}=\\{b\\}$, $\Sigma_{\mathit{int}}=\\{c\\}$) and a monotonic
factorization $bcabb\leavevmode\nobreak\ cab\leavevmode\nobreak\
a\leavevmode\nobreak\ abc\leavevmode\nobreak\ a\leavevmode\nobreak\
aababb\leavevmode\nobreak\ a$.

### Representation of Myhill-Nerode classes.

To apply Theorem 4.2 we need a suitable description of the $\sim_{L}$-classes.
We follow the approach in [5] of choosing length-lexicographic minimal
representative configurations. Since their definition slightly differs from
ours (according to their definition, a VPA may not read a return letter if the
stack contains $\bot$ only) we briefly recall their argument (in the
appendix). Let $\mathrm{rConf}=\\{\delta(\bot q_{0},w)\mid w\in\Sigma^{*}\\}$
be the set of all reachable configurations in $A$, which is known to be
regular [7, 11]. Two configurations $c_{1},c_{2}\in\mathrm{rConf}$ are
equivalent, denoted by $c_{1}\sim c_{2}$, if
$\mathsf{L}(c_{1})=\mathsf{L}(c_{2})$. By fixing arbitrary linear orders on
$\Gamma$ and $Q$ we can consider the length-lexicographical order on
$\mathrm{rConf}$ and define the function
$\mathsf{rep}\colon\mathrm{rConf}\to\mathrm{rConf}$ which chooses the minimal
representative from each $\sim$-class, i.e. for all $c\in\mathrm{rConf}$ we
have $\mathsf{rep}(c)\sim c$ and for any $c^{\prime}\in\mathrm{rConf}$ with
$c\sim c^{\prime}$ we have $\mathsf{rep}(c)\leq_{\mathit{llex}}c^{\prime}$.
The set of representative configurations is denoted by
$\mathrm{Rep}=\mathsf{rep}(\mathrm{rConf})$.

######  Lemma 5.1 ([5]).

The function $\mathsf{rep}$ is rational.

Finally we define $\nu_{A}\colon\Sigma^{*}\to\mathrm{Rep}$ by
$\nu_{A}(w)=\mathsf{rep}(\delta(\bot q_{0},w))$ for all $w\in\Sigma^{*}$. It
represents $\sim_{L}$ in the sense that
$\mathsf{L}(\nu_{A}(w))=w^{-1}\mathsf{L}(A)$ for all $w\in\Sigma^{*}$ and
hence $\nu_{A}(u)=\nu_{A}(v)$ if and only if $u\sim_{L}v$. Therefore we have
$V_{L}(n)=\log|\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{A}(\Sigma^{\leq n})|$ by Theorem 4.2.

### Flattenings.

Since we cannot compute $\nu_{A}$ using a finite state transducer we choose a
different representation of the input. Define the alphabet
$\Sigma_{f}=\Sigma_{c}\cup Q\cup Q^{Q}$. A flattening is a word
$s_{0}s_{1}\cdots s_{m}\in\Sigma_{f}^{*}$ where $s_{0}\in Q^{*}$ and
$s_{i}\in\Sigma_{c}\cup Q^{Q}Q^{*}$ for all $1\leq i\leq m$. Notice that the
factorization $s=s_{0}s_{1}\cdots s_{m}$ is unique. The set of all flattenings
is $\mathrm{AllFlat}=Q^{*}(\Sigma_{c}\cup Q^{Q}Q^{*})^{*}$. We define a
function $t_{f}\colon\mathrm{AllFlat}\to\mathrm{rConf}$ as follows. Let
$s=s_{0}s_{1}\cdots s_{m}\in\Sigma_{f}^{*}$ be a flattening and we define
$t_{f}(s)$ by induction on $m$:

  * •

If $s_{0}=\varepsilon$ then $t_{f}(s_{0})=\bot q_{0}$. If $s_{0}=q_{1}\cdots
q_{n}\in Q^{+}$ then $t_{f}(s_{0})=\bot q_{1}$.

  * •

If $s_{m}\in\Sigma_{c}$ then $t_{f}(s_{0}\cdots
s_{m})=\delta(t_{f}(s_{0}\cdots s_{m-1}),s_{m})$.

  * •

If $s_{m}=\tau q_{2}\cdots q_{m}\in Q^{Q}Q^{*}$ and $t_{f}(s_{0}\cdots
s_{m-1})=\alpha q$ then $t_{f}(s)=\alpha\tau(q)$.

Define the function $\nu_{f}\colon\mathrm{AllFlat}\to\mathrm{Rep}$ by
$\nu_{f}=\mathsf{rep}\circ t_{f}$.

######  Lemma 5.2.

The functions $t_{f}$ and $\nu_{f}$ are rational.

######  Proof 5.3.

We first define a transducer $A_{1}$ which handles flattenings where the
initial factor is empty. Let
$A_{1}=(Q,\Sigma_{f},Q\cup\Gamma,\\{q_{0}\\},\Delta^{\prime},Q,o)$ with the
following transitions:

  * •

$p\xrightarrow{q\mid\varepsilon}p$ for all $p,q\in Q$

  * •

$p\xrightarrow{a\mid\gamma}q$ for all $\delta(p,a)=(\gamma,q)$ where
$a\in\Sigma_{c}$

  * •

$p\xrightarrow{\tau\mid\varepsilon}\tau(p)$ for all $p\in Q,\tau\in Q^{Q}$

and $o(q)=q$. For each $p\in Q$ let $t_{p}$ be the rational function defined
by $A_{1}$ with the only initial state $p$. One can easily show that for all
$s\in\mathrm{AllFlat}$ we have $t_{f}(s)=\bot t_{q_{0}}(s)$ and
$t_{f}(q_{1}\cdots q_{k}s)=\bot t_{q_{1}}(s)$ for all $q_{1}\cdots q_{k}\in
Q^{+}$. Hence we can prove that $t_{f}$ is rational by providing a transducer
for $t_{f}$: First it verifies whether the input word belongs to the regular
language $\mathrm{AllFlat}\subseteq\Sigma_{f}^{*}$. Simultaneously, it
verifies whether the input word starts with a state $q\in Q$. If so, it
memorizes $q$ and simulates $A_{1}$ on $s^{\prime}$ from $q$, and otherwise
$A_{1}$ is directly simulated on $s$ from $q_{0}$. Since $\mathsf{rep}$ is
rational by Lemma 5.1, $\nu_{f}$ is also rational.

If $w=a_{1}\cdots a_{n}\in D$ is a descending word then $\delta(\bot
q_{0},w)=\bot p$ for some $p\in Q$. By definition of $\nu_{A}$ there exists a
state $q\in Q$ with $\nu_{A}(w)=\bot q$. Since each suffix of $w$ is also
descending we have $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{A}(w)=\bot q_{1}\,\bot q_{2}\cdots\bot q_{n}$ for
some $q_{1},\dots,q_{n}\in Q$. We define $\sigma_{0}(w)=q_{1}\cdots q_{n}\in
Q^{*}$, i.e. we remove the redundant $\bot$-symbols from $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{A}(w)$. If $w$ is non-empty and well-matched we
additionally define $\sigma_{1}(w)=\tau q_{2}\cdots q_{n}\in Q^{Q}Q^{*}$ where
$\tau=\varphi(w)$. We define the sets $S_{0}=\sigma_{0}(D)$ and
$S_{1}=\sigma_{1}(W\setminus\\{\varepsilon\\})$. Notice that $S_{0}$ is
exactly the set of proper suffixes of words from $S_{1}$ since descending
words are exactly the (proper) suffixes of well-matched words. We say that
$s=s_{0}s_{1}\cdots s_{m}\in\mathrm{AllFlat}$ represents a word
$w\in\Sigma^{*}$ if there exists a monotonic factorization $w=w_{0}w_{1}\cdots
w_{m}\in\Sigma^{*}$ such that $s_{0}=\sigma_{0}(w_{0})$, and for all $1\leq
i\leq m$ if $w_{i}$ is well-matched, then $s_{i}=\sigma_{1}(w_{i})$, and if
$w_{i}\in\Sigma_{c}$ then $s_{i}=w_{i}$. Since a word may have different
monotonic factorizations, it may also be represented by many flattenings. We
define the suffix-closed set $\mathrm{Flat}=S_{0}(\Sigma_{c}\cup S_{1})^{*}$,
containing all flattenings which represent some word.

######  Proposition 5.4.

If $s\in\mathrm{AllFlat}$ represents $w\in\Sigma^{*}$ then
$\nu_{f}(s)=\nu_{A}(w)$. Therefore, $\nu_{f}(\mathrm{Flat})=\mathrm{Rep}$ and
$V_{L}(n)=\log|\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{f}(\mathrm{Flat}\cap\Sigma_{f}^{\leq n})|$.

######  Lemma 5.5.

The languages $S_{0}$ and $S_{1}$ are context-free.

######  Proof 5.6.

Since $S_{0}$ is the set of all proper suffixes of words from $S_{1}$ it
suffices to consider $S_{1}$. We will prove that $\\{w\otimes\sigma_{1}(w)\mid
w\in W\\}$ is a VPL over the pushdown alphabet
$(\Sigma_{c}\times\Sigma_{f},\Sigma_{r}\times\Sigma_{f},\Sigma_{\mathit{int}}\times\Sigma_{f})$.
Since the class of context-free languages is closed under projections it then
follows that $S_{1}$ is context-free. A VPA can test whether the first
component $w=a_{1}\cdots a_{n}$ is well-matched and whether the second
component has the form $\tau q_{2}\cdots q_{n}\in Q^{Q}Q^{*}$. Since VPLs are
closed under Boolean operations, it suffices to test whether
$\tau\neq\varphi(w)$ or there exists a state $q_{i}$ with $\nu_{A}(a_{i}\cdots
a_{n})\neq\bot q_{i}$. To guess an incorrect state we use a VPA whose stack
alphabet contains all stack symbols of $A$ and a special symbol $\\#$
representing the stack bottom. We guess and read a prefix of the input word
and push/pop only the special symbol $\\#$ on/from the stack. Then at some
point we store the second component $q_{i}$ in the next symbol and simulate
$A$ on the remaining suffix. Finally, we accept if and only if the reached
state is $q$ and $\mathsf{rep}(\bot q)\neq\bot q_{i}$. Similarly, we can
verify $\tau$ by testing whether there exists a state $p\in Q$ with
$\varphi(w)(p)\neq\tau(p)$.

######  Lemma 5.7.

The language $S_{0}$ is bounded if and only if $S_{1}$ is bounded. If $S_{0}$
is not bounded then the $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{A}$-growth of $\Sigma^{*}$ is exponential and
therefore $V_{L}(n)\notin o(n)$.

######  Proof 5.8.

Assume that $S_{0}\subseteq s_{1}^{*}\cdots s_{k}^{*}$ is bounded. Since
$S_{1}\subseteq\bigcup\\{\tau S_{0}\mid\tau\in Q^{Q}\\}$ we have
$S_{1}\subseteq\tau_{1}^{*}\cdots\tau_{m}^{*}s_{1}^{*}\cdots s_{k}^{*}$ for
any enumeration $\tau_{1},\dots,\tau_{m}$ of $Q^{Q}$. Conversely, if $S_{1}$
is bounded then each word in $S_{0}$ is a factor, namely a proper suffix, of a
word from $S_{1}$. Therefore $S_{0}$ must be also bounded.

If the context-free language $S_{0}=\sigma_{0}(D)\subseteq Q^{*}$ is not
bounded then its growth must be exponential. Recall that $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{A}(w)$ and $\sigma_{0}(w)$ are equal for all $w\in D$
up to the $\bot$-symbol. Hence $|\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{A}(\Sigma^{\leq n})|\geq|\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{A}(D\cap\Sigma^{\leq
n})|=|\sigma_{0}(D\cap\Sigma^{\leq n})|=|S_{0}\cap Q^{\leq n}|$, which proves
the growth bound.

### Bounded overapproximation.

By Lemma 5.7 we can restrict ourselves to the case that $S_{0}$ and $S_{1}$
are bounded languages, which will be assumed in the following. We define
$\Psi(a_{1}\cdots a_{n})=\\{(a_{1},n),(a_{2},n-1)\dots,(a_{n},1)\\}$ and
$\Psi(L)=\bigcup_{w\in L}\Psi(w)$.

######  Lemma 5.9.

Let $K$ be a bounded context-free language. Then there exists a bounded
regular superset $R\supseteq K$ such that $\\{|w|\mid w\in K\\}=\\{|w|\mid
w\in R\\}$ and $\Psi(K)=\Psi(R)$, called a bounded overapproximation of $K$.

######  Proof 5.10.

We use Parikh’s theorem [26], which implies that for every context-free
language $K\subseteq\Sigma^{*}$ the set $\\{|w|\mid w\in K\\}$ is semilinear,
i.e. a finite union of arithmetic progressions, and hence
$\\{v\in\Sigma^{*}\mid\exists w\in K:|v|=|w|\\}$ is a regular language. Assume
that $K\subseteq w_{1}^{*}\cdots w_{k}^{*}$ for some
$w_{1},\dots,w_{k}\in\Sigma^{*}$. We define

$R=(w_{1}^{*}\cdots w_{k}^{*})\cap\\{v\in\Sigma^{*}\mid\exists w\in
K:|v|=|w|\\}\cap\\{w\in\Sigma^{*}\mid\Psi(w)\subseteq\Psi(K)\\}.$

Clearly, $K$ is contained in $R$ and it remains to verify that the third part
is regular. It suffices to show that for each $a\in\Sigma$ the set
$P_{a}=\\{i\mid(a,i)\in\Psi(K)\\}$ is semilinear because then an automaton can
verify the property $\Psi(w)\subseteq\Psi(K)$. Consider the transducer

$T_{a}=\\{(a_{1}\cdots a_{n},\Box^{n-i+1})\mid a_{1}\cdots
a_{n}\in\Sigma^{*},\,a_{i}=a\\}.$

It is easy to see that $T_{a}$ is rational and $T_{a}K=\\{\Box^{i}\mid i\in
P_{a}\\}$. The claim follows again from Parikh’s theorem.

For each $\tau\in Q^{Q}$ let $R_{\tau}$ be a bounded overapproximation of
$\tau^{-1}S_{1}$ and let $R_{1}=\bigcup_{\tau\in Q^{Q}}(\tau R_{\tau})$. Let
$R_{0}=\bigcup_{\tau\in Q^{Q}}\mathsf{Suf}(R_{\tau})$, which is the set of all
proper suffixes of words in $R_{1}$. Both $R_{0}$ and $R_{1}$ are also bounded
languages. Finally, set $\mathrm{RegFlat}=R_{0}(\Sigma_{c}\cup R_{1})^{*}$,
which is the same as $\mathsf{Suf}((\Sigma_{c}\cup R_{1})^{*})$ and is suffix-
closed. According to the definition of bounded overapproximations we can
approximate a word $v=\tau q_{2}\cdots q_{k}\in R_{1}$ in two possible ways:
Firstly, define $\mathsf{apx}_{\ell}(v)$ to be any word of the form
$\mathsf{apx}_{\ell}(v)=\tau p_{2}\cdots p_{k}\in S_{1}$ with
$|v|=|\mathsf{apx}_{\ell}(v)|$. Secondly, for any position $2\leq i\leq k$
define $\mathsf{apx}_{i}(v)$ to be any word $\mathsf{apx}_{i}(v)=\tau
s^{\prime}q_{i}p_{i+1}\cdots p_{k}\in S_{1}$ where $s^{\prime},p_{i+1}\cdots
p_{k}\in Q^{*}$. If $r=r_{0}r_{1}\cdots r_{m}\in\mathrm{RegFlat}$ then we can
replace any internal factor $r_{i}\in R_{1}$ by $\mathsf{apx}_{\ell}(r_{i})$
or any $\mathsf{apx}_{j}(r_{i})$ without changing the value of $\nu_{f}(r)$.

######  Proposition 5.11.

$\nu_{f}(\mathrm{Flat})=\nu_{f}(\mathrm{RegFlat})=\mathrm{Rep}$.

######  Proposition 5.12.

If $\mathrm{RegFlat}$ contains a linear fooling set for $\nu_{f}$ then also
$\mathrm{Flat}$ contains a linear fooling set for $\nu_{f}$.

######  Proof 5.13 (Proof of Theorem 4.1).

If $L=\emptyset$ or $L=\Sigma^{*}$ then $V_{L}(n)\in O(1)$. Now assume
$\emptyset\subsetneq L\subsetneq\Sigma^{*}$, in which case we have
$V_{L}(n)=\Omega(\log n)$. Furthermore we know that
$V_{L}(n)=\log|\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{f}(\mathrm{Flat}\cap\Sigma_{f}^{\leq n})|$ by
Proposition 5.4. If the constructed language $S_{0}$ is not bounded then
$V_{L}(n)\notin o(n)$ by Lemma 5.7. Now assume that $S_{0}$ is bounded, in
which case we can construct the regular language $\mathrm{RegFlat}$. By
Theorem 4.7 the $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{f}$-growth of $\mathrm{RegFlat}$ is either polynomial
or exponential (formally, we have to restrict the domain of $\nu_{f}$ to the
regular language $\mathrm{RegFlat}$). If the $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{f}$-growth of $\mathrm{RegFlat}$ is polynomial then
the same holds for its subset $\mathrm{Flat}$, and hence $V_{L}(n)\in O(\log
n)$. If the $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{f}$-growth of $\mathrm{RegFlat}$ is exponential then
by Theorem 4.7 either the image $\nu_{f}(\mathrm{RegFlat})$ is not bounded or
$\mathrm{RegFlat}$ contains a linear fooling set for $\nu_{f}$. By Proposition
5.11 we have $\nu_{f}(\mathrm{RegFlat})=\nu_{f}(\mathrm{Flat})=\mathrm{Rep}$.
Hence, if $\mathrm{Rep}$ has exponential growth then Proposition 4.3 implies
that $\mathrm{Flat}$ has exponential $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{f}$-growth and hence $V_{L}(n)\notin o(n)$. If
$\mathrm{RegFlat}$ contains a linear fooling set for $\nu_{f}$ then also
$\mathrm{Flat}$ contains one by Proposition 5.12. By Proposition 4.5 the
$\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{f}$-growth of $\mathrm{Flat}$ is exponential and
hence $V_{L}(n)\notin o(n)$.

##  6 Dichotomy for rational functions

In this section we will prove Theorem 4.7. Let
$t\colon\Sigma^{*}\to\Omega^{*}$ be a rational function with suffix-closed
domain $X=\mathrm{dom}(t)$. By Proposition 4.3 the interesting case is where
the image $t(X)$ is polynomial growing, i.e. a bounded language. There are two
further necessary properties in order to achieve polynomial
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern 3.0mu$}}$ -growth.
Since we apply the rational function to all suffixes, it is natural to
consider right transducers, reading the input from right to left. The first
property states that $t$ has to resemble so called right-subsequential
functions, which are defined by deterministic finite right transducers. Here
we will make use of a representation of rational functions due to Reutenauer
and Schützenberger, which decomposes the rational function $t$ into a right
congruence $\mathcal{R}_{t}$ and a right-subsequential transducer $B$ [27].
Secondly, we demand that $B$ is well-behaved, which means that, roughly
speaking, the output produced during a run inside a strongly connected
component only depends on its entry state and the length of the run. We will
prove that in fact these properties are sufficient for the polynomial
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern 3.0mu$}}$ -growth
and in all other cases $X$ contains a linear fooling set.

### The case of finite-index right congruences.

Let $\sim$ be a finite index right congruence on $\Sigma^{*}$ and $\approx$
its suffix expansion. We will characterize those finite index right
congruences $\sim$ where $\Sigma^{\leq n}/{\approx}$ is polynomially bounded,
which can be viewed as a special case of Theorem 4.7 since
$\nu_{\sim}\colon\Sigma^{*}\to\Sigma^{*}/{\sim}$ is rational. First assume
that $\sim$ is the Myhill-Nerode right congruence $\sim_{L}$ of a regular
language $L$. Since $\log|\Sigma^{\leq n}/{\approx}|$ is exactly the space
complexity $V_{L}(n)$ by Theorem 4.2, this case was characterized in [18]
using so called critical tuples in the minimal DFA for $L$. We slightly adapt
this definition for right congruences. A critical tuple in a right congruence
$\sim$ is a tuple of words $(u_{2},v_{2},u,v)\in(\Sigma^{*})^{4}$ such that
$|u_{2}|=|v_{2}|\geq 1$, there exist $u_{1},v_{1}\in\Sigma^{*}$ with
$u=u_{1}u_{2}$, $v=v_{1}v_{2}$, and $u_{2}w\not\sim v_{2}w$ for all
$w\in\\{u,v\\}^{*}$.

######  Proposition 6.1.

If $\sim$ has a critical tuple then $|\Sigma^{\leq n}/{\approx}|$ grows
exponentially and there exists a critical tuple $(u_{2},v_{2},u,v)$ in $\sim$
such that $u_{2}u\sim u_{2}wu$ and $v_{2}u\sim v_{2}wu$ for all
$w\in\\{u,v\\}^{*}$.

######  Proof 6.2.

If $(u_{2},v_{2},u,v)$ is critical tuple in a right congruence $\sim$ then we
claim that $|\Sigma^{\leq n}/{\approx}|$ grows exponentially. Let
$n\in\mathbb{N}$ and let $w\neq w^{\prime}\in\\{u,v\\}^{n}$. There exists a
word $z\in\\{u,v\\}^{*}$ such that $w$ and $w^{\prime}$ have the suffixes
$u_{2}z$ and $v_{2}z$ of equal length. By the definition of critical tuples we
have $u_{2}z\not\sim v_{2}z$, which implies $w\not\approx w^{\prime}$.
Therefore $|\Sigma^{\leq cn}/{\approx}|\geq 2^{n}$ where
$c=\max\\{|u|,|v|\\}$.

The second part is based on the proof of [19, Lemma 7.4]. Let $\equiv$ be the
syntactic congruence on $\Sigma^{*}$ defined by $x\equiv y$ if and only if
$\ell x\sim\ell y$ for all $\ell\in\Sigma^{*}$. Since $\sim$ is a right
congruence $\equiv$ is a congruence on $\Sigma^{*}$ of finite index satisfying
$\equiv\,\subseteq\,\sim$. Define the monoid $M=\Sigma^{*}/{\equiv}$. It is
known that there exists a number $\omega\in\mathbb{N}$ such that $m^{\omega}$
is idempotent for all $m\in M$, i.e. $m^{\omega}\cdot m^{\omega}=m^{\omega}$.
Now let $(u_{2},v_{2},u,v)$ be a critical tuple and define
$u^{\prime}=(v^{\omega}u^{\omega})^{\omega}$ and
$v^{\prime}=(v^{\omega}u^{\omega})^{\omega}v^{\omega}$. Since $u_{2}$ is a
suffix of $u^{\prime}$, $v_{2}$ is a suffix of $u^{\prime}$ and
$u^{\prime},v^{\prime}\in\\{u,v\\}^{*}$ the tuple
$(u_{2},v_{2},u^{\prime},v^{\prime})$ is again a critical tuple in $\sim$.
Furthermore we have
$u^{\prime}u^{\prime}=(v^{\omega}u^{\omega})^{\omega}(v^{\omega}u^{\omega})^{\omega}\equiv(v^{\omega}u^{\omega})^{\omega}=u^{\prime}$
and
$v^{\prime}u^{\prime}=(v^{\omega}u^{\omega})^{\omega}v^{\omega}(v^{\omega}u^{\omega})^{\omega}\equiv(v^{\omega}u^{\omega})^{\omega}=u^{\prime}$,
and therefore $u^{\prime}\equiv wu^{\prime}$ for all
$w\in\\{u^{\prime},v^{\prime}\\}^{*}$. Since $\equiv$ is a congruence this
implies $u_{2}u^{\prime}\equiv u_{2}wu^{\prime}$ and $v_{2}u^{\prime}\equiv
v_{2}wu^{\prime}$ for all $w\in\\{u^{\prime},v^{\prime}\\}^{*}$, and thus also
$u_{2}u^{\prime}\sim u_{2}wu^{\prime}$ and $v_{2}u^{\prime}\sim
v_{2}wu^{\prime}$, which concludes the proof.

######  Theorem 6.3.

Let $L\subseteq\Sigma^{*}$ be regular. Then $V_{L}(n)\in O(\log n)$ if and
only if $|\Sigma^{\leq n}/{\approx_{L}}|$ is polynomially bounded if and only
if $\sim_{L}$ has no critical tuple.

######  Proof 6.4.

The first equivalence follows from Theorem 4.2. By Proposition 6.1 the
existence of a critical tuple in $\sim$ implies exponential growth of
$|\Sigma^{\leq n}/{\approx}|$.

Now assume that $V_{L}(n)\notin O(\log n)$. By [18, Lemma 7.2] there exist
words $u_{2},v_{2},u,v\in\Sigma^{*}$ such that $u_{2}$ is a suffix of $u$,
$v_{2}$ is a suffix of $v$, $|u_{2}|=|v_{2}|$ and
$u_{2}w\not\sim_{L}v_{2}w^{\prime}$ for all $w,w^{\prime}\in\\{u,v\\}^{*}$
(one needs the fact that $x\sim_{L}y$ if and only if $x$ and $y$ reach the
same state in the minimal DFA for $L$). Since in particular
$u_{2}w\not\sim_{L}v_{2}w$ for all $w\in\\{u,v\\}^{*}$ the tuple
$(u_{2},v_{2},u,v)$ constitutes a critical tuple.

We generalize this theorem to arbitrary finite index right congruences
(Theorem 6.7). Given equivalence relations $\sim$ and $\sim^{\prime}$ on a set
$X$, we say that $\sim^{\prime}$ is coarser than $\sim$ if
$\sim\,\subseteq\,\sim^{\prime}$, i.e. each $\sim^{\prime}$-class is a union
of $\sim$-classes. The intersection $\sim\cap\sim^{\prime}$ is again an
equivalence relation on $X$.

######  Lemma 6.5.

Let $\sim$ and $\sim^{\prime}$ be right congruences.

  1. (a)

If $\sim^{\prime}$ is coarser than $\sim$ and $\sim$ has no critical tuple,
then $\sim^{\prime}$ also has no critical tuple.

  2. (b)

If $\sim$ and $\sim^{\prime}$ have no critical tuple then
$\sim\cap\sim^{\prime}$ is also a right congruence which has no critical tuple

######  Proof 6.6.

Closure under coarsening is clear because the property “$\sim$ has no critical
tuple” is positive in $\sim$: $\forall u=u_{1}u_{2}\,\forall
v=v_{1}v_{2}(|u_{2}|=|v_{2}|\to\exists w\in\\{u,v\\}^{*}:u_{2}w\sim v_{2}w)$.

Consider two right congruences $\sim$, $\sim^{\prime}$ which have no critical
tuples. One can verify that their intersection $\sim\cap\sim^{\prime}$ is
again a right congruence. Let $u=u_{1}u_{2}$ and $v=v_{1}v_{2}$ with
$|u_{2}|=|v_{2}|$. Because $\sim$ has no critical tuple there exist a word
$w\in\\{u,v\\}^{*}$ with $u_{2}w\mathrel{\sim}v_{2}w$. Now consider the
condition for the words $u_{1}(u_{2}w)$ and $v_{1}(v_{2}w)$. Because
$\sim^{\prime}$ has no critical tuple there exists a word
$x\in\\{uw,vw\\}^{*}$ such that $u_{2}wx\mathrel{\sim^{\prime}}v_{2}wx$. Since
$\sim$ is a right congruence we also have $u_{2}wx\mathrel{\sim}v_{2}wx$ and
thus $u_{2}wx\mathrel{(\sim\cap\sim^{\prime})}v_{2}wx$. This proves that
$\sim\cap\sim^{\prime}$ has no critical tuple.

######  Theorem 6.7.

$|\Sigma^{\leq n}/{\approx}|$ is polynomially bounded if and only if $\sim$
has no critical tuple.

######  Proof 6.8.

Let $u_{1},\dots,u_{m}$ be representatives from each $\sim$-class. Observe
that $\sim\,=\bigcap_{i=1}^{m}\sim_{[u_{i}]_{\sim}}$ because $\sim$ saturates
each class $[u_{i}]_{\sim}$ and $\bigcap_{i=1}^{m}\sim_{[u_{i}]_{\sim}}$ also
saturates each class $[v]_{\sim}$. Let us write $\sim_{i}$ instead of
$\sim_{[u_{i}]_{\sim}}$ and let $\approx_{i}$ be its suffix expansion
$\approx_{[u_{i}]_{\sim}}$. Then we have $\sim\,=\bigcap_{i=1}^{m}\sim_{i}$
and $\approx\,=\bigcap_{i=1}^{m}\approx_{i}$. This implies that

$\max_{1\leq i\leq m}|\Sigma^{\leq n}/{\approx_{i}}|\leq|\Sigma^{\leq
n}/{\approx}|\leq\prod_{i=1}^{m}|\Sigma^{\leq n}/{\approx_{i}}|.$ (1)

($\Rightarrow$): If $|\Sigma^{\leq n}/{\approx}|$ is polynomially bounded then
the same holds for $|\Sigma^{\leq n}/{\approx_{i}}|$ for all $1\leq i\leq k$
by (1). By Theorem 6.3 $\sim_{[u_{i}]_{\sim}}$ has no critical tuple for all
$1\leq i\leq k$ and therefore Lemma 6.5(b) implies that
$\sim\,=\bigcap_{i=1}^{m}\sim_{[u_{i}]_{\sim}}$ has no critical tuple.

($\Leftarrow$): If $\sim$ has no critical tuple then each congruence
$\sim_{i}$ has no critical tuple by Lemma 6.5(a) because $\sim_{i}$ is coarser
than $\sim$. Theorem 6.3 implies that $|\Sigma^{\leq n}/{\approx_{i}}|$ is
polynomially bounded for all $1\leq i\leq k$. By (1) also $|\Sigma^{\leq
n}/{\approx}|$ is polynomially bounded.

### Regular look-ahead.

A result due to Reutenauer and Schützenberger states that every rational
function $f$ can be factorized as $f=r\circ\ell$ where $\ell$ and $r$ are
left- and right-subsequential, respectively [27]. A rational function is left-
or right-subsequential if the input is read in a deterministic fashion from
left to right and right to left, respectively. In the literature the order of
the directions is usually reversed, i.e. one decomposes $t$ as $f=r\circ\ell$.
Often this is described by the statement that every rational function is
(left-)subsequential with regular look-ahead. Furthermore, this decomposition
is canonical in a certain sense.

We follow the notation from the survey paper [16]. A right-subsequential
transducer $B=(Q,\Sigma,\Omega,F,\Delta,\\{q_{\mathit{in}}\\},o)$ is a real-
time right transducer which is deterministic, i.e. $q_{\mathit{in}}$ is the
only initial state and for every $p\in Q$ and $a\in\Sigma$ there exists at
most one transition $(p,a,y,q)\in\Delta$. Clearly, right-subsequential
transducers define rational functions, the so called right-subsequential
functions, but not every rational function is right-subsequential. Let
$\mathcal{R}$ be a right congruence on $\Sigma^{*}$ with finite index. The
look-ahead extension is the injective function
$e_{\mathcal{R}}\colon\Sigma^{*}\to(\Sigma\times\Sigma^{*}/\mathcal{R})^{*}$
defined by

$e_{\mathcal{R}}(a_{1}\cdots
a_{n})=(a_{1},[\varepsilon]_{\mathcal{R}})(a_{2},[a_{1}]_{\mathcal{R}})(a_{3},[a_{1}a_{2}]_{\mathcal{R}})\cdots(a_{n},[a_{1}\cdots
a_{n-1}]_{\mathcal{R}}).$

Let $f\colon\Sigma^{*}\to\Omega^{*}$ be a partial function. The partial
function
$f[\mathcal{R}]\colon(\Sigma\times\Sigma^{*}/\mathcal{R})^{*}\to\Omega^{*}$
with $\mathrm{dom}(f[\mathcal{R}])=e_{\mathcal{R}}(\mathrm{dom}(f))$ is
defined by $f[\mathcal{R}](e_{\mathcal{R}}(x))=f(x)$. Furthermore we define a
right congruence $\mathcal{R}_{f}$ on $\Sigma^{*}$. For this we need the
distance function $\|x,y\|=|x|+|y|-2|x\wedge y|$ where $x\wedge y$ is the
longest common suffix of $x$ and $y$. Equivalently, $\|x,y\|$ is the length of
the reduced word of $xy^{-1}$ in the free group generated by $\Sigma$. Notice
that $\|\cdot,\cdot\|$ satisfies the triangle inequality. We define
$u\mathrel{\mathcal{R}_{f}}v$ if and only if (i) $u\sim_{\mathrm{dom}(f)}v$
and (ii) $\\{\|f(uw),f(vw)\|\mid uw,vw\in\mathrm{dom}(f)\\}$ is finite. One
can verify that $\mathcal{R}_{f}$ is a right congruence on $\Sigma^{*}$. As an
example, recall the rational transduction $f$ from Example 4.4. The induced
right congruence $\mathcal{R}_{f}$ has two classes, which are $a^{*}$ and
$a^{*}b\\{a,b\\}^{*}$.

######  Theorem 6.9 ([27]).

A partial function $f\colon\Sigma^{*}\to\Omega^{*}$ is rational if and only if
$\mathcal{R}_{f}$ has finite index and $f[\mathcal{R}_{f}]$ is right-
subsequential.

For the rest of the section let
$B=(Q,\Sigma\times\Sigma^{*}/{\mathcal{R}_{t}},\Omega,F,\Delta,\\{q_{\mathit{in}}\\},o)$
be a trim right-subsequential transducer for $t[\mathcal{R}_{t}]$. One obtains
an unambiguous real-time right transducer $A$ for $t$ by projection to the
first component, i.e. $A=(Q,\Sigma,\Omega,F,\Lambda,\\{q_{\mathit{in}}\\},o)$
where $\Lambda=\\{(q,a,y,p)\mid(q,(a,b),y,p)\in\Delta\\}$. Notice that every
run $q\xleftarrow{x\mid y}p$ in $A$ induces a corresponding run
$q\xleftarrow{(x,z)\mid y}p$ in $B$ for some
$z\in(\Sigma^{*}/{\mathcal{R}_{t}})^{*}$ and that this correspondence is a
bijection between the sets of all runs in $A$ and $B$. We need two auxiliary
lemmas which concern the right congruence $\mathcal{R}_{t}$.

######  Lemma 6.10 (Short distances).

Let $u,v,w\in\Sigma^{*}$ with $uw,vw\in X$. If $u\mathrel{\mathcal{R}}_{t}v$
then $\|t(uw),t(vw)\|\leq O(|u|+|v|)$.

Two partial functions $t_{1},t_{2}\colon\Sigma^{*}\to\Omega^{*}$ are adjacent
if $\sup\\{\|t_{1}(w),t_{2}(w)\|\mid
w\in\mathrm{dom}(t_{1})\cap\mathrm{dom}(t_{2})\\}<\infty$ where
$\sup\emptyset=-\infty$. We remark that two functions are adjacent in our
definition if and only if their reversals are adjacent according to the
original definition [27]. Notice that $u\mathrel{\mathcal{R}_{t}}v$ if and
only if $u\sim_{X}v$ and the functions $w\mapsto t(uw)$ and $w\mapsto t(vw)$
are adjacent.

######  Lemma 6.11 (Short witnesses).

Let $t_{1},t_{2}\colon\Sigma^{*}\to\Omega^{*}$ be rational functions which are
not adjacent. Then there are words $x,y,z\in\Sigma^{*}$ such that
$xy^{*}z\subseteq\mathrm{dom}(t_{1})\cap\mathrm{dom}(t_{2})$ and
$\|t_{1}(xy^{k}z),t_{2}(xy^{k}z)\|=\Omega(k)$. In particular, for each
$k\in\mathbb{N}$ there exists a word
$x\in\mathrm{dom}(t_{1})\cap\mathrm{dom}(t_{2})$ of length $|x|\leq O(k)$ such
that $\|t_{1}(x),t_{2}(x)\|\geq k$.

######  Proposition 6.12.

If $\mathcal{R}_{t}$ has a critical tuple then $X$ contains a linear fooling
set.

######  Proof 6.13.

Let $(u_{2},v_{2},u,v)$ be a critical tuple in $\mathcal{R}_{t}$ with
$u=u_{1}u_{2}$ and $v=v_{1}v_{2}$. By Proposition 6.1 we can assume that
$u_{2}u\mathrel{\mathcal{R}_{t}}u_{2}wu$ and
$v_{2}u\mathrel{\mathcal{R}_{t}}v_{2}wu$ for all $w\in\\{u,v\\}^{*}$. By
assumption we know that $(u_{2}u,v_{2}u)\notin\mathcal{R}_{t}$. Furthermore,
we claim that $u_{2}u\sim_{X}v_{2}u$: Let $z\in\Sigma^{*}$ and assume that
$u_{2}uz\in X$. Then $u_{2}v_{1}v_{2}uz\in X$ because
$u_{2}u\sim_{X}u_{2}v_{1}v_{2}u$, and thus $v_{2}uz\in X$ because $X$ is
suffix-closed. The other direction follows by a symmetric argument.

Let $n\in\mathbb{N}$ and define

$N=\max_{x\in\\{u_{2},v_{2}\\}}\max_{w\in\\{u,v\\}^{\leq
n}}\sup\\{\|t(xuz),t(xwuz)\|\mid xuz,xwuz\in X\\}<\infty.$

By Lemma 6.10 we have $N\leq O(n)$. Since
$(u_{2}u,v_{2}u)\notin\mathcal{R}_{t}$ and $u_{2}u\sim_{X}v_{2}u$, the
functions $z\mapsto t(u_{2}uz)$ and $z\mapsto t(v_{2}uz)$ are not adjacent. By
Lemma 6.11 there exists a word $z_{n}\in(u_{2}u)^{-1}X$ with
$\|t(u_{2}uz_{n}),t(v_{2}uz_{n})\|\geq 2N+1$ and $|z_{n}|\leq O(N)\leq O(n)$.
We claim that $t(u_{2}wuz_{n})\neq t(v_{2}wuz_{n})$ for all
$w\in\\{u,v\\}^{\leq n}$: By the triangle inequality we have

$\displaystyle 2N+1$ $\displaystyle\leq\|t(u_{2}uz_{n}),t(v_{2}uz_{n})\|$
$\displaystyle\leq\|t(u_{2}uz_{n}),t(u_{2}wuz_{n})\|+\|t(u_{2}wuz_{n}),t(v_{2}wuz_{n})\|+\|t(v_{2}wuz_{n}),t(v_{2}uz_{n})\|$
$\displaystyle\leq 2N+\|t(u_{2}wuz_{n}),t(v_{2}wuz_{n})\|$

which implies $\|t(u_{2}wuz_{n}),t(v_{2}wuz_{n})\|\geq 1$ and in particular
$t(u_{2}wuz_{n})\neq t(v_{2}wuz_{n})$. We have proved that for each
$n\in\mathbb{N}$ there exists a word $z_{n}$ of length $O(n)$ such that
$t(u_{2}wuz_{n})\neq t(v_{2}wuz_{n})$ for all $w\in\\{u,v\\}^{\leq n}$. If $Z$
is the set of all constructed $z_{n}$ for $n\in\mathbb{N}$ then
$\\{u_{2},v_{2}\\}\\{u,v\\}^{*}uZ\subseteq X$ and $(u_{2},v_{2},u,v,uZ)$ is a
linear fooling scheme.

### Well-behaved transducers.

Let $(Q,\preceq)$ be the quasi-order defined by $q\preceq p$ iff there exists
a run from $p$ to $q$ in $A$ or equivalently in $B$. Its equivalence classes
are the strongly connected components (SCCs) of $A$ and $B$. A word
$w\in\Sigma^{*}$ is guarded by a state $p\in Q$ if there exists a run
$q^{\prime}\xleftarrow{w}p$ in $A$ such that $p\preceq q^{\prime}$, i.e. $p$
and $q^{\prime}$ belong to the same SCC. Notice that the set of all words
which are guarded by a fixed state $p$ is suffix-closed. A run
$q\xleftarrow{w}p$ in $A$ is guarded if $w$ is guarded by $p$. We say that $A$
is well-behaved if for all $p\in Q$ and all guarded accepting runs
$\pi,\pi^{\prime}$ from $p$ with $|\pi|=|\pi^{\prime}|$ we have
$\mathsf{out}_{F}(\pi)=\mathsf{out}_{F}(\pi^{\prime})$.

######  Proposition 6.14.

If $A$ is not well-behaved then $X$ contains a linear fooling set.

######  Proof 6.15.

Assume there exist states $p,q,r,q^{\prime},r^{\prime}\in Q$, and accepting
runs $q\xleftarrow{u_{2}}p$ and $r\xleftarrow{v_{2}}p$ with $|u_{2}|=|v_{2}|$
and
$\mathsf{out}_{F}(q\xleftarrow{u_{2}}p)\neq\mathsf{out}_{F}(r\xleftarrow{v_{2}}p)$.
Furthermore let $p\xleftarrow{u_{1}}q^{\prime}\xleftarrow{u_{2}}p$,
$p\xleftarrow{v_{1}}r^{\prime}\xleftarrow{v_{2}}p$ and
$p\xleftarrow{s}q_{\mathit{in}}$ be runs. Let $u=u_{1}u_{2}$ and
$v=v_{1}v_{2}$ and consider any word $w\in\\{u,v\\}^{*}$. Since
$t(u_{2}ws)=\mathsf{out}_{F}(q\xleftarrow{u_{2}}p)\,\mathsf{out}(p\xleftarrow{ws}q_{\mathit{in}})$
and
$t(v_{2}ws)=\mathsf{out}_{F}(r\xleftarrow{v_{2}}p)\,\mathsf{out}(p\xleftarrow{ws}q_{\mathit{in}})$,
we have $t(u_{2}ws)\neq t(v_{2}ws)$. This shows that
$(u_{2},v_{2},u,v,\\{s\\})$ is a linear fooling scheme.

If $\pi$ is a non-empty run $p\xleftarrow{a_{1}\cdots a_{n}}q$ in $A$ and
$p\xleftarrow{(a_{1},\rho_{1})\cdots(a_{n},\rho_{n})}q$ is the corresponding
run in $B$ then we call $\rho_{1}$ the key of $\pi$. The following lemma
justifies the name, stating that $\pi$ is determined by the state $q$, the
word $a_{1}\cdots a_{n}$ and the key $\rho_{1}$.

######  Lemma 6.16.

If $p\xleftarrow{w}q$ and $p^{\prime}\xleftarrow{w}q$ are non-empty runs in
$A$ with the same key then the runs must be identical.

######  Proof 6.17.

Assume that $w=a_{1}\cdots a_{n}$ and let
$p\xleftarrow{(a_{1},\rho_{1})\cdots(a_{n},\rho_{n})}q$ and
$p^{\prime}\xleftarrow{(a_{1},\rho^{\prime}_{1})\cdots(a_{n},\rho^{\prime}_{n})}q$
be the corresponding runs in $B$ with $\rho_{1}=\rho_{1}^{\prime}$. We proceed
by induction on $n$. If $n=1$ then this statement is trivial because $B$ is
deterministic. Now assume $n\geq 2$ and let
$p\xleftarrow{a_{1}}r\xleftarrow{a_{2}\cdots a_{n}}q$ and
$p^{\prime}\xleftarrow{a_{1}}r^{\prime}\xleftarrow{a_{2}\cdots a_{n}}q$. Since
$B$ is trim there exist an accepting run on $e_{\mathcal{R}_{t}}(u)$ from $p$
and an accepting run on $e_{\mathcal{R}_{t}}(u^{\prime})$ from $p^{\prime}$
for some words $u,u^{\prime}\in\Sigma^{*}$. By definition of
$t[\mathcal{R}_{t}]$ we have
$[u]_{\mathcal{R}_{t}}=\rho_{1}=\rho^{\prime}_{1}=[u^{\prime}]_{\mathcal{R}_{t}}$
and therefore
$\rho_{2}=[ua_{1}]_{\mathcal{R}_{t}}=[u^{\prime}a_{1}]_{\mathcal{R}_{t}}=\rho_{2}^{\prime}$.
By induction hypothesis we know that the runs $r\xleftarrow{a_{2}\cdots
a_{n}}q$ and $r^{\prime}\xleftarrow{a_{2}\cdots a_{n}}q$ are identical. Since
$p\xleftarrow{(a_{1},\rho_{1})}r$ and
$p^{\prime}\xleftarrow{(a_{1},\rho_{1}^{\prime})}r^{\prime}$ and $B$ is
deterministic we must have $p=p^{\prime}$.

Let $\pi$ be any run on a word $y\in\Sigma^{*}$. If $\pi$ is not guarded, we
can factorize $\pi=\pi^{\prime}\pi^{\prime\prime}$ such that
$\pi^{\prime\prime}$ is the shortest suffix of $\pi$ which is unguarded, and
then iterate this process on $\pi^{\prime}$. This yields unique factorizations
$\pi=\pi_{0}\pi_{1}\cdots\pi_{m}$ and $y=y_{0}y_{1}\cdots y_{m}$ where
$\pi_{i}$ is a run on $y_{i}$ from a state $q_{i}$ to a state $q_{i-1}$ such
that $y_{i}$ is the shortest suffix of $y_{0}\cdots y_{i}$ which is not
guarded by $q_{i}$ for all $1\leq i\leq m$ and $\pi_{0}$ is guarded. The
factorization $\pi=\pi_{0}\pi_{1}\cdots\pi_{m}$ is the guarded factorization
of $\pi$.

######  Proposition 6.18.

Assume that $t(X)$ is bounded, $A$ is well-behaved and $\mathcal{R}_{t}$ has
no critical tuple. Then the
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern 3.0mu$}}$ -growth
of $X$ is polynomially bounded.

######  Proof 6.19.

We will describe an encoding of $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
t\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}(w)$ for $w\in X$ using $O(\log|w|)$ bits. For
each word $w\in\Sigma^{*}$ and each state $q\in Q$ we define a tree $T_{q,w}$
recursively, which carries information at the nodes and edges. If $w$ is
guarded by $q$ then $T_{q,w}$ consists of a single node labelled by the pair
$(q,|w|)$. Otherwise let $w=uv$ such that $v$ is the shortest suffix of $w$
which is not guarded by $q$. Then $T_{q,w}$ has a root which is labelled by
the tuple $(q,|w|,|v|,\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{\mathcal{R}_{t}}(u))$. For each run
$p\xleftarrow{v}q$ we attach $T_{p,u}$ to the root as a direct subtree. The
edge is labelled by the pair $(\rho,\mathsf{out}(p\xleftarrow{v}q))$ where
$\rho$ is the key of $p\xleftarrow{v}q$. By Lemma 6.16 distinct outgoing edges
from the root are labelled by distinct keys.

The tree $T_{q,w}$ can be encoded using $O(\log|w|)$ bits: Since we have
$p\prec q$ for every unguarded run $p\xleftarrow{v}q$ the tree $T_{q,w}$ has
height at most $|Q|$ and size at most $|Q|^{|Q|}$. All occurring numbers have
at most magnitude $|w|$, and the states and keys can be encoded by $O(1)$
bits. The output words $\mathsf{out}(p\xleftarrow{v}q)$ are factors of words
from the bounded language $t(X)$ and have length at most
$\mathsf{iml}(A)\cdot|v|$. Thus they can be encoded using $O(\log|w|)$ bits.
The node label $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{\mathcal{R}_{t}}(u)$ can be encoded using
$O(\log|w|)$ bits by Theorem 6.7 since $\mathcal{R}_{t}$ has no critical
tuple.

Let $w=xy\in\Sigma^{*}$, $q\in Q$ and let $\pi$ be an accepting run on $y$
from $q$. We show that $T_{q,w}$ and $|y|$ determine $\mathsf{out}_{F}(\pi)$
by induction on the length of the guarded factorization
$\pi=\pi_{0}\pi_{1}\cdots\pi_{m}$. Since $T_{q_{\mathit{in}},w}$ determines
the length $|w|$, the tuple $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
t\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}(w)$ is determined by $T_{q_{\mathit{in}},w}$
for all $w\in X$. If $m=0$ then $y$ is guarded by $q$. Since $A$ is well-
behaved $\mathsf{out}_{F}(\pi)$ is determined by $q$ (which is part of the
label of the root of $T_{q,w}$) and $|y|$ only. Now assume $m\geq 1$ and
suppose that $\pi_{i}$ is a run $q_{i-1}\xleftarrow{y_{i}}q_{i}$ for all
$1\leq i\leq m$ with $q_{m}=q$. Then $y_{m}$ is the shortest suffix of $w$
which is not guarded by $q$. The root of $T_{q,w}$ is labelled by
$(q,|y_{m}|,\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{\mathcal{R}_{t}}(xy_{0}\cdots y_{m-1}))$. Since
$|y_{m}|$ and $|y|$ are known, we can also determine $|y_{0}\cdots y_{m-1}|$.
From $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\nu\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\nu\mkern
2.0mu$}}$}\mkern-2.0mu}_{\mathcal{R}_{t}}(xy_{0}\cdots y_{m-1})$ and
$|y_{0}\cdots y_{m-1}|$ we can then determine $[y_{0}\cdots
y_{m-1}]_{\mathcal{R}_{t}}$, which is the key of $\pi_{m}$. By Lemma 6.16 we
can find the unique edge which is labelled by $([y_{0}\cdots
y_{m-1}]_{\mathcal{R}_{t}},\mathsf{out}(\pi_{m}))$. It leads to the direct
subtree $T_{q_{m-1},xy_{0}\cdots y_{m-1}}$ of $T_{q,w}$. By induction
hypothesis $T_{q_{m-1},xy_{0}\cdots y_{m-1}}$ and $|y_{0}\cdots y_{m-1}|$
determine $\mathsf{out}_{F}(\pi_{0}\cdots\pi_{m-1})$. Finally, we can
determine
$\mathsf{out}_{F}(\pi_{0}\cdots\pi_{m})=\mathsf{out}_{F}(\pi_{0}\cdots\pi_{m-1})\,\mathsf{out}(\pi_{m})$,
concluding the proof.

Now we can prove Theorem 4.7: If $X$ contains no linear fooling set for $t$
then $A$ must be well-behaved by Proposition 6.14 and $\mathcal{R}_{t}$ has no
critical tuple by Proposition 6.12. If additionally $t(X)$ is bounded then the
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern 3.0mu$}}$ -growth
of $X$ is polynomially bounded by Proposition 6.18. Otherwise, if either $X$
contains a linear fooling set or $t(X)$ is not bounded then the
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern 3.0mu$}}$ -growth
of $X$ is exponential by Proposition 4.5 and by Proposition 4.3.

## References

  * [1] Rajeev Alur and P. Madhusudan.  Visibly pushdown languages.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 202–211, 2004.  URL: http://doi.acm.org/10.1145/1007352.1007390, doi:10.1145/1007352.1007390.
  * [2] Arvind Arasu and Gurmeet Singh Manku.  Approximate counts and quantiles over sliding windows.  In Proceedings of PODS 2004, pages 286–296. ACM, 2004.
  * [3] Brian Babcock, Mayur Datar, Rajeev Motwani, and Liadan O’Callaghan.  Maintaining variance and k-medians over data stream windows.  In Proceedings of PODS 2003, pages 234–243. ACM, 2003.
  * [4] Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, and Girish Varma.  Streaming algorithms for language recognition problems.  Theor. Comput. Sci., 494:13–23, 2013.  URL: https://doi.org/10.1016/j.tcs.2012.12.028, doi:10.1016/j.tcs.2012.12.028.
  * [5] Vince Bárány, Christof Löding, and Olivier Serre.  Regularity problems for visibly pushdown languages.  In STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, pages 420–431, 2006.  URL: https://doi.org/10.1007/11672142_34.
  * [6] Jean Berstel.  Transductions and context-free languages, volume 38 of Teubner Studienbücher: Informatik.  Teubner, 1979.
  * [7] Ahmed Bouajjani, Javier Esparza, and Oded Maler.  Reachability analysis of pushdown automata: Application to model-checking.  In CONCUR ’97: Concurrency Theory, 8th International Conference, Warsaw, Poland, July 1-4, 1997, Proceedings, pages 135–150, 1997\.  URL: https://doi.org/10.1007/3-540-63141-0_10, doi:10.1007/3-540-63141-0\\_10.
  * [8] Vladimir Braverman and Rafail Ostrovsky.  Smooth histograms for sliding windows.  In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science FOCS 2007, pages 283–293. IEEE Computer Society, 2007.
  * [9] Vladimir Braverman, Rafail Ostrovsky, and Carlo Zaniolo.  Optimal sampling from sliding windows.  J. Comput. Syst. Sci., 78(1):260–272, 2012.
  * [10] Dany Breslauer and Zvi Galil.  Real-time streaming string-matching.  ACM Trans. Algorithms, 10(4):22:1–22:12, 2014.
  * [11] J Richard Büchi.  Regular canonical systems.  Archiv für mathematische Logik und Grundlagenforschung, 6(3-4):91–111, 1964.
  * [12] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana A. Starikovskaya.  Dictionary matching in a stream.  In Proceedings of ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 361–372. Springer, 2015.
  * [13] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana A. Starikovskaya.  The _k_ -mismatch problem revisited.  In Proceedings of SODA 2016, pages 2039–2052. SIAM, 2016.
  * [14] Raphaël Clifford and Tatiana A. Starikovskaya.  Approximate hamming distance in a stream.  In Proceedings of ICALP 2016, volume 55 of LIPIcs, pages 20:1–20:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016\.
  * [15] Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani.  Maintaining stream statistics over sliding windows.  SIAM J. Comput., 31(6):1794–1813, 2002.
  * [16] Emmanuel Filiot and Pierre-Alain Reynier.  Transducers, logic and algebra for functions of finite words.  SIGLOG News, 3(3):4–19, 2016.  URL: http://doi.acm.org/10.1145/2984450.2984453, doi:10.1145/2984450.2984453.
  * [17] Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre.  Streaming property testing of visibly pushdown languages.  In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 43:1–43:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.  URL: https://doi.org/10.4230/LIPIcs.ESA.2016.43, doi:10.4230/LIPIcs.ESA.2016.43.
  * [18] Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey, and Konstantinos Mamouras.  Automata theory on sliding windows.  In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, volume 96 of LIPIcs, pages 31:1–31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [19] Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey, and Konstantinos Mamouras.  Automata theory on sliding windows.  Technical report, arXiv.org, 2018.  https://arxiv.org/abs/1702.04376.
  * [20] Moses Ganardi, Danny Hucke, and Markus Lohrey.  Querying regular languages over sliding windows.  In Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, volume 65 of LIPIcs, pages 18:1–18:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [21] Moses Ganardi, Artur Jez, and Markus Lohrey.  Sliding windows over context-free languages.  In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, pages 15:1–15:15, 2018.  URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.15, doi:10.4230/LIPIcs.MFCS.2018.15.
  * [22] Seymour Ginsburg.  The Mathematical Theory of Context-Free Languages.  McGraw-Hill, Inc., New York, NY, USA, 1966.
  * [23] Seymour Ginsburg and Edwin H Spanier.  Bounded algol-like languages.  Transactions of the American Mathematical Society, 113(2):333–368, 1964.
  * [24] Bakhadyr Khoussainov and Anil Nerode.  Automatic presentations of structures.  In Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, International Workshop LCC ’94, Indianapolis, Indiana, USA, 13-16 October 1994, pages 367–392, 1994.  URL: https://doi.org/10.1007/3-540-60178-3_93, doi:10.1007/3-540-60178-3\\_93.
  * [25] Frédéric Magniez, Claire Mathieu, and Ashwin Nayak.  Recognizing well-parenthesized expressions in the streaming model.  SIAM J. Comput., 43(6):1880–1905, 2014.  URL: https://doi.org/10.1137/130926122, doi:10.1137/130926122.
  * [26] Rohit Parikh.  On context-free languages.  J. ACM, 13(4):570–581, 1966.  URL: http://doi.acm.org/10.1145/321356.321364, doi:10.1145/321356.321364.
  * [27] Christophe Reutenauer and Marcel Paul Schützenberger.  Minimization of rational word functions.  SIAM J. Comput., 20(4):669–685, 1991.  URL: https://doi.org/10.1137/0220042, doi:10.1137/0220042.
  * [28] Andreas Weber and Reinhard Klemm.  Economy of description for single-valued transducers.  Inf. Comput., 118(2):327–340, 1995.  URL: https://doi.org/10.1006/inco.1995.1071, doi:10.1006/inco.1995.1071.

##  Appendix A Proof of Proposition 4.3

Since $\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
t\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}(x)$ determines $t(x)$ we have
$|\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
t\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}(X\cap\Sigma^{\leq n})|\geq|t(X\cap\Sigma^{\leq
n})|$ for all $n\in\mathbb{N}$. It suffices to show that every non-empty
preimage $t^{-1}(\\{y\\})$ contains at least one word of length $O(|y|)$ in
$X$, i.e. there exists a number $c>0$ such that $t(X)\cap\Omega^{\leq
n}\subseteq t(X\cap\Sigma^{\leq cn})$ for sufficiently large $n\in\mathbb{N}$.
Then, if by assumption $|t(X)\cap\Omega^{\leq n}|$ grows exponentially, then
so does $|t(X\cap\Sigma^{\leq n})|$ and also $|\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle
t\mkern 3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle t\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle
t\mkern 2.0mu$}}$}\mkern-2.0mu}(X\cap\Sigma^{\leq n})|$.

Let us now prove the claim, for which we need to define context-free grammars
over arbitrary monoids. A context-free grammar over a monoid $M$ has the form
$G=(N,S,\to_{G})$ where $N$ is a finite set of nonterminals (which is disjoint
from $M$), $S$ is the starting nonterminal, and $\to_{G}\,\subseteq
N\times(M*N^{*})$ is a finite set of productions where $M*N^{*}$ is the free
product of the monoids $M$ and $N^{*}$. A derivation tree for $m\in M$ is a
node-labelled rooted ordered tree with the following properties:

  * •

Inner nodes are labelled by nonterminals $A\in N$.

  * •

Leaves are labelled by monoid elements $m\in M$.

  * •

If a node $s$ has children $s_{1},\dots,s_{k}$ where $v$ is labelled by $A$
and $s_{1},\dots,s_{k}$ are labelled by $\alpha_{1},\dots,\alpha_{k}$ then
there exists a production $A\to_{G}\alpha_{1}\cdots\alpha_{k}$.

  * •

If $m_{1},\dots,m_{\ell}$ are the labels of the leaves read from left to right
then $m=m_{1}\cdots m_{\ell}$.

The language $\mathsf{L}(A)$ generated by a nonterminal $A\in N$ is the set of
all elements $m\in M$ such that there exists a derivation tree for $m$ whose
root is labelled by $A$. The language $\mathsf{L}(G)$ generated by $G$ is the
language $\mathsf{L}(S)$.

We first construct from a context-free grammar $G=(N,S,\to_{G})$ for
$X\subseteq\Sigma^{*}$ a context-free grammar
$H=(N^{\prime},S^{\prime},\to_{H})$ for $t|_{X}=\\{(x,t(x))\mid x\in X\\}$
over the product monoid $\Sigma^{*}\times\Omega^{*}$. We can assume that
$\varepsilon\notin X$ and that $G$ is in Chomsky normal form, i.e. each rule
has the form $A\to a$ where $A\in N$ and $a\in\Sigma$, or $A\to BC$ where
$A,B,C\in N$. Let $R=(Q,\Sigma,\Omega,I,\Delta,F,o)$ be a real-time transducer
for $t$. We define $N^{\prime}=\\{S^{\prime}\\}\cup\\{A_{p,q}\mid A\in
N,\,p,q\in Q\\}$ and $\to_{H}$ contains the productions

  * •

$A_{p,q}\to_{H}(a,y)$ for all productions $A\to_{G}a$ and transitions
$p\xrightarrow{a\mid y}q$ in $R$,

  * •

$A_{p,q}\to_{H}B_{p,r}C_{r,q}$ for all productions $A\to_{G}BC$ and $p,q,r\in
Q$,

  * •

$S^{\prime}\to_{H}S_{p,q}\,(\varepsilon,o(q))$ for all $(p,q)\in I\times F$.

One can verify that for all $A\in N$ and $p,q\in Q$ the language
$\mathsf{L}(A_{p,q})$ is the set of all pairs
$(x,y)\in\mathsf{L}(A)\times\Omega^{*}$ such that $p\xrightarrow{x\mid y}q$ in
$R$, and that $\mathsf{L}(H)=t|_{X}$.

Now let $A\in N$, $p,q\in Q$ and $(x,y)\in\mathsf{L}(A_{p,q})$ with the
property that
$|x|=\min\\{|x^{\prime}|\mid(x^{\prime},y)\in\mathsf{L}(A_{p,q})\\}$. Consider
a derivation tree $T$ for $(x,y)$ whose root is labelled by $A_{p,q}$. If $s$
is a node in $T$ which derives $(u,v)$ then we define the weight of $s$ to be
$|v|$. Clearly, the weight of an inner node is the sum of the weights of its
children.

######  Claim 1.

If $(s_{1},s_{2},\dots,s_{k})$ is a path in $T$ such that all nodes $s_{i}$ on
the path have the same length then $k\leq|N^{\prime}|$.

######  Proof A.1.

Assume that $k>|N^{\prime}|$. There exist two nodes $s_{i}\neq s_{j}$ with
$i<j$ which are labelled by the same nonterminal from $N^{\prime}$. The
subtrees rooted in $s_{i}$ and $s_{j}$ are derivation trees for pairs $(u,v)$
and $(u^{\prime},v)$ for some $u,u^{\prime}\in\Sigma^{*}$ and $v\in\Omega^{*}$
where $u^{\prime}$ is a proper factor of $u$. We can then replace the subtree
rooted in $s_{i}$ by the subtree rooted in $s_{j}$ and obtain a derivation
tree for a pair $(x^{\prime},y)$ with $|x^{\prime}|<|x|$, contradiction.

Set $c=|N^{\prime}|$. By the claim above every subtree whose root has weight 0
has depth at most $c$ and hence its size is at most $C=2^{c}-1$. Define
$D=c+(c-1)C$.

######  Claim 2.

The derivation tree $T$ has $O(|y|)$ nodes.

######  Proof A.2.

We prove by induction on $|y|$ that, if $|y|\geq 1$ then $T$ has at most
$(2|y|-1)D$ nodes. The root of $T$ has weight $|y|$. Let $(s_{1},\dots,s_{k})$
be the maximal path starting in the root whose nodes have weight $|y|$. We
know that $k\leq c$. If $s_{i}^{\prime}$ is the sibling of $s_{i-1}$ for
$2\leq i\leq k$, then $s_{i}^{\prime}$ has weight $0$ and the subtree rooted
in $s_{i}^{\prime}$ has at most $C$ nodes.

  1. 1.

Assume that $s_{k}$ is a leaf. Then $T$ consists of at most
$D=c+(c-1)C\leq(2|y|-1)D$ nodes, namely $k\leq c$ nodes on the path
$(s_{1},\dots,s_{k})$ and $c-1$ many subtrees with at most $C$ nodes.

  2. 2.

Assume that $s_{k}$ has two children $s_{k+1}$ and $s^{\prime}_{k+1}$ and let
$w$ and $w^{\prime}$ be the weights of $s_{k+1}$ and $s^{\prime}_{k+1}$,
respectively. We have $|y|=w+w^{\prime}$ and $1\leq w,w^{\prime}<|y|$. By
induction hypothesis the subtrees rooted in $s_{k+1}$ and $s^{\prime}_{k+1}$
have at most $(2w-1)D$ and $(2w^{\prime}-1)D$ nodes, respectively. Therefore
$T$ has in total at most $D+(2w-1)D+(2w^{\prime}-1)D\leq(2|y|-1)D$ nodes.

This concludes the proof of the claim.

Now let $y\in t(X)\cap\Omega^{\leq n}$ and $x\in X$ be any word with $t(x)=y$.
There exists an initial accepting run $p\xrightarrow{x\mid y^{\prime}}q$ with
$y=y^{\prime}\,o(q)$. As shown above there exists a word $x^{\prime}$ with
$p\xrightarrow{x^{\prime}\mid y^{\prime}}q$ and $x^{\prime}\leq
O(|y^{\prime}|)\leq O(n)$, which concludes the proof.

##  Appendix B Proof of Lemma 5.1

In [5] it was observed that $\sim$ can be recognized by a synchronous 2-tape
automaton. The convolution of two words $u=a_{1}\cdots a_{m},v=b_{1}\cdots
b_{n}\in\Omega^{*}$ is the word $u\otimes v=c_{1}\cdots c_{\ell}$ of length
$\ell=\max(m,n)$ over the alphabet $(\Omega\cup\\{\Box\\})^{2}$ where
$c_{i}=(a_{i},b_{i})$ if $1\leq i\leq\min(m,n)$, $c_{i}=(a_{i},\square)$ if
$m<i\leq n$ and $c_{i}=(\square,b_{i})$ if $n<i\leq m$. Similarly, one can
define an associative operation $\otimes$ on $k$-tuples of words. A $k$-ary
relation $R\subseteq(\Omega^{*})^{k}$ is synchronous rational if $\otimes
R=\\{\otimes(u_{1},\dots,u_{k})\mid(u_{1},\dots,u_{k})\in R\\}$ is a regular
language over $(\Omega\cup\\{\Box\\})^{k}$. The set of synchronous rational
relations is known to be closed under first-order operations and, in
particular, under Boolean operations, cf. [24]. Clearly, every binary
synchronous rational relation is a rational transduction.

######  Lemma B.1 ([5]).

The equivalence relation $\sim^{\mathsf{R}}$ is synchronous rational.

######  Proof B.2.

We present a right automaton which recognizes the complement of
$\sim^{\mathsf{R}}$. It reads two configurations $\alpha p$ and $\beta q$
synchronously which are aligned to the right, from right to left. The
automaton stores a pair of states of $A$, starting with the pair $(p,q)$. It
then guesses a word $w$ by its monotonic factorization which witnesses that
$w$ belongs to exactly one of the languages $\mathsf{L}(\alpha p)$ and
$\mathsf{L}(\beta q)$. Notice that it suffices to read the maximal descending
prefix of $w$ and test whether the reached state pair
$(p^{\prime},q^{\prime})$ belongs to some fixed set of state pairs since the
remaining ascending suffix cannot access the stack contents of the reached
configurations. To simulate $A$ on a descending prefix in each step the
automaton either guesses a return symbol and removes the top most stack symbol
of both configurations (or leaves $\bot$ at the top), or guesses a state
transformation $\tau\in\varphi(W)$ which only modifies the current state pair.

It is well-known that $\leq_{\mathit{llex}}$ is a synchronous rational
relation. By the closure properties of synchronous rational relations the
function $\mathsf{rep}$ is rational.

##  Appendix C Proof of Proposition 5.4

Let $w=w_{0}w_{1}\cdots w_{m}\in\Sigma^{*}$ be a monotonic factorization and
let $s=s_{0}s_{1}\cdots s_{m}\in\mathrm{Flat}$ be the associated flattening.
We prove $t_{f}(s)\sim\delta(\bot q_{0},w)$ by induction on $m$.

  * •

If $m=0$ and $s_{0}=\varepsilon$ then $t_{f}(s)=\bot q_{0}=\delta(\bot
q_{0},\varepsilon)$.

  * •

If $m=0$ and $s_{0}=q_{1}\cdots q_{k}\in Q^{+}$ then $t_{f}(s)=\bot q_{1}$ and
$\nu_{A}(w)=\mathsf{rep}(\delta(\bot q_{0},w))=\bot q_{1}$.

  * •

If $m\geq 1$ and $s_{m}\in\Sigma_{c}$ then $s_{m}=w_{m}$. By induction
hypothesis we know that $t_{f}(s_{0}\cdots s_{m-1})\sim\delta(\bot
q_{0},w_{0}\cdots w_{m-1})$. Since $\delta(\bot q_{0},w)=\delta(\delta(\bot
q_{0},w_{0}\cdots w_{m-1}),w_{m})$ and $t_{f}(s)=\delta(t_{f}(s_{0}\cdots
s_{m-1}),s_{m})$ we obtain $\delta(\bot q_{0},w)\sim t_{f}(s)$.

  * •

If $m\geq 1$ and $s_{m}=\tau q_{2}\cdots q_{k}\in Q^{Q}Q^{*}$ then $w_{m}$ is
well-matched and $\varphi(w_{m})=\tau$. Assume that $t_{f}(s_{0}\cdots
s_{m-1})=\alpha p$ and $\delta(\bot q_{0},w_{0}\cdots w_{m-1})=\beta q$. By
induction hypothesis we know that $\alpha p\sim\beta q$. Since
$t_{f}(s)=\alpha\tau(p)=\delta(\alpha p,w_{m})$ and $\delta(\bot
q_{0},w)=\delta(\beta q,w_{m})$ we obtain $t_{f}(s)\sim\delta(\bot q_{0},w)$.

Since $\nu_{f}=\mathsf{rep}\circ t_{f}$ and
$\nu_{A}(w)=\mathsf{rep}(\delta(\bot q_{0},w))$ we have
$\nu_{f}(s)=\nu_{A}(w)$.

######  Lemma C.1.

Let $w=w_{0}w_{1}\cdots w_{m}\in\Sigma^{*}$ be a monotonic factorization with
empty initial factor $w_{0}=\varepsilon$ and let $s=s_{0}s_{1}\cdots
s_{m}\in\Sigma_{f}^{*}$ be the associated flattening. If $\delta(\bot
p,w)=\bot\alpha q$ then $p\xrightarrow{s\mid\alpha}q$ in $A_{1}$ and hence
$t_{p}(s)=\alpha q$.

######  Proof C.2.

Proof by induction on $m$. If $m=0$ then $w=s=\varepsilon$, $p=q$ and
$\alpha=\varepsilon$. For the induction step assume $\delta(\bot p,w_{1}\cdots
w_{m-1})=\bot\alpha q$ and $\delta(\bot\alpha
q,w_{m})=\bot\alpha\alpha_{1}q_{1}$. By induction hypothesis the run of
$A_{1}$ on $s$ has the form $p\xrightarrow{s_{1}\cdots
s_{m-1}\mid\alpha}q\xrightarrow{s_{m}\mid\alpha_{2}}q_{2}$. We do a case
distinction.

If $w_{m}\in\Sigma_{c}$ then $\delta(q,w_{m})=(\alpha_{1},q_{1})$. Since
$s_{m}=w_{m}$ and by definition of $A_{1}$ we have $\alpha_{1}=\alpha_{2}$ and
$q_{1}=q_{2}$. Otherwise $w_{m}\in W\setminus\\{\varepsilon\\}$ and
$\alpha_{1}=\varepsilon$. The word $s_{m}=\sigma_{1}(w_{m})$ starts with
$\tau=\varphi(w_{m})$ and we have $\tau(q)=q_{1}$. By definition of $A_{1}$ we
indeed have $q_{2}=\tau(q)$ and $\alpha_{2}=\varepsilon$.

We define the following total function
$t_{f}\colon\Sigma_{f}^{*}\to(Q\cup\Gamma)^{*}$. Let $s\in\Sigma_{f}^{*}$ be
an input word and let $q_{1}\cdots q_{k}\in Q^{*}$ be the maximal prefix of
$s$ from $Q^{*}$, say $s=q_{1}\cdots q_{k}s^{\prime}$ for some
$s^{\prime}\in\Sigma_{f}^{*}$. Then we define

$t_{f}(s)=\begin{cases}t_{q_{0}}(s),&\text{if $k=0$,}\\\
t_{q_{1}}(s^{\prime}),&\text{if $k\geq 1$.}\\\ \end{cases}$

It is easy to see that $t_{f}$ is rational by providing a transducer for
$t_{f}$. It verifies whether $s$ starts with a state $q\in Q$. If so, it
memorizes $q$ and simulates $A_{1}$ on $s^{\prime}$ from $q$, and otherwise
$A_{1}$ is directly simulated on $s$ from $q_{0}$.

Now let $w=w_{0}w_{1}\cdots w_{m}$ be a monotonic factorization and
$s=s_{0}s_{1}\cdots s_{m}\in\Sigma_{f}^{*}$ be the associated flattening. We
claim that $\delta(\bot q_{0},w)\sim\bot t_{f}(s)$. If $w_{0}=\varepsilon$
then $s_{0}=\varepsilon$ and $s$ does not start with a state from $Q$. In this
case we have $\delta(\bot q_{0},w)=\bot t_{q_{0}}(s)=\bot t_{f}(s)$ by Lemma
C.1. If $w_{0}\neq\varepsilon$ then $s_{0}$ starts with some state $q_{1}\in
Q$. By definition of $\sigma_{0}$ we have $\delta(\bot q_{0},w_{0})\sim\bot
q_{1}$ and thus $\delta(\bot q_{0},w)\sim\delta(\bot q_{1},w_{1}\cdots
w_{m})$. By Lemma C.1 we have $\delta(\bot q_{1},w_{1}\cdots w_{m})=\bot
t_{q_{1}}(s_{1}\cdots s_{m})=\bot t_{f}(s)$, which proves the claim. Finally,
we can set $\nu_{f}(s)=\mathsf{rep}(\bot t_{f}(s))$ for all
$s\in\Sigma_{f}^{*}$.

##  Appendix D Proof of Proposition 5.11

By Proposition 5.4 we know $\nu_{f}(\mathrm{Flat})=\mathrm{Rep}$. Clearly
$\nu_{f}(\mathrm{Flat})\subseteq\nu_{f}(\mathrm{RegFlat})$ and it remains to
show the other inclusion. Consider a word $r\in\mathrm{RegFlat}$ which does
not have a non-empty prefix from $R_{0}$, say $r=u_{1}v_{1}u_{2}v_{2}\cdots
v_{m}u_{m+1}$ where $u_{1},\dots,u_{m+1}\in\Sigma_{c}^{*}$ and
$v_{1},\dots,v_{m}\in R_{1}$. Then
$r^{\prime}=u_{1}\,\mathsf{apx}_{\ell}(v_{1})\,u_{2}\,\mathsf{apx}_{\ell}(v_{2})\cdots\mathsf{apx}_{\ell}(v_{m})\,u_{m+1}$
belongs to $\mathrm{Flat}$ and $\nu_{f}(r)=\nu_{f}(r^{\prime})$.

Now assume that $r$ has a non-empty prefix $q_{1}\cdots q_{k}\in R_{0}$. We do
the replacements above and the following. By definition $q_{1}\cdots q_{k}$ is
a proper suffix of some word $x=\tau p_{2}\cdots p_{i-1}q_{1}\cdots q_{k}\in
R_{1}$. Let $y=\mathsf{apx}_{i}(x)\in S_{1}$ which has a proper suffix of the
form $q_{1}q_{2}^{\prime}\cdots q_{k}^{\prime}$ belonging to $S_{0}$. We can
replace $q_{1}\cdots q_{k}$ by $q_{1}q_{2}^{\prime}\cdots q_{k}^{\prime}$ in
$r$ and obtain a word $r^{\prime}\in\mathrm{Flat}$ with
$\nu_{f}(r)=\nu_{f}(r^{\prime})$.

##  Appendix E Proof of Proposition 5.12

Assume that $(u_{2},v_{2},u,v,Z)$ is a linear fooling scheme for $\nu_{f}$
with $\\{u_{2},v_{2}\\}\\{u,v\\}^{*}Z\subseteq\mathrm{RegFlat}$. We first
ensure that $\\{u,v\\}\cup Z\subseteq(\Sigma_{c}\cup R_{1})^{*}$. Assume that
$u,v\in Q^{*}$ and hence $\\{u_{2},v_{2}\\}\\{u,v\\}^{*}\subseteq Q^{*}$ is
contained in the set of prefixes of words in $R_{0}$. Since $R_{0}$ is bounded
by assumption also $\\{u_{2},v_{2}\\}\\{u,v\\}^{*}$ must be bounded, which
contradicts the fact that $\\{u_{2},v_{2}\\}\\{u,v\\}^{*}$ has exponential
growth.

Without loss of generality, assume that $u=u_{3}u_{4}$ such that $u_{4}$
either starts with a call letter $a\in\Sigma_{c}$ or a transformation $\tau\in
Q^{Q}$. We claim that $(u_{2}u_{3},v_{2}u_{3},u_{4}uu_{3},u_{4}vu_{3},u_{4}Z)$
is a linear fooling scheme for $\nu_{f}$. It has the following properties:

  * •

$\\{u_{2}u_{3},v_{2}u_{3}\\}\\{u_{4}uu_{3},u_{4}vu_{3}\\}^{*}u_{4}Z\subseteq\mathrm{RegFlat}$,

  * •

$u_{2}u_{3}$ is a suffix of $u_{4}uu_{3}$,

  * •

$v_{2}u_{3}$ is a suffix of $u_{4}vu_{3}$,

  * •

$|u_{2}u_{3}|=|v_{2}u_{3}|$.

Also, we know that for every $n\in\mathbb{N}$ there exists a word $z_{n}\in Z$
with $|z_{n}|\leq O(n)$ and $\nu_{f}(u_{2}wz_{n})\neq\nu_{f}(v_{2}wz_{n})$ for
all $w\in\\{uu,uv\\}^{\leq n}\\{u\\}$ and thus, by factoring out the first
$u_{3}$\- and the last $u_{4}$-factor, we have
$\nu_{f}(u_{2}u_{3}wu_{4}z_{n})\neq\nu_{f}(v_{2}u_{3}wu_{4}z_{n})$ for all
$w\in\\{u_{4}uu_{3},u_{4}vu_{3}\\}^{\leq n}$. Hence we have verified the
conditions of a linear fooling scheme. It has the desired properties that
$\\{u_{4}uu_{3},u_{4}vu_{3}\\}\cup u_{4}Z\subseteq(\Sigma_{c}\cup R_{1})^{*}$
because $u_{4}$ starts with a call letter or a transformation.

Now let $(u_{2},v_{2},u,v,Z)$ be a linear fooling scheme with $\\{u,v\\}\cup
Z\subseteq(\Sigma_{c}\cup R_{1})^{*}$. We replace occurring factors from
$R_{1}$ by factors from $S_{1}$ while maintaining the values
$\nu_{f}(u_{2}wz)$ and $\nu_{f}(v_{2}wz)$ for $w\in\\{u,v\\}^{*}$ and $z\in
Z$.

  1. 1.

First, in each word $z\in Z\subseteq(\Sigma_{c}\cup R_{1})^{*}$ we replace
each $R_{1}$-factor $v$ by $\mathsf{apx}_{\ell}(v)$ which ensures that
$Z\subseteq(\Sigma_{c}\cup S_{1})^{*}$.

  2. 2.

Next consider $u$ and $v$, and assume that $u=u_{1}u_{2}$ and $v=v_{1}v_{2}$
for some $u_{1},v_{1}\in\Sigma_{f}^{*}$. Let us consider $R_{1}$-factors which
cross the factorization $u=u_{1}u_{2}$ or $v=v_{1}v_{2}$, respectively. If
$u_{2}$ starts with some state we can factorize $u_{1}$ and $u_{2}$ as
$u_{1}=u_{3}\tau q_{2}\cdots q_{i-1}$ and $u_{2}=q_{i}\cdots q_{k}u_{4}$ where
$u_{3},u_{4}\in(\Sigma_{c}\cup R_{1})^{*}$ and $\tau q_{2}\cdots q_{k}\in
R_{1}$. Let $\mathsf{apx}_{i}(\tau q_{2}\cdots q_{k})=\tau
s^{\prime}q_{i}p_{i+1}\cdots p_{k}\in S_{1}$. We replace $u_{1}$ by $u_{3}\tau
s^{\prime}$ and $u_{2}$ by $q_{i}p_{i+1}\cdots p_{k}u_{4}$. Notice that the
length of $u_{2}$ has not changed (this maintains $|u_{2}|=|v_{2}|$) and the
first state of $u_{2}$ has not changed either (this maintains the values
$\nu_{f}(u_{2}wz)$). If $v_{2}$ starts with some state we do the analogous
replacements for $v_{1}$ and $v_{2}$.

  3. 3.

Finally, each $R_{1}$-factor $v$ in $u_{1}$, $u_{2}$, $v_{1}$ and $v_{2}$ is
replaced by $\mathsf{apx}_{\ell}(v)$.

One can verify that the obtained tuple $(u_{2},v_{2},u,v,Z)$ is again a linear
fooling scheme for $\nu_{f}$ satisfying
$\\{u_{2},v_{2}\\}\\{u,v\\}^{*}Z\subseteq\mathrm{Flat}$.

##  Appendix F Proof of Lemma 6.10

Suppose that $w=a_{1}\cdots a_{m}$. Since $\mathcal{R}_{t}$ is a right
congruence we know that $ua_{1}\cdots
a_{i}\mathrel{\mathcal{R}}_{t}va_{1}\cdots a_{i}$ for all $0\leq i\leq m$. By
definition of the look-ahead extension the words $e_{\mathcal{R}_{t}}(uw)$ and
$e_{\mathcal{R}_{t}}(vw)$ have the common suffix

$s=\binom{a_{1}}{[u]_{\mathcal{R}_{t}}}\binom{a_{2}}{[ua_{1}]_{\mathcal{R}_{t}}}\cdots\binom{a_{m}}{[ua_{1}\cdots
a_{m-1}]_{\mathcal{R}_{t}}}.$

The initial accepting runs of $B$ on $e_{\mathcal{R}_{t}}(uw)$ and
$e_{\mathcal{R}_{t}}(vw)$ have the form

$q\xleftarrow{e_{\mathcal{R}_{t}}(u)}p\xleftarrow{s}q_{\mathit{in}}\quad\text{and}\quad
r\xleftarrow{e_{\mathcal{R}_{t}}(v)}p\xleftarrow{s}q_{\mathit{in}}$

and thus $t(uw)$ and $t(vw)$ share the suffix
$\mathsf{out}(p\xleftarrow{s}q_{0})$. This implies

$\|t(uw),t(vw)\|\leq|\mathsf{out}_{F}(q\xleftarrow{e_{\mathcal{R}_{t}}(u)}p)|+|\mathsf{out}_{F}(r\xleftarrow{e_{\mathcal{R}_{t}}(v)}p)|\leq\mathsf{iml}(A)\cdot(|u|+|v|+2),$

proving the statement.

##  Appendix G Proof of Lemma 6.11

Assume that $t_{1}$ and $t_{2}$ are not adjacent. By [27, Proof of Proposition
1.] there exist words $x,y,z\in\Sigma^{*}$ and
$u_{1},u_{2},v_{1},v_{2},w_{1},w_{2}\in\Omega^{*}$ such that
$t_{1}(xy^{k}z)=u_{1}v_{1}^{k}w_{1}$, $t_{2}(xy^{k}z)=u_{2}v_{2}^{k}w_{2}$ for
all $k\in\mathbb{N}$, and
$\sup\\{\|u_{1}v_{1}^{k}w_{1},u_{2}v_{2}^{k}w_{2}\|\mid
k\in\mathbb{N}\\}=\infty$. By the triangle inequality we have

$\displaystyle\|v_{1}^{k}w_{1},v_{2}^{k}w_{2}\|$
$\displaystyle\leq\|v_{1}^{k}w_{1},u_{1}v_{1}^{k}w_{1}\|+\|u_{1}v_{1}^{k}w_{1},u_{2}v_{2}^{k}w_{2}\|+\|u_{2}v_{2}^{k}w_{2},v_{2}^{k}w_{2}\|$
$\displaystyle=|u_{1}|+\|u_{1}v_{1}^{k}w_{1},u_{2}v_{2}^{k}w_{2}\|+|u_{2}|=\|t_{1}(xy^{k}z),t_{2}(xy^{k}z)\|+|u_{1}|+|u_{2}|.$

We prove that $\|v_{1}^{k}w_{1},v_{2}^{k}w_{2}\|\geq\Omega(k)$ which implies
that $\|t_{1}(xy^{k}z),t_{2}(xy^{k}z)\|\geq\Omega(k)$. If both
$v_{1}=v_{2}=\varepsilon$ then

$\sup_{k\in\mathbb{N}}\|v_{1}^{k}w_{1},v_{2}^{k}w_{2}\|=\|w_{1},w_{2}\|<\infty,$

which contradicts $\sup\\{\|u_{1}v_{1}^{k}w_{1},u_{2}v_{2}^{k}w_{2}\|\mid
k\in\mathbb{N}\\}=\infty$. If $|v_{1}|\neq|v_{2}|$ then

$\|v_{1}^{k}w_{1},v_{2}^{k}w_{2}\|\geq\big{|}|v_{1}^{k}w_{1}|-|v_{2}^{k}w_{2}|\big{|}=\Omega(k).$

Now assume $|v_{1}|=|v_{2}|\geq 1$. Since

$\|v_{1}^{k}w_{1},v_{2}^{k}w_{2}\|=|v_{1}^{k}w_{1}|+|v_{2}^{k}w_{2}|-2|v_{1}^{k}w_{1}\wedge
v_{2}^{k}w_{2}|\geq\Omega(k)-2|v_{1}^{k}w_{1}\wedge v_{2}^{k}w_{2}|$

it suffices to show that $\sup_{k}|v_{1}^{k}w_{1}\wedge
v_{2}^{k}w_{2}|<\infty$. Towards a contradiction assume that
$\sup_{k}|v_{1}^{k}w_{1}\wedge v_{2}^{k}w_{2}|=\infty$. Then, for every
$k\in\mathbb{N}$ there exists $K\in\mathbb{N}$ such that
$|v_{1}^{K}w_{1}\wedge
v_{2}^{K}w_{2}|\geq\max\\{|v_{1}^{k}w_{1}|,|v_{2}^{k}w_{2}|\\}$. If
$|v_{1}^{k}w_{1}|\geq|v_{2}^{k}w_{2}|$ then $v_{1}^{k}w_{1}$ is a suffix of
$v_{1}^{K}w_{1}\wedge v_{2}^{K}w_{2}$ and otherwise $v_{2}^{k}w_{2}$ is a
suffix of $v_{1}^{K}w_{1}\wedge v_{2}^{K}w_{2}$. This shows that for all
$k\in\mathbb{N}$ either $v_{1}^{k}w_{1}$ is a suffix of $v_{2}^{k}w_{2}$, or
vice versa, and therefore $|v_{1}^{k}w_{1}\wedge
v_{2}^{k}w_{2}|=\min\\{|v_{1}^{k}w_{1}|,|v_{2}^{k}w_{2}|\\}$. Since
$|v_{1}|=|v_{2}|$ we obtain

$\|v_{1}^{k}w_{1},v_{2}^{k}w_{2}\|=|v_{1}^{k}w_{1}|+|v_{2}^{k}w_{2}|-2\min\\{|v_{1}^{k}w_{1}|,|v_{2}^{k}w_{2}|\\}=|w_{1}|+|w_{2}|-2\min\\{|w_{1}|,|w_{2}|\\}$

contradicting $\sup_{k}\|v_{1}^{k}w_{1},v_{2}^{k}w_{2}\|=\infty$.