# Sample Complexity of Automata Cascades

Alessandro Ronca,1 Nadezda A. Knorozova,2 Giuseppe De Giacomo1,3

###### Abstract

Every automaton can be decomposed into a cascade of basic automata. This is
the Prime Decomposition Theorem by Krohn and Rhodes. We show that cascades
allow for describing the sample complexity of automata in terms of their
components. In particular, we show that the sample complexity is linear in the
number of components and the maximum complexity of a single component, modulo
logarithmic factors. This opens to the possibility of learning automata
representing large dynamical systems consisting of many parts interacting with
each other. It is in sharp contrast with the established understanding of the
sample complexity of automata, described in terms of the overall number of
states and input letters, which implies that it is only possible to learn
automata where the number of states is linear in the amount of data available.
Instead our results show that one can learn automata with a number of states
that is exponential in the amount of data available.

##  1 Introduction

Automata are fundamental in computer science. They are one of the simplest
models of computation, with the expressive power of regular languages, placed
at the bottom of the Chomsky hierarchy. They are also a mathematical model of
finite-state dynamical systems. In learning applications, automata allow for
capturing targets that exhibit a time-dependent behaviour; namely, functions
over sequences such as time-series, traces of a system, histories of
interactions between an agent and its environment. Automata are typically
viewed as state diagrams, where states and transitions are the building blocks
of an automaton, cf. (Hopcroft and Ullman 1979). Accordingly, classes of
automata are described in terms of the number of states and input letters.
Learning from such classes requires an amount of data that is linear in the
number of states and letters (Ishigami and Tani 1997). Practically it means
that, in order to learn large dynamical systems made of many components, the
amount of data required is exponential in the number of components, as the
number of states of a system will typically be exponential in the number of
its stateful components.

We propose _automata cascades_ as a structured, modular, way to describe
automata as complex systems made of many _components_ connected in an acylic
way. Our cascades are strongly based on the _theory of Krohn and Rhodes_ ,
which says that every automaton can be decomposed into a cascade of basic
components called _prime automata_ (Krohn and Rhodes 1965). Conversely, the
theory can be seen as prescribing which components to use in order to build
certain classes of automata, and hence obtain a certain expressivity. For
example, we can cascade so-called _flip-flop automata_ in order to build all
counter-free automata, and hence obtain the expressivity of well-known logics
such as monadic first-order logic on finite linearly-ordered domains
(McNaughton and Papert 1971) and the linear temporal logic on finite traces
LTLf (De Giacomo and Vardi 2013).

Figure 1: Diagram of a fully-connected cascade of three components, based on a
figure in (Maler 1990). Boxes denote components. Arrows depict flow of
information: component $A$ reads the external input; component $B$ reads the
external input together with the output of $A$; component $C$ reads the
external input together with the outputs of $A$ and $B$. The overall output is
the output of $C$.

We focus on cascades as a means to learn automata. Our cascades are designed
for a fine control of their sample complexity. We show that—ignoring
logarithmic factors— _the sample complexity of automata cascades is at most
linear in the product of the number of components and the maximum complexity
of a single component_. Notably, the complexity of a single component does not
grow with the number of components in the cascade. We carry out the analysis
both in the setting where classes of automata cascades are finite, and in the
more general setting where they can be infinite. For both cases, we obtain
bounds of the same shape, with one notable difference that for infinite
classes we incur a logarithmic dependency on the maximum length of a string.
Overall, our results show that the sample complexity of automata can be
decoupled from the the number of states and input letters. Rather, it can be
described in terms of the components of a cascade capturing the automaton.
Notably, the number of states of such an automaton can be exponential in the
number of components of the cascade.

We see the opportunity for cascades to unlock a greater potential of automata
in learning applications. On one hand, automata come with many favourable,
well-understood, theoretical properties, and they admit elegant algorithmic
solutions. On the other hand, the existing automata learning algorithms have a
complexity that depends directly on the number of states. This hurts
applications where the number of states grows very fast, such as non-Markov
reinforcement learning (Toro Icarte et al. 2018; De Giacomo et al. 2019; Gaon
and Brafman 2020; Brafman and De Giacomo 2019; Abadi and Brafman 2020; Xu et
al. 2020; Neider et al. 2021; Jothimurugan et al. 2021; Ronca and De Giacomo
2021; Ronca, Paludo Licks, and De Giacomo 2022). Given our favourable sample
complexity results, automata cascades have a great potential to extend the
applicability of automata learning in large complex settings.

Before concluding the section, we introduce our running example, that is
representative of a class of tasks commonly considered in reinforcement
learning. It is based on an example from (Andreas, Klein, and Levine 2017).

######  Example 1.

Consider a Minecraft-like domain, where an agent has to build a bridge by
first collecting some raw materials, and then using a factory. The agent has
two options. The first option is to complete the tasks $\\{\mathrm{getWood},$
$\mathrm{getIron},$ $\mathrm{getFire}\\}$ in any order, and then
$\\{\mathrm{useFactory}\\}$. The second option is to complete
$\\{\mathrm{getSteel}\\}$, and then $\\{\mathrm{useFactory}\\}$.

A formal description of the example as well as full proofs of all our
technical results are deferred to the appendix.

##  2 Preliminaries

#### Functions.

For $f:X\to Y$ and $g:Y\to Z$, their _composition_ $f\circ g:X\to Z$ is
defined as $(f\circ g)(x)=g(f(x))$. For $f:X\to Y$ and $h:X\to Z$, their
_cross product_ $f\times h:X\to Y\times Z$ is defined as $(f\times
h)(x)=\langle f(x),h(x)\rangle$. A class of functions is _uniform_ if all
functions in the class have the same domain and codomain. Given a tuple
$t=\langle x_{1},\dots,x_{n}\rangle$, and a subset $J\subseteq[1,n]$, the
_projection_ $\pi_{J}(t)$ is $\langle x_{j_{1}},\dots,x_{j_{m}}\rangle$ where
$j_{1},\dots,j_{m}$ is the sorted sequence of elements of $J$. Furthermore,
$\pi_{m}^{a}$ denotes the class of all projections $\pi_{J}$ for $J$ a subset
of $[1,a]$ of cardinality $m$. We write $I$ for the _identity function_ , and
$\log$ for $\log_{2}$.

#### String Functions and Languages.

An _alphabet_ $\Sigma$ is a set of elements called _letters_. A _string_ over
$\Sigma$ is an expression $\sigma_{1}\dots\sigma_{\ell}$ where each letter
$\sigma_{i}$ is from $\Sigma$. The _empty string_ is denoted by $\varepsilon$.
The set of all strings over $\Sigma$ is denoted by $\Sigma^{*}$. A _factored
alphabet_ is of the form $X^{a}$ for some set $X$ called the _domain_ and some
integer $a\geq 1$ called the _arity_. A _string function_ is of the form
$f:\Sigma^{*}\to\Gamma$ for $\Sigma$ and $\Gamma$ alphabets. _Languages_ are a
special case of string functions; namely, when $f:\Sigma\to\\{0,1\\}$ is an
indicator function, it can be equivalently described by the set
$\\{x\in\Sigma^{*}\mid f(x)=1\\}$, that is called a _language_.

##  3 Learning Theory

We introduce the problem of learning, following the classical perspective of
statistical learning theory (Vapnik 1998).

#### Learning Problem.

Consider an input domain $X$ and an output domain $Y$. For example, in the
setting where we classify strings over an alphabet $\Sigma$, the input domain
$X$ is $\Sigma^{*}$ and the output domain $Y$ is $\\{0,1\\}$. The _problem of
learning_ is that of choosing, from an _admissible class_ $\mathcal{F}$ of
functions from $X$ to $Y$, a function $f$ that best approximates an unknown
_target function_ $f_{0}:X\to Y$, not necessarily included in $\mathcal{F}$.
The quality of the approximation of $f$ is given by the overall discrepancy of
$f$ with the target $f_{0}$. On a single domain element $x$, the discrepancy
between $f(x)$ and $f_{0}(x)$ is measured as $L(f(x),f_{0}(x))$, for a given
_loss function_ $L:Y\times Y\to\\{0,1\\}$. The overall discrepancy is the
expectation $\mathbb{E}[L(f(x),f_{0}(x))]$ with respect to an underlying
probability distribution $P$, and it is called the _risk_ of the function,
written $R(f)$. Then, the goal is to choose a function $f\in\mathcal{F}$ that
minimises the risk $R(f)$, when the underlying probability distribution $P$ is
unknown, but we are given a _sample_ $Z_{\ell}$ of $\ell$ i.i.d. elements
$x_{i}\in X$ drawn according to $P(x_{i})$ together with their labels
$f_{0}(x_{i})$; specifically, $Z_{\ell}=z_{1},\dots,z_{\ell}$ with
$z_{i}=\langle x_{i},f_{0}(x_{i})\rangle$.

#### Sample Complexity.

We would like to establish the minimum sample size $\ell$ sufficient to
identify a function $f\in\mathcal{F}$ such that

$R(f)-\min_{f\in\mathcal{F}}R(f)\leq\epsilon$

with probability at least $1-\eta$. We call such $\ell$ the sample complexity
of $\mathcal{F}$, and we write it as $S(\mathcal{F},\epsilon,\eta)$. When
$\epsilon$ and $\eta$ are considered fixed, we write it as $S(\mathcal{F})$.

#### Sample Complexity Bounds for Finite Classes.

When the set of admissible functions $\mathcal{F}$ is finite, its sample
complexity can be bounded in terms of its cardinality, cf. (Shalev-Shwartz and
Ben-David 2014). In particular,

$S(\mathcal{F},\epsilon,\eta)\in
O\big{(}(\log|\mathcal{F}|-\log\eta)/\epsilon^{2}\big{)}.$

Then, for fixed $\epsilon$ and $\eta$, the sample complexity $S(\mathcal{F})$
is $O(\log|\mathcal{F}|)$, and hence finite classes can be compared in terms
of their cardinality.

##  4 Automata

This section introduces basic notions of automata theory, with some
inspiration from (Ginzburg 1968; Maler 1990).

An automaton is a mathematical description of a stateful machine that returns
an output letter on every input string. At its core lies the mechanism that
updates the internal state upon reading an input letter. This mechanism is
captured by the notion of semiautomaton. An $n$-state _semiautomaton_ is a
tuple $D=\langle\Sigma,Q,\delta,q_{\mathrm{init}}\rangle$ where: $\Sigma$ is
an alphabet called the _input alphabet_ ; $Q$ is a set of $n$ elements called
_states_ ; $\delta:Q\times\Sigma\to Q$ is a function called _transition
function_ ; $q_{\mathrm{init}}\in Q$ is called _initial state_. The transition
function is recursively extended to non-empty strings as
$\delta(q,\sigma_{1}\sigma_{2}\dots\sigma_{m})=\delta(\delta(q,\sigma_{1}),\sigma_{2}\dots\sigma_{m})$,
and to the empty string as $\delta(q,\varepsilon)=q$. The result of executing
semiautomaton $D$ on an input string is
$D(\sigma_{1}\dots\sigma_{m})=\delta(q_{\mathrm{init}},\sigma_{1}\dots\sigma_{m})$.
We also call such function $D:\Sigma^{*}\to Q$ the function implemented by the
semiautomaton.

Automata are obtained from semiautomata by adding an output function. An
$n$-state _automaton_ is a tuple
$A=\langle\Sigma,Q,\delta,q_{\mathrm{init}},\Gamma,\theta\rangle$ where:
$D_{A}=\langle\Sigma,Q,\delta,q_{\mathrm{init}}\rangle$ is a semiautomaton,
called the _core semiautomaton_ of $A$; $\Gamma$ is an alphabet called _output
alphabet_ , $\theta:Q\times\Sigma\to\Gamma$ is called _output function_. An
acceptor is a special kind of automaton where the output function is an
indicator function $\theta:Q\times\Sigma\to\\{0,1\\}$. The result of executing
autmaton $A$ on an input string is
$A(\sigma_{1}\dots\sigma_{m})=\theta(D_{A}(\sigma_{1}\dots\sigma_{m-1}),\sigma_{m})$.
We also call such function $A:\Sigma^{*}\to\Gamma$ the function implemented by
the automaton. The language _recognised_ by an acceptor is the set of strings
on which it returns $1$. When two automata $A_{1}$ and $A_{2}$ implement the
same function, we say that $A_{1}$ _is captured by_ $A_{2}$, or equivalently
that $A_{2}$ is captured by $A_{1}$.

The _expressivity_ of a class of automata is the set of functions they
implement. Thus, for acceptors, it is the set of languages they recognise. The
expressivity of all acceptors is the _regular languages_ (Kleene 1956), i.e.,
the languages that can be specified by regular expressions. We will often
point out the expressivity of acceptors because the classes of languages they
capture are widely known.

Figure 2: State diagram of the automaton for Example 2.

######  Example 2.

The automaton for our running example reads traces generated by the agent
while interacting with the environment. The input alphabet is
$\Sigma=\\{\mathrm{blank}$, $\mathrm{wood},$ $\mathrm{iron},$ $\mathrm{fire},$
$\mathrm{steel},$ $\mathrm{factory}\\}$, where $\mathrm{blank}$ describes that
no relvant event happened. The automaton returns $1$ on traces where the agent
has completed the task. The state diagram is depicted in Figure 2, where
transitions for $\mathrm{blank}$ are omitted and they always yield the current
state. The output is $1$ on all transitions entering the double-lined state,
and $0$ otherwise.

The automaton in the example has to keep track of the subset of tasks
completed so far, requiring one state per subset. In general, the number of
states can grow exponentially with the number of tasks.

###  4.1 Existing Sample Complexity Results

Classes of automata are typically defined in terms of the cardinality $k$ of
the input alphabet (assumed to be finite) and the number $n$ of states. The
existing result on the sample complexity of automata is for such a family of
classes.

######  Theorem 1 (Ishigami and Tani, 1997).

Let $\mathcal{A}(k,n)$ be the class of $n$-state acceptors over the input
alphabet $[1,k]$. Then, the sample complexity of $\mathcal{A}(k,n)$ is
$\Theta(k\cdot n\cdot\log n)$.111The original result is equivalently stated in
terms of the VC dimension, introduced later in this paper.

Consequently, learning an acceptor from the class of all acceptors with $k$
input letters and $n$ states requires an amount of data that is at least
$k\cdot n$. Such a dependency is also observed in the existing automata
learning algorithms, e.g., (Angluin 1987; Ron, Singer, and Tishby 1996, 1998;
Clark and Thollard 2004; Palmer and Goldberg 2007; Balle, Castro, and Gavaldà
2013, 2014). More recently, there has been an effort in overcoming the direct
dependency on the cardinality $k$ of the input alphabet, through _symbolic
automata_ (Mens and Maler 2015; Maler and Mens 2017; Argyros and D’Antoni
2018), but their sample complexity has not been studied.

##  5 Automata Cascades

We present the formalism of automata cascades, strongly based on the cascades
from (Krohn and Rhodes 1965)—see also (Ginzburg 1968; Maler 1990; Dömösi and
Nehaniv 2005). The novelty of our formalism is that every cascade component is
equipped with mechanisms for processing of inputs and outputs. This allows for
(_i_) controlling the complexity of components as the size of cascade
increases; and (_ii_) handling large (and even infinite) input alphabets.

######  Definition 1.

An _automata cascade_ is a sequence of automata $A_{1}\ltimes\cdots\ltimes
A_{d}$ where each $A_{i}$ is called a _component_ of the cascade and it is of
the form

$\langle\Sigma_{1}\times\cdots\times\Sigma_{i},Q_{i},\delta_{i},q^{\mathrm{init}}_{i},\Sigma_{i+1},\theta_{i}\rangle.$

The function implemented by the cascade is the one implemented by the
automaton
$\langle\Sigma_{1},Q,\delta,q^{\mathrm{init}},\Sigma_{d+1},\theta\rangle$
having set of states $Q=Q_{1}\times\dots\times Q_{d},$ initial state
$q_{\mathrm{init}}=\langle
q_{1}^{\mathrm{init}},\dots,q_{d}^{\mathrm{init}}\rangle$, transition and
output functions defined as

$\displaystyle\delta(\langle q_{1},\dots,q_{d}\rangle,\sigma)$
$\displaystyle=\langle\delta_{1}(q_{1},\sigma_{1}),\dots,\delta_{d}(q_{d},\sigma_{d})\rangle,$
$\displaystyle\theta(\langle q_{1},\dots,q_{d}\rangle,\sigma)$
$\displaystyle=\theta_{d}(q_{d},\sigma_{d}),$

where each component reads the recursively-defined input

$\sigma_{1}=\sigma\text{, and
}\sigma_{i+1}=\langle\sigma_{i},\theta_{i}(q_{i},\sigma_{i})\rangle.$

A cascade is _simple_ if $\theta_{i}(q,\sigma)=q$, for every $i\in[1,d-1]$.

The components of a cascade are arranged in a sequence. Every component reads
the input and output of the preceding component, and hence, recursively, it
reads the external input together with the output of all the preceding
components. A cascade architecture is depicted in Figure 1. The external input
is the input to the first component, and the overall output is the one of the
last component.

As components of a cascade, we consider automata on factored alphabets that
first apply a _projection_ operation on their input, then apply a map to a
smaller _internal alphabet_ , and finally transition based on the result of
the previous operations.

######  Definition 2.

An $n$-state _automaton_ is a tuple $A=\langle
X^{a},J,\Pi,\phi,Q,\delta,q_{\mathrm{init}},\Gamma,\theta\rangle$ where
$X^{a}$ is the factored input alphabet; $J\subseteq[1,a]$ is the _dependency
set_ and its cardinality $m$ is the _degree of dependency_ ; $\Pi$ is the
finite _internal alphabet_ ; $\phi:X^{m}\to\Pi$ is an _input function_ that
operates on the projected input tuples; $Q$ is a set of $n$ states;
$\delta:Q\times\Pi\to Q$ is the transition function on the interal letters;
$q_{\mathrm{init}}\in Q$ is the initial state; $\Gamma$ is the output
alphabet; and $\theta:Q\times X^{m}\to\Gamma$ is an output function that
operates on the projected input tuples. The automaton induced by $A$ is the
automaton
$A^{\prime}=\langle\Sigma,Q,\delta_{J,\phi},q_{\mathrm{init}},\Gamma,\theta_{J}\rangle$
where the input alphabet is $\Sigma=X^{a}$, the transition function is
$\delta_{J,\phi}(q,\sigma)=\delta(q,\phi(\pi_{J}(\sigma)))$, and the output
function is $\theta_{J}(q,\sigma)=\theta(q,\pi_{J}(\sigma))$. The core
semiautomaton of $A$ is the core semiautomaton of $A^{\prime}$. The string
function implemented by $A$ is the one implemented by the induced automaton.

The above definition adds two key aspects to the standard definition of
automaton. First, the projection operation $\pi_{J}$, that allows for
capturing the dependencies between the components in a cascade. Although every
component receives the output of all the preceding components, it may use only
some of them, and hence the others can be projected away. The dependency set
$J$ corresponds to the indices of the input tuple that are relevant to the
component. Second, the input function $\phi$, that maps the result of the
projection operation to an internal letter. The rationale is that many inputs
trigger the same transitions, and hence they can be mapped to the same
internal letter. This particularly allows for decoupling the size of the core
semiautomaton from the cardinality of the input alphabet—in line with the
mechanisms of symbolic automata (Maler and Mens 2017; Argyros and D’Antoni
2018).

##  6 Expressivity of Automata Cascades

Cascades can be built out of any set of components. However, the theory by
Krohn and Rhodes identifies a set of _prime automata_ that is a sufficient set
of components to build cascades, as it allows for capturing all automata. They
are, in a sense, the building blocks of automata. Moreover, using only some
prime automata, we obtain specialised expressivity results.

###  6.1 Prime Components

Figure 3: Some of the simplest prime automata: two flip-flops (left), and a
$5$-counter (right).

Prime automata are partitioned into two classes. The _first class of prime
automata_ are flip-flops, a kind of automaton that allows for storing one bit
of information.

######  Definition 3.

A _flip-flop_ is a two-state automaton $\langle
X^{a},J,\Pi,\phi,Q,\delta,q_{\mathrm{init}},\Gamma,\theta\rangle$ where
$\Pi=\\{\mathrm{set},\mathrm{reset},\mathrm{read}\\}$, $Q=\\{0,1\\}$ and the
transition function satisfies the following three identities:

$\delta(q,\mathrm{read})=q,\quad\delta(q,\mathrm{set})=1,\quad\delta(q,\mathrm{reset})=0.$

Figure 3 depicts two flip-flops. The top flip-flop implements a rewritable bit
of memory, since it can be set, reset, and read—e.g., it captures whether ‘an
event has just happened’. The bottom flip-flop implements a write-once bit of
memory, since it cannot be reset—e.g., it captures whether ‘an event has ever
happened’.

We capture the task of our running example with a cascade where each task is
captured exactly by a flip-flop.

######  Example 3.

The sequence task of our running example is captured by the cascade

$A_{\mathrm{wood}}\ltimes A_{\mathrm{iron}}\ltimes A_{\mathrm{fire}}\ltimes
A_{\mathrm{steel}}\ltimes A_{\mathrm{factory}}$

where each component is a flip-flop that outputs its current state. The
diagram for the cascade is shown in Figure 4, where $\mathrm{getWood}$
corresponds to $A_{\mathrm{wood}}$, and similarly for the other components.
All components read the input, and only $A_{\mathrm{factory}}$ also reads the
output of the other components. Thus, the dependency set of
$A_{\mathrm{wood}},$ $A_{\mathrm{iron}},$ $A_{\mathrm{fire}},$ and
$A_{\mathrm{steel}}$ is the singleton $\\{1\\}$, and the dependency set of
$A_{\mathrm{factory}}$ is $\\{1,2,3,4,5\\}$—note that the indices correspond
to positions of the components in the cascade. Then, $A_{\mathrm{wood}}$ has
input function $\phi_{\mathrm{wood}}(x)$ that returns $\mathrm{set}$ if
$x=\mathrm{wood}$, and returns $\mathrm{read}$ otherwise. Similarly,
$A_{\mathrm{iron}},$ $A_{\mathrm{fire}},$ and $A_{\mathrm{steel}}$. Instead,
the component $A_{\mathrm{factory}}$ has input function
$\phi_{\mathrm{factory}}(x,\mathit{wood},\mathit{iron},\mathit{fire},\mathit{steel})$
that returns $\mathrm{set}$ if

$\displaystyle(x=\mathrm{factory})\land[(\mathit{wood}\land\mathit{iron}\land\mathit{fire})\lor\mathit{steel}]$

and returns $\mathrm{read}$ otherwise.

The _second class of prime automata_ is a class of automata that have a
correspondence with simple groups from group theory. Their general definition
is beyond the scope of this paper. For that, see (Ginzburg 1968). Here we
present the class of prime counters, as a subclass that seems particularly
relevant from a practical point of view.

######  Definition 4.

An _$n$ -counter_ is an $n$-state automaton $\langle
X^{a},J,\Pi,\phi,Q,\delta,q_{\mathrm{init}},\Gamma,\theta\rangle$ where
$\Pi=\\{\mathrm{inc},\mathrm{read}\\}$, $Q=[0,n-1]$, and the transition
function satisfies the following two identities:

$\delta(i,\mathrm{read})=i,\quad\delta(i,\mathrm{inc})=i+1\,(\operatorname{mod}n).$

An $n$-counter is _prime_ if $n$ is a prime number.

An $n$-counter implements a counter modulo $n$. The modulo aspect can be seen
both as a bug and a feature. We may be interested just in counting; then, the
modulo stands for the overflow due to finite memory. On the other hand, we
might be interested in counting modulo $n$; for instance, to capture periodic
events such as ‘something happens every 24 hours’. A $5$-counter, that is a
prime counter, is depicted in Figure 3.

######  Example 4.

Resuming our running example, say that now, in order to use the factory, we
need  (i) $13$pieces of wood, $5$ pieces of iron, and fire, or alternatively
(ii) $7$pieces of steel.  From the cascade in Example 3, it suffices to change
the cascade components
$A_{\mathrm{wood}},A_{\mathrm{iron}},A_{\mathrm{steel}}$ into counters (e.g.,
$16$-counters) and change the input function of $A_{\mathrm{factory}}$ so that
$\phi_{\mathrm{factory}}(x,\mathit{wood},\mathit{iron},\mathit{fire},\mathit{steel})$
returns $\mathrm{set}$ if

$\displaystyle(x=\mathrm{factory})\land{}$
$\displaystyle\big{[}\big{(}(\mathit{wood}\geq 13)\land(\mathit{iron}\geq
5)\land\mathit{fire}\big{)}\lor(\mathit{steel}\geq 7)\big{]},$

and it returns $\mathrm{read}$ otherwise. The rest is left unchanged. The
cascade, despite its simplicity, corresponds to an automaton that has over
$700$ states. Furthermore, suppose that we need to learn to detect
$\mathrm{wood}$, $\mathrm{iron}$, $\mathrm{fire}$, $\mathrm{steel}$ from video
frames represented as vectors of $\mathbb{R}^{a}$. It suffices to replace the
input function of the corresponding components with a function over
$\mathbb{R}^{a}$ such as a neural network.

###  6.2 Expressivity Results

A key aspect of automata cascades is their expressivity. As an immediate
consequence of the Krohn-Rhodes theorem (Krohn and Rhodes 1965)—see also
(Ginzburg 1968; Maler 1990; Dömösi and Nehaniv 2005)—we have that simple
cascades of prime automata capture all automata.

######  Theorem 2.

Every automaton is captured by a simple cascade of prime automata.
Furthermore, every counter-free automaton is captured by a simple cascade of
flip-flops. The converse of both claims holds as well.

The second part of the theorem is worth noting, since counter-free acceptors
have the expressivity of _star-free regular languages_ (Schützenberger
1965)—i.e., the languages that can be specified by regular expressions without
using the Kleene star—which is the expressivity of well-known logics such as
_monadic first-order logic on finite linearly-ordered domains_ (McNaughton and
Papert 1971), and the _linear temporal logic on finite traces_ LTLf (De
Giacomo and Vardi 2013).

######  Corollary 1.

The expressivity of simple cascades of prime automata is the regular
languages. The expressivity of simple cascades of flip-flops is the star-free
regular languages.

Figure 4: Diagram for the cascade of the running example.

##  7 Sample Complexity of Automata Cascades

We study the sample complexity of class of automata (and cascades thereof)
built from given classes of input functions, semiautomata, and output
functions. This allows for a fine-grained specification of automata and
cascades.

######  Definition 5.

The class $\mathcal{A}(\Phi,\Delta,\Theta)$ over a given input alphabet
$X^{a}$ consists of each automaton with input function from a given class
$\Phi$, core semiautomaton from a given class $\Delta$, and output function
from a give class $\Theta$. The classes $\Phi$, $\Delta$, $\Theta$ are
uniform, and hence all automata in $\mathcal{A}(\Phi,\Delta,\Theta)$ have the
same degree of dependency $m$, same internal alphabet $\Pi$, and same output
alphabet $\Gamma$; hence, sometimes we write
$\mathcal{A}(\Phi,\Delta,\Theta;a,m)$ and
$\mathcal{A}(\Phi,\Delta,\Theta;a,m,\Pi,\Gamma)$ to have such quantities at
hand.

###  7.1 Results for Finite Classes of Cascades

The following two theorems establish upper bounds on the cardinality and
sample complexity of finite classes of automata, and finite classes of
cascades, respectively. The results are obtained by counting the number of
ways in which we can instantiate the parts of a single automaton.

######  Theorem 3.

The cardinality of a class of automata
$\mathcal{A}=\mathcal{A}(\Phi,\Delta,\Theta;a,m)$ is bounded as

$\left|\mathcal{A}\right|\leq\left|\pi_{m}^{a}\right|\cdot\left|\Phi\right|\cdot\left|\Delta\right|\cdot\left|\Theta\right|,$

and its sample complexity is asymptotically bounded as

$S(\mathcal{A})\in
O\big{(}\log\left|\pi_{m}^{a}\right|+\log\left|\Phi\right|+\log\left|\Delta\right|+\log\left|\Theta\right|\big{)}.$

######  Theorem 4.

The cardinality of a class of automata cascades
$\mathcal{C}=\mathcal{A}_{1}\ltimes\cdots\ltimes\mathcal{A}_{d}$ where the
automata classes are
$\mathcal{A}_{i}=\mathcal{A}(\Phi_{i},\Delta_{i},\Theta_{i};a_{i},m_{i})$ is
bounded as

$\left|\mathcal{C}\right|\leq\prod_{i=1}^{d}\left|\pi_{m_{i}}^{a_{i}}\right|\cdot\left|\Phi_{i}\right|\cdot\left|\Delta_{i}\right|\cdot\left|\Theta_{i}\right|,$

and its sample complexity is asymptotically bounded as

$S(\mathcal{C})\in
O\Big{(}d\cdot(\log\left|\pi_{m}^{a}\right|\,+\,\log\left|\Phi\right|\,+\,\log\left|\Delta\right|\,+\,\log\left|\Theta\right|)\Big{)},$

where dropping the indices denotes the maximum.

Consequently, the complexity of a cascade is bounded by the product of the
number $d$ of components and a second factor that bounds the complexity of a
single component.

###  7.2 Aspects and Implications of The Results

The term $\log|\pi_{m}^{a}|$, accounting for the projection functions, ranges
from $0$ to $\min(m,a_{1}+d-m)\cdot\log(a_{1}+d)$ where $a_{1}$ is the input
arity of the first component, and hence of the external input. In particular,
it is minimum when we allow each component to depend on all or none of its
preceding components, and it is maximum when each component has to choose half
of its preceding components as its dependencies.

The term $\log|\Phi|$ plays an important role, since the set of input
functions has to be sufficiently rich so as to map the external input and the
outputs of the preceding components to the internal input. First, its
cardinality can be controlled by the degree of dependency $m$; for instance,
taking all Boolean functions yields $\log|\Phi|=2^{m}$. Notably, it does not
depend on $d$, and hence, the overall sample complexity grows linearly with
the number of cascade components as long as the degree of dependency $m$ is
bounded. Second, the class of input functions can be tailored towards the
application at hand. For instance, in our running example, input functions can
be chosen from a class $\Phi$ such that $\log|\Phi|$ is linear in the number
of tasks—see Example 5 below.

The term $\log|\Delta|$ is the contribution of the _number of semiautomata_
—note that the number of letters and states of each semiautomaton plays no
role. Interestingly, very small classes of semiautomata suffice to build very
expressive cascades, by the results in Section 5. In general, it is sufficient
to build $\Delta$ out of prime components. But we can also include other
semiautomata implementing some interesting functionality.

The term $\log|\Theta|$ admits similar considerations as $\log|\Phi|$. It is
worth noting that one can focus on simple cascades, by the results in Section
5, where output functions of all but last component component are fixed. Then,
the contribution to the sample complexity is given by the class of output
functions of the last component.

Overall, the sample complexity grows linearly with the number $d$ of
components, modulo a logarithmic factor. Specifically, the term
$\log|\pi^{a}_{m}|$ has only a logarithmic dependency on $d$, and the other
terms $\log|\Phi|,$ $\log|\Delta|,$ and $\log|\Theta|$ are independent of $d$.

######  Corollary 2.

Let us recall the quantities from Theorem 4, and fix the quantities $a$, $m$,
$\Phi$, $\Delta$, and $\Theta$. Then, the sample complexity of $\mathcal{C}$
is bounded as $S(\mathcal{C})\in O(d\cdot\log d)$.

######  Example 5.

The cascade described in Example 3 has one component per task, and all
components have the same output function and semiautomaton. The input function
$\phi_{\mathrm{factory}}$ is $2$-term monotone DNF over $9$ propositional
variables. Every other component has an input function that is $1$-term
monotone DNF over $5$ propositional variables. Using these observations, we
can design a class of cascades for similar sequence tasks where the goal task
depends on two groups of arbitrary size, having $d$ basic tasks overall. Such
a class will consist of cascades of $d$ components. For every $i\in[1,d-1]$,
the class of input functions $\Phi_{i}$ is the class of $1$-term monotone DNF
over $d$ variables; and $\Phi_{d}$ is the class of $2$-term monotone DNF over
$2d-1$ variables. For all $i\in[1,d]$, $\Delta_{i}$ is a singleton consisting
of a flip-flop semiautomaton; and $\Theta_{i}$ is a singleton consisting of
the function that returns the state. The cardinality of $\Phi_{i}$ is
$e^{2}\cdot 2^{(4d-4)}$, and hence its logarithm is less than $4d$—see
Corollary 5 of (Schmitt 2004). By Theorem 4, considering that we have $d$
cascade components, we obtain that our class of cascades has sample complexity
$O(d^{2})$. At the same time, the minimum automaton for the considered family
of sequence tasks has $\Omega(2^{d})$ states. Going back to the bound of
Theorem 1, if we had to learn from the class of all automata with $2^{d}$
states, we would incur a sample complexity exponential in the number of tasks.

###  7.3 Learning Theory for Infinite Classes

Infinite classes of cascades naturally arise when the input alphabet is
infinite. In this case, one may consider to pick input and output functions
from an infinite class. For instance, the class of all threshold functions
over the domain of integers, or as in Example 4 the neural networks over the
vectors of real numbers.

When considering infinite classes of functions, the sample complexity bounds
based on cardinality become trivial. However, even when the class is infinite,
the number of functions from the class that can be distinguished on a given
sample is finite, and the way it grows as a function of the sample size allows
for establishing sample complexity bounds. In turn, such _growth_ can be
bounded in terms of the _dimension_ of the class of functions, a single-number
characterisation of its complexity. Next we present these notions formally.

#### Growth and Dimension.

Let $\mathcal{F}$ be a class of functions from a set $X$ to a finite set $Y$.
Let $X_{\ell}=x_{1},\dots,x_{\ell}$ be a sequence of $\ell$ elements from $X$.
The set of _patterns_ of a class $\mathcal{F}$ on $X_{\ell}$ is

$\mathcal{F}(X_{\ell})=\\{\langle f(x_{1}),\dots,f(x_{\ell})\rangle\mid
f\in\mathcal{F}\\},$

and the _number of distinct patterns_ of class $\mathcal{F}$ on $X_{\ell}$ is
$N(\mathcal{F},X_{\ell})=|\mathcal{F}(X_{\ell})|$. The _growth_ of
$\mathcal{F}$ is

$G(\mathcal{F},\ell)=\operatorname{sup}_{X_{\ell}}N(\mathcal{F},X_{\ell}).$

The growth of $\mathcal{F}$ can be bounded using its _dimension_ , written as
$\operatorname{dim}(\mathcal{F})$. When $|Y|=2$, we define the dimension of
$\mathcal{F}$ to be its _VC dimension_ (Vapnik and Chervonenkis 1971)—see also
(Vapnik 1998). It is the largest integer $h$ such that
$G(\mathcal{F},h)=2^{h}$ and $G(\mathcal{F},h+1)<2^{h+1}$ if such an $h$
exists, and infinity otherwise. When $|Y|>2$, we define the dimension of
$\mathcal{F}$ to be its _graph dimension_ (Natarajan 1989; Haussler and Long
1995). It is defined by first binarising the class of functions. For a given
function $f:X\to Y$, its binarisation $f_{\mathrm{bin}}:X\times Y\to\\{0,1\\}$
is defined as $f_{\mathrm{bin}}(x,y)=\mathbf{1}[f(x)=y]$. The _binarisation_
of $\mathcal{F}$ is $\mathcal{F}_{\mathrm{bin}}=\\{f_{\mathrm{bin}}\mid
f\in\mathcal{F}\\}$. Then, the graph dimension of $\mathcal{F}$ is defined as
the VC dimension of its binarisation $\mathcal{F}_{\mathrm{bin}}$.

The growth of $\mathcal{F}$ can be bounded in terms of its dimension (Haussler
and Long 1995), as follows:

$G(\mathcal{F},\ell)\leq\left(e\cdot\ell\cdot|Y|\right)^{\operatorname{dim}(\mathcal{F})}.$

#### Sample Complexity.

The sample complexity can be bounded in terms of the dimension, cf. (Shalev-
Shwartz and Ben-David 2014). In particular,

$S(\mathcal{F},\epsilon,\eta)\in
O\left((\operatorname{dim}(\mathcal{F})\cdot\log|Y|-\log\eta)/\epsilon^{2}\right).$

For fixed $\epsilon$, $\eta$, and $Y$, the sample complexity is
$O(\operatorname{dim}(\mathcal{F}))$, and hence arbitrary classes over the
same outputs can be compared in terms of their dimension.

###  7.4 Results for Infinite Classes of Cascades

We generalise our sample complexity bounds to infinite classes of automata and
cascades. The bound have the same shape of the bounds derived in Section 7.1
for finite classes, with the dimension replacing the logarithm of the
cardinality. One notable difference is the logarithmic dependency on the
maximum length $M$ of a string. It occurs due to the (stateless) input and
output functions. Their growth is on single letters, regardless of the way
they are grouped into strings. Thus, the growth on a sample of $\ell$ strings
is the growth on a sample of $\ell\cdot M$ letters.

The bounds are derived using a functional description of automata and
cascades. It is a shift of perspective, from stateful machines that process
one letter at a time, to black-boxes that process an entire input string at
once. We first introduce function constructors to help us to build such
descriptions.

######  Definition 6 (Function constructors).

For $f:\Sigma\to\Gamma$, $f^{*}:\Sigma^{*}\to\Gamma$ is defined as
$f^{*}(\sigma_{1}\dots\sigma_{n})=f(\sigma_{n})$. For $g:\Sigma^{*}\to\Gamma$,
$\overline{g}:\Sigma^{*}\to\Gamma^{*}$ is defined as
$\overline{g}(\sigma_{1}\dots\sigma_{n})=g(\sigma_{1})\dots
g(\sigma_{1}\dots\sigma_{n})$; furthermore,
$g^{\triangleleft}:\Sigma^{*}\to\Gamma^{*}$ is defined as
$g^{\triangleleft}(\sigma_{1}\dots\sigma_{n})=g(\sigma_{1}\dots\sigma_{n-1})$.

######  Lemma 1.

The function $A$ implemented by an automaton $\langle
X^{a},J,\Pi,\phi,Q,\delta,q_{\mathrm{init}},\Gamma,\theta\rangle$ can be
expressed as

$A=\overline{\pi^{*}_{J}}\circ((\overline{\phi^{*}}\circ
D^{\triangleleft})\times I^{*})\circ\theta,$

where $D$ is the function implemented by the semiautomaton
$\langle\Pi,Q,\delta,q_{\mathrm{init}}\rangle$.

Note that $I^{*}$ propagates the projected input to the output function. Also
note that the output function reads the state before the last update. The
functional description allows us to bound the growth, by making use of the
fact that the growth of composition and cross product of two classes of
functions is upper bounded by the product of their respective growths. From
there, we derive the dimension, and the sample complexity.

######  Theorem 5.

Let $\mathcal{A}$ be a class $\mathcal{A}(\Phi,\Delta,\Theta;a,m,\Pi,\Gamma)$,
let $M$ be the maximum length of a string, and let
$w=\log\left|\pi_{m}^{a}\right|+\log\left|\Delta\right|+\operatorname{dim}(\Phi)+\operatorname{dim}(\Theta)\geq
2$.

(i) The growth of $\mathcal{A}$ is bounded as:

$G(\mathcal{A},\ell)\leq\left|\pi^{a}_{m}\right|\cdot\left|\Delta\right|\cdot
G(\Phi,\ell\cdot M)\cdot G(\Theta,\ell).$

(ii) The dimension of $\mathcal{A}$ is bounded as:

$\operatorname{dim}(\mathcal{A})\leq 2\cdot w\cdot\log(w\cdot e\cdot
M\cdot|\Pi|\cdot|\Gamma|).$

(iii) The sample complexity of $\mathcal{A}$ is bounded as:

$S(\mathcal{A})\in O\big{(}w\cdot\log(w\cdot
M\cdot|\Pi|\cdot|\Gamma|)\big{)}.$

Next we show the functional description of an automata cascade. It captures
the high-level idea that each component of a cascade can be fully executed
before executing any of the subsequent automata, since it does not depend on
them.

######  Lemma 2.

The function implemented by an automata cascade $A_{1}\ltimes\cdots\ltimes
A_{d}$ with $d\geq 2$ can be expressed as

$\overline{(I^{*}\times A_{1})}\circ\dots\circ\overline{(I^{*}\times
A_{d-1})}\circ A_{d}.$

The cross product with $I^{*}$ in the functional description above captures
the fact that the input of each component is propagated to the next one.

Then, a bound on the growth is derived from the functional description, and
hence the dimension and sample complexity bounds.

######  Theorem 6.

Let $\mathcal{C}$ be a class
$\mathcal{A}_{1}\ltimes\dots\ltimes\mathcal{A}_{d}$ where automata classes are
$\mathcal{A}_{i}=\mathcal{A}(\Phi_{i},\Delta_{i},\Theta_{i};a_{i},m_{i},\Pi_{i},\Gamma_{i})$,
let $M$ be the maximum length of a string, and let
$w=\log\left|\pi_{m}^{a}\right|+\log\left|\Delta\right|+\operatorname{dim}(\Phi)+\operatorname{dim}(\Theta)\geq
2$ where dropping the indices denotes the maximum.

(i) The growth of $\mathcal{C}$ is bounded as:

$G(\mathcal{C},\ell)\leq\prod_{i=1}^{d}\left|\pi_{m_{i}}^{a_{i}}\right|\cdot\left|\Delta_{i}\right|\cdot
G(\Phi_{i},\ell\cdot M)\cdot G(\Theta_{i},\ell\cdot M).$

(ii) The dimension of $\mathcal{C}$ is bounded as:

$\operatorname{dim}(\mathcal{C})\leq 2\cdot d\cdot w\cdot\log(d\cdot w\cdot
e\cdot M\cdot|\Pi|\cdot|\Gamma|).$

(iii) The sample complexity of $\mathcal{C}$ is bounded as:

$S(\mathcal{C})\in O\big{(}d\cdot w\cdot\log(d\cdot w\cdot
M\cdot|\Pi|\cdot|\Gamma|)\big{)}.$

By a similar reasoning as in the results for finite classes, the sample
complexity has a linear dependency on the number $d$ of cascade components,
modulo a logarithmic factor.

######  Corollary 3.

Let us recall the quantities from Theorem 6, and fix the quantities $a_{1}$,
$m$, $\Phi$, $\Delta$, $\Theta$, $M$, $\Pi$, and $\Gamma$. Then, the sample
complexity of $\mathcal{C}$ is bounded as $S(\mathcal{C})\in O(d\cdot\log d)$.

##  8 Related Work

The main related work is the sample complexity bounds from (Ishigami and Tani
1997), stated in Theorem 1. Our bounds are qualitatively different, as they
allow for describing the sample complexity of a richer variety of classes of
automata, and cascades thereof. With reference to Theorem 3, their specific
case is obtained when: the input alphabet is non-factored and hence
$|\pi^{a}_{m}|=1$; $\Phi=\\{I\\}$ and hence $|\Pi|=|\Sigma|=k$; $\Delta$ is
the class of all semiautomata on $k$ letters and $n$ states, and hence
$|\Delta|=n^{k\cdot n}$; and $\Theta$ is the class of all indicator functions
on $n$ states, and hence $|\Theta|=2^{n}$. In this case, it is easy to verify
that our bound matches theirs.

Learning automata expressed as a cross product is considered in (Moerman
2018). They correspond to cascades where all components read the input, but no
component reads the output of the others. The authors provide a so-called
_active learning_ algorithm, that asks membership and equivalence queries.
Although it is a different setting from ours, it is interesting that they
observe an exponential gain in some specific cases, compared to ignoring the
product structure of the automata.

The idea of decoupling the input alphabet from the core functioning of an
automaton is found in _symbolic automata_. The existing results on learning
symbolic automata are in the active learning setting (Berg, Jonsson, and
Raffelt 2006; Mens and Maler 2015; Maler and Mens 2017; Argyros and D’Antoni
2018).

##  9 Conclusion

Given the favourable sample complexity of automata cascades, the next step is
to devise learning algorithms, able to learn automata as complex systems
consisting of many components implementing specific functionalities.

## Acknowledgments

This work has been supported by the ERC Advanced Grant WhiteMech (No. 834228),
by the EU ICT-48 2020 project TAILOR (No. 952215), by the PRIN project RIPER
(No. 20203FFYLK), by the EU’s Horizon 2020 research and innovation programme
under grant agreement No. 682588.

## References

  * Abadi and Brafman (2020) Abadi, E.; and Brafman, R. I. 2020.  Learning and Solving Regular Decision Processes.  In _IJCAI_.
  * Andreas, Klein, and Levine (2017) Andreas, J.; Klein, D.; and Levine, S. 2017.  Modular Multitask Reinforcement Learning with Policy Sketches.  In _ICML_.
  * Angluin (1987) Angluin, D. 1987.  Learning Regular Sets from Queries and Counterexamples.  _Inf. Comput._
  * Argyros and D’Antoni (2018) Argyros, G.; and D’Antoni, L. 2018.  The Learnability of Symbolic Automata.  In _CAV_.
  * Balle, Castro, and Gavaldà (2013) Balle, B.; Castro, J.; and Gavaldà, R. 2013.  Learning probabilistic automata: A study in state distinguishability.  _Theory Comput. Sci._
  * Balle, Castro, and Gavaldà (2014) Balle, B.; Castro, J.; and Gavaldà, R. 2014.  Adaptively learning probabilistic deterministic automata from data streams.  _Mach. Learn._
  * Berg, Jonsson, and Raffelt (2006) Berg, T.; Jonsson, B.; and Raffelt, H. 2006.  Regular Inference for State Machines with Parameters.  In _FASE_.
  * Brafman and De Giacomo (2019) Brafman, R. I.; and De Giacomo, G. 2019.  Regular Decision Processes: A Model for Non-Markovian Domains.  In _IJCAI_.
  * Clark and Thollard (2004) Clark, A.; and Thollard, F. 2004.  PAC-learnability of Probabilistic Deterministic Finite State Automata.  _J. Mach. Learn. Res._
  * De Giacomo et al. (2019) De Giacomo, G.; Iocchi, L.; Favorito, M.; and Patrizi, F. 2019.  Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf Restraining Specifications.  In _ICAPS_.
  * De Giacomo and Vardi (2013) De Giacomo, G.; and Vardi, M. Y. 2013.  Linear Temporal Logic and Linear Dynamic Logic on Finite Traces.  In _IJCAI_.
  * Dömösi and Nehaniv (2005) Dömösi, P.; and Nehaniv, C. L. 2005.  _Algebraic Theory of Automata Networks: An Introduction_.  SIAM.
  * Gaon and Brafman (2020) Gaon, M.; and Brafman, R. I. 2020.  Reinforcement Learning with Non-Markovian Rewards.  In _AAAI_.
  * Ginzburg (1968) Ginzburg, A. 1968.  _Algebraic Theory of Automata_.  Academic Press.
  * Haussler and Long (1995) Haussler, D.; and Long, P. M. 1995.  A generalization of Sauer’s lemma.  _J. Comb. Theory Ser. A_.
  * Hopcroft and Ullman (1979) Hopcroft, J.; and Ullman, J. 1979.  _Introduction to Automata Theory, Languages, and Computation_.  Addison-Wesley.
  * Ishigami and Tani (1997) Ishigami, Y.; and Tani, S. 1997.  VC-dimensions of Finite Automata and Commutative Finite Automata with $k$ Letters and $n$ States.  _Discret. Appl. Math._
  * Jothimurugan et al. (2021) Jothimurugan, K.; Bansal, S.; Bastani, O.; and Alur, R. 2021.  Compositional Reinforcement Learning from Logical Specifications.  In _NeurIPS_.
  * Kleene (1956) Kleene, S. C. 1956.  Representation of events in nerve nets and finite automata.  _Automata studies_.
  * Krohn and Rhodes (1965) Krohn, K.; and Rhodes, J. 1965.  Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines.  _Trans. Am. Math. Soc._
  * Maler (1990) Maler, O. 1990.  _Finite Automata: Infinite Behaviour, Learnability and Decomposition_.  Ph.D. thesis, The Weizmann Institute of Science.
  * Maler and Mens (2017) Maler, O.; and Mens, I. 2017.  A Generic Algorithm for Learning Symbolic Automata from Membership Queries.  In _Models, Algorithms, Logics and Tools_.
  * McNaughton and Papert (1971) McNaughton, R.; and Papert, S. A. 1971.  _Counter-Free Automata_.  The MIT Press.
  * Mens and Maler (2015) Mens, I.; and Maler, O. 2015.  Learning Regular Languages over Large Ordered Alphabets.  _Log. Methods Comput. Sci._
  * Moerman (2018) Moerman, J. 2018.  Learning Product Automata.  In _ICGI_.
  * Natarajan (1989) Natarajan, B. K. 1989.  On Learning Sets and Functions.  _Mach. Learn._
  * Neider et al. (2021) Neider, D.; Gaglione, J.; Gavran, I.; Topcu, U.; Wu, B.; and Xu, Z. 2021.  Advice-Guided Reinforcement Learning in a non-Markovian Environment.  In _AAAI_.
  * Palmer and Goldberg (2007) Palmer, N.; and Goldberg, P. W. 2007.  PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance.  _Theory Comput. Sci._
  * Ron, Singer, and Tishby (1996) Ron, D.; Singer, Y.; and Tishby, N. 1996.  The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length.  _Mach. Learn._
  * Ron, Singer, and Tishby (1998) Ron, D.; Singer, Y.; and Tishby, N. 1998.  On the Learnability and Usage of Acyclic Probabilistic Finite Automata.  _J. Comput. Syst. Sci._
  * Ronca and De Giacomo (2021) Ronca, A.; and De Giacomo, G. 2021.  Efficient PAC Reinforcement Learning in Regular Decision Processes.  In _IJCAI_.
  * Ronca, Paludo Licks, and De Giacomo (2022) Ronca, A.; Paludo Licks, G.; and De Giacomo, G. 2022.  Markov Abstractions for PAC Reinforcement Learning in Regular Decision Processes.  In _IJCAI_.
  * Schmitt (2004) Schmitt, M. 2004.  An Improved VC Dimension Bound for Sparse Polynomials.  In _COLT_.
  * Schützenberger (1965) Schützenberger, M. P. 1965.  On Finite Monoids Having Only Trivial Subgroups.  _Inf. Control._
  * Shalev-Shwartz and Ben-David (2014) Shalev-Shwartz, S.; and Ben-David, S. 2014.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge University Press.
  * Toro Icarte et al. (2018) Toro Icarte, R.; Klassen, T. Q.; Valenzano, R. A.; and McIlraith, S. A. 2018.  Using Reward Machines for High-Level Task Specification and Decomposition in Reinforcement Learning.  In _ICML_.
  * Vapnik (1998) Vapnik, V. N. 1998.  _Statistical learning theory_.  Wiley.
  * Vapnik and Chervonenkis (1971) Vapnik, V. N.; and Chervonenkis, A. Y. 1971.  On The Uniform Convergence of Relative Frequencies of Events to Their Probabilities.  _Theory Probab. its Appl._
  * Xu et al. (2020) Xu, Z.; Gavran, I.; Ahmad, Y.; Majumdar, R.; Neider, D.; Topcu, U.; and Wu, B. 2020\.  Joint Inference of Reward Machines and Policies for Reinforcement Learning.  In _ICAPS_.

##  Appendix A Proofs

###  A.1 Proof of Theorem 2 (Expressivity of Automata Cascades)

We first introduce the _cascade product_ between semiautomata. Given two
semiautomata

$\displaystyle D_{1}$
$\displaystyle=\langle\Sigma,Q,\delta_{1},q_{\mathrm{init}}^{1}\rangle,$
$\displaystyle D_{2}$ $\displaystyle=\langle\Sigma\times
Q,Q,\delta_{2},q_{\mathrm{init}}^{2}\rangle,$

their cascade product $D_{1}\ltimes D_{2}$ yields the semiautomaton
$D=\langle\Sigma,Q,\delta,q_{\mathrm{init}}\rangle$ where

$\displaystyle Q$ $\displaystyle=Q_{1}\times Q_{2},$ $\displaystyle
q_{\mathrm{init}}$ $\displaystyle=\langle
q_{\mathrm{init}}^{1},q_{\mathrm{init}}^{2}\rangle,$
$\displaystyle\delta(\langle q_{1},q_{2}\rangle,\sigma)$
$\displaystyle=\langle\delta_{1}(q_{1},\sigma),\delta_{2}(q_{2},\langle
q_{1},\sigma\rangle)\rangle.$

The cascade product on semiautomata is left-associative. Hence, given
semiautomata $D_{i}=\langle\Sigma\times Q_{1}\times\dots\times
Q_{i-1},Q_{i},\delta_{i},q_{\mathrm{init}}^{i}\rangle$ for $i\in[1,d]$, we can
build a semiautomaton as $D_{1}\ltimes\cdots\ltimes D_{d}$.

The proof of Theorem 2 is based on the following theorem, which is an
immediate consequence of the Krohn-Rhodes Prime Decomposition Theorem (Krohn
and Rhodes 1965), together with Theorem 5.6 of (Ginzburg 1968).

######  Theorem 7 (Krohn and Rhodes + Ginzburg).

Every automaton $A$ is captured by an automaton $A^{\prime}$ whose core
semiautomaton is expressed by a cascade product $A_{1}\ltimes\cdots\ltimes
A_{d}$ where each $A_{i}$ is a prime semiautomaton. Furthermore, every
counter-free automaton $A$ is captured by an automaton $A^{\prime}$ whose core
semiautomaton is expressed by a cascade product $A_{1}\ltimes\cdots\ltimes
A_{d}$ where each $A_{i}$ is a flip-flop semiautomaton. The converse of both
claims holds as well.

See 2

###### Proof.

Consider an automaton
$A=\langle\Sigma,Q,\delta,q_{\mathrm{init}},\Gamma,\theta\rangle$. By Theorem
7, automaton $A$ is captured by an automaton
$A^{\prime}=\langle\Sigma,Q^{\prime},\delta^{\prime},q^{\prime}_{\mathrm{init}},\Gamma,\theta^{\prime}\rangle$
such that its semiautomaton
$\langle\Sigma,Q^{\prime},\delta^{\prime},q_{\mathrm{init}}^{\prime}\rangle$
is expressed by a cascade product $D_{1}\ltimes\cdots\ltimes D_{d}$ where each
$D_{i}$ is a prime semiautomaton of the form $\langle\Sigma\times
Q_{1}\times\dots\times Q_{i-1},Q_{i},\delta_{i},q_{\mathrm{init}}^{i}\rangle$.
For every $i\in[1,d-1]$, let $A_{i}$ be the automaton with core semiautomaton
$D_{i}$ and output function
$\theta_{i}(q_{i},\langle\sigma,q_{1},\dots,q_{i-1}\rangle)=q_{i}$. Also, let
$A_{d}$ be the automaton with core semiautomaton $D_{d}$ and output function
$\theta_{d}(q_{d},\langle\sigma,q_{1},\dots,q_{d-1}\rangle)=\theta^{\prime}(\langle
q_{1},\dots,q_{d}\rangle,\sigma)$. Now, consider the cascade
$C=(A_{1},\dots,A_{d})$ made of the automata just introduced. Since the
cascade is simple and its components are prime, it suffices to show that $A$
is captured by $C$. Namely, that $A$ and $C$ implement the same function. Let
$A_{C}=\langle\Sigma,Q_{C},\delta_{C},q^{\mathrm{init}}_{C},\Gamma,\theta_{C}\rangle$
be the automaton corresponding to the cascade $C$. Consider an input string
$\sigma_{1}\dots\sigma_{m}$. Let $q=\langle q_{1},\dots,q_{d}\rangle$ be the
state of $A_{C}$ after reading $\sigma_{1}\dots\sigma_{m-1}$; namely,
$q=\delta_{C}(q^{\mathrm{init}}_{C},\sigma_{1}\dots\sigma_{m-1})$. The
function implemented by $C$ is

$\displaystyle
C(\sigma_{1}\dots\sigma_{m})=\theta_{d}(q_{d},\langle\sigma_{m},q_{1},\dots,q_{d-1}\rangle)=\theta^{\prime}(\langle
q_{1},\dots,q_{d}\rangle,\sigma_{m})=A^{\prime}(\sigma_{1}\dots\sigma_{m})=A(\sigma_{1}\dots\sigma_{m}).$

For the second claim, it suffices to note that $A_{1},\dots,A_{d}$ can be
taken to be flip-flops when $A$ is counter-free, by Theorem 7.

Next we show the converse of the two claims. The converse of the first claim
holds immediately by the definition of cascade, which says that the function
it implements is the one implemented by the corresponding automaton. For the
converse of the second claim, consider a simple cascade
$C=(A_{1},\dots,A_{d})$. For every $i\in[1,d]$, the core semiautomaton $D_{i}$
of $A_{i}$ is a flip-flop. Also, for every $i\in[1,d-1]$ the output function
of $A_{i}$ is
$\theta_{i}(q_{i},\langle\sigma,q_{1},\dots,q_{i-1}\rangle)=q_{i}$. Thus, the
core semiautomaton of the automaton corresponding to $C$ is expressed by the
cascade product $D_{1}\ltimes\cdots\ltimes D_{d}$. Thus, by Theorem 7, cascade
$C$ is captured by a counter-free automaton. ∎

###  A.2 Proof of Theorem 3 (Cardinality and Sample Complexity of Finite
Classes of Automata)

See 3

###### Proof.

We bound the number of automata in the class
$\mathcal{A}(m,\Phi,\Delta,\Theta)$. Consider that each automaton in the class
is of the form

$A=\langle X^{a},J,\Pi,\phi,Q,\delta,q_{\mathrm{init}},\Gamma,\theta\rangle.$

To establish the cardinality of the class, it suffices to count the number of
distinct components of the tuple above. The input alphabet $X^{a}$ is fixed.
The number of possible sets of indices of $J\subseteq[1,a]$ is the cardinality
of the set $\left|\pi_{m}^{a}\right|=\left|\binom{a}{m}\right|$. The number of
input functions $\phi$ is $|\Phi|$. Each input function determines the
internal alphabet $\Pi$. Each semiautomaton
$\langle\Pi,Q,\delta,q_{\mathrm{init}}\rangle$ is from $\Delta$, and hence we
have at most $|\Delta|$. The number of output functions $\theta$ is
$|\Theta|$, and the output alphabet $\Gamma$ is determined by the output
function. The bound follows by taking the product of the sets of components
whose cardinality has been discussed above.

For the case where $\Delta$ is the set of all semiautomaton with $k$ letters
and $n$ states, we have $|\Delta|\leq n^{k\cdot n}$—assuming w.l.o.g. that
$Q=[1,n]$ and $q_{\mathrm{init}}=1$.

The sample complexity is immediate by taking the logarithm of the cardinality
bound established above. ∎

###  A.3 Proof of Theorem 4 (Cardinality and Sample Complexity of Finite
Classes of Automata Cascades)

Note that the theorem is restated by defining some of the quantities more
clearly.

Theorem 4. The cardinality of a class of automata cascades
$\mathcal{C}=\mathcal{A}_{1}\ltimes\cdots\ltimes\mathcal{A}_{d}$ where the
automata are from
$\mathcal{A}_{i}=\mathcal{A}(\Phi_{i},\Delta_{i},\Theta_{i};a_{i},m_{i})$ is
bounded as

$\left|\mathcal{C}\right|\leq\prod_{i=1}^{d}\left|\pi_{m_{i}}^{a_{i}}\right|\cdot\left|\Phi_{i}\right|\cdot\left|\Delta_{i}\right|\cdot\left|\Theta_{i}\right|,$

and its sample complexity is asymptotically bounded as

$S(\mathcal{C})\in
O\Big{(}d\cdot(\log\left|\pi_{m}^{a}\right|\,+\,\log\left|\Phi\right|\,+\,\log\left|\Delta\right|\,+\,\log\left|\Theta\right|)\Big{)},$

where dropping the indices denotes the maximum as follows:

$\displaystyle\pi_{m}^{a}$
$\displaystyle=\operatorname{arg\,max}_{\pi_{m_{i}}^{a_{i}}}|\pi_{m_{i}}^{a_{i}}|$
the class of projection functions with maximum cardinality,
$\displaystyle\Phi$
$\displaystyle=\operatorname{arg\,max}_{\Phi_{i}}|\Phi_{i}|$ the class of
input functions with maximum cardinality, $\displaystyle\Delta$
$\displaystyle=\operatorname{arg\,max}_{\Delta_{i}}|\Delta_{i}|$ the class of
semiautomata with maximum cardinality, $\displaystyle\Theta$
$\displaystyle=\operatorname{arg\,max}_{\Theta_{i}}|\Theta_{i}|$ the class of
output functions with maximum cardinality.

###### Proof.

We bound the number of cascades in the class
$\mathcal{C}=\mathcal{A}_{1}\ltimes\cdots\ltimes\mathcal{A}_{d}$. In order to
do so, we bound the cardinality of each class of automata
$\mathcal{A}_{i}=\mathcal{A}(\Phi_{i},\Delta_{i},\Theta_{i};a_{i},m_{i})$.
Thus, by the cardinality bound in Theorem 3, we have that

$\left|\mathcal{A}_{i}\right|\leq\left|\pi_{m_{i}}^{a_{i}}\right|\cdot\left|\Phi_{i}\right|\cdot\left|\Delta_{i}\right|\cdot\left|\Theta_{i}\right|.$

Thus, the bound on $\left|\mathcal{C}\right|$ is given by
$\prod_{i=1}^{d}\left|\mathcal{A}_{i}\right|$. Then, for the sample
complexity, we loosen the bound taking the maximum of each indexed quantity.
Namely,

$\displaystyle\left|\mathcal{C}\right|$
$\displaystyle\leq\prod_{i=1}^{d}\left|\mathcal{A}_{i}\right|\leq\prod_{i=1}^{d}\left|\pi_{m}^{a}\right|\cdot\left|\Phi\right|\cdot\left|\Delta\right|\cdot\left|\Theta\right|,$

where $\pi_{m}^{a},$ $\Phi,$ $\Delta,$ and $\Theta$ are defined in the
statement of the theorem. Then,

$\left|\mathcal{C}\right|\leq\left|\pi_{m}^{a}\right|^{d}\cdot\left|\Phi\right|^{d}\cdot\left|\Delta\right|^{d}\cdot\left|\Theta\right|^{d}.$

The sample complexity bound follows by taking the logarithm of the cardinality
bound established above. ∎

###  A.4 Further Details on the Growth and Sample Complexity

This section restates two claims from Section 7.3, providing details on the
way they are derived. The following Proposition 1 restates the upper bound on
the growth in terms of the dimension.

######  Proposition 1.

Let $\mathcal{F}$ be a class of functions from $X$ to $Y$. Then,

$G(\mathcal{F},\ell)\;\leq\;\sum_{i=0}^{\operatorname{dim}(\mathcal{F})}\binom{\ell}{i}\cdot(|Y|-1)^{i}\;\leq\;\sum_{i=0}^{\operatorname{dim}(\mathcal{F})}\binom{\ell}{i}\cdot|Y|^{i}\;\leq\;\left(e\cdot\ell\cdot|Y|\right)^{\operatorname{dim}(\mathcal{F})}.$

###### Proof.

The first inequality is Corollary 3 of (Haussler and Long 1995). We loosen it
by substituting $(|Y|-1)^{i}$ with $|Y|^{i}$ and then applying the well-known
bound on the partial sum of binomials $\sum_{i=0}^{d}\binom{m}{i}\leq(e\cdot
m)^{d}$ to derive the last inequality. ∎

The following Proposition 2 restates the asymptotic bound on the sample
complexity in terms of the dimension.

######  Proposition 2.

The following asymptotic bound on the sample complexity holds true:

$S(\mathcal{F},\epsilon,\eta)\in
O\left((\operatorname{dim}(\mathcal{F})\cdot\log|Y|-\log\eta)/\epsilon^{2}\right).$

###### Proof.

By Point 2 of Theorem 19.3 of (Shalev-Shwartz and Ben-David 2014), the
proposition holds with the _Natarajan dimension_ of $\mathcal{F}$ in place of
$\operatorname{dim}(\mathcal{F})$. Then the proposition follows immediately
since $\operatorname{dim}(\mathcal{F})$ is an upper bound on the Natarajan
dimension, by Equations (24) and (26) of (Haussler and Long 1995). ∎

###  A.5 Basic Propositions

In this section we state and prove some basic propositions that we use in the
next sections of the appendix, where we prove the results for Section 7.4.

The next Proposition 3 describes a relationship between the growth of
$\mathcal{F}$ and the growth of its binarisation $\mathcal{F}_{\mathrm{bin}}$.

######  Proposition 3.

Let $\mathcal{F}$ be a class of functions. Then,
$G(\mathcal{F}_{\mathrm{bin}},\ell)\leq G(\mathcal{F},\ell)$.

###### Proof.

Let $Z_{\ell}=\langle x_{1},y_{1}\rangle,\dots,\langle
x_{\ell},y_{\ell}\rangle$ and let $X_{\ell}=x_{1},\dots,x_{\ell}$. The
proposition is immediate by observing that every tuple in

$\mathcal{F}(X_{\ell})=\\{\langle f(x_{1}),\dots,f(x_{\ell})\rangle\mid
f\in\mathcal{F}\\}$

corresponds to at most one tuple in

$\mathcal{F}_{\mathrm{bin}}(Z_{\ell})=\\{\langle\mathbf{1}[y_{1}\\!=\\!f(x_{1})],\dots,\mathbf{1}[y_{\ell}\\!=\\!f(x_{\ell})]\rangle\mid
f\in\mathcal{F}\\}.$

∎

The next Propositions 4 and 5 provide bounds on the growth for composition and
cross product of functions. They are well-known. For instance, they are left
as an exercise in the book (Shalev-Shwartz and Ben-David 2014). However, we
were not able to find a peer-reviewed reference for the proofs. We report
proofs based on the lecture notes (Kakade and Tewari 2008).

######  Proposition 4.

Let $\mathcal{F}_{1}:X\to W$, and let $\mathcal{F}_{2}:W\to Y$. Then,
$G(\mathcal{F}_{1}\circ\mathcal{F}_{2},\ell)\leq G(\mathcal{F}_{1},\ell)\cdot
G(\mathcal{F}_{2},\ell).$

###### Proof.

Let $X_{\ell}=x_{1},\dots,x_{\ell}$ be a sequence of $\ell$ elements from $X$.
Let $\mathcal{F}=\mathcal{F}_{1}\circ\mathcal{F}_{2}$. We have

$\displaystyle\mathcal{F}(X_{\ell})$ $\displaystyle=\\{\langle
f_{2}(f_{1}(x_{1})),\dots,f_{2}(f_{1}(x_{\ell}))\rangle\mid
f_{1}\in\mathcal{F}_{1},\,f_{2}\in\mathcal{F}_{2}\\}$
$\displaystyle=\bigcup_{U_{\ell}\in\mathcal{F}_{1}(X_{\ell})}\\{\langle
f_{2}(u_{1}),\dots,f_{2}(u_{\ell})\rangle\mid f_{2}\in\mathcal{F}_{2}\\},$

and therefore,

$\displaystyle N(\mathcal{F},X_{\ell})=|\mathcal{F}(X_{\ell})|$
$\displaystyle\leq\sum_{U_{\ell}\in\mathcal{F}_{1}(X_{\ell})}\left|\\{\langle
f_{2}(u_{1}),\dots,f_{2}(u_{\ell})\rangle\mid
f_{2}\in\mathcal{F}_{2}\\}\right|$
$\displaystyle\leq\sum_{U_{\ell}\in\mathcal{F}_{1}(X_{\ell})}N(\mathcal{F}_{2},U_{\ell})$
$\displaystyle\leq\sum_{U_{\ell}\in\mathcal{F}_{1}(X_{\ell})}G(\mathcal{F}_{2},\ell)$
$\displaystyle=N(\mathcal{F}_{1},X_{\ell})\cdot G(\mathcal{F}_{2},\ell)$
$\displaystyle\leq G(\mathcal{F}_{1},\ell)\cdot G(\mathcal{F}_{2},\ell).$

Since $X_{\ell}$ is arbitrary, this concludes the proof. ∎

######  Proposition 5.

Let $\mathcal{F}_{1}:X\to Y$ and let $\mathcal{F}_{2}:X\to Z$. Then,
$G(\mathcal{F}_{1}\times\mathcal{F}_{2},\ell)\leq G(\mathcal{F}_{1},\ell)\cdot
G(\mathcal{F}_{2},\ell)$.

###### Proof.

$G(\mathcal{F}_{1}\times\mathcal{F}_{2},\ell)=\sup_{X_{\ell}}N(\mathcal{F}_{1}\times\mathcal{F}_{2},X_{\ell})=\sup_{X_{\ell}}\big{[}N(\mathcal{F}_{1},X_{\ell})\cdot
N(\mathcal{F}_{2},X_{\ell})\big{]}\leq G(\mathcal{F}_{1},\ell)\cdot
G(\mathcal{F}_{2},\ell).$

∎

The next Propositions 6–8 describe properties of the growth with respect to
string functions.

######  Proposition 6.

Let $\mathcal{F}$ be a class of functions $\Sigma\to\Gamma$. Then,
$G(\mathcal{F}^{*},\ell)\leq G(\mathcal{F},\ell)$.

###### Proof.

Let $X_{\ell}=x_{1},\dots,x_{\ell}$ be a sequence of strings over $\Sigma$,
and let $\sigma_{i}$ be the last letter of $x_{i}$. Since
$f^{*}(x_{i})=f(\sigma_{i})$ for every function $f\in\mathcal{F}$, we have
that
$\mathcal{F}^{*}(X_{\ell})=\mathcal{F}^{*}(\sigma_{1},\dots,\sigma_{\ell})=\mathcal{F}(\sigma_{1},\dots,\sigma_{\ell})$.
Therefore,

$N(\mathcal{F}^{*},X_{\ell})=|\mathcal{F}^{*}(X_{\ell})|=|\mathcal{F}(\sigma_{1},\dots,\sigma_{\ell})|=N(\mathcal{F},\sigma_{1},\dots,\sigma_{\ell})\leq
G(\mathcal{F},\ell).$

Since $X_{\ell}$ is arbitrary, this concludes the proof. ∎

######  Proposition 7.

Let $\mathcal{F}_{1}:\Sigma^{*}\to Y$ and let $\mathcal{F}_{2}:\Sigma^{*}\to
Z$. Then,
$G(\overline{\mathcal{F}_{1}\times\mathcal{F}_{2}},\ell)=G(\overline{\mathcal{F}_{1}}\times\overline{\mathcal{F}_{2}},\ell)$.

###### Proof.

Consider a function $f_{1}\in\mathcal{F}_{1}$, a function
$f_{2}\in\mathcal{F}_{2}$, and a sequence $X_{\ell}=x_{1},\dots,x_{\ell}$ of
strings over $\Sigma$. We have that

$(\overline{f_{1}\times f_{2}})(X_{\ell})=(\overline{f_{1}\times
f_{2}})(x_{1}),\dots,(\overline{f_{1}\times f_{2}})(x_{\ell}),$

and

$(\overline{f_{1}}\times\overline{f_{2}})(X_{\ell})=(\overline{f_{1}}\times\overline{f_{2}})(x_{1}),\dots,(\overline{f_{1}}\times\overline{f_{2}})(x_{\ell}).$

Now, consider $x_{i}=\sigma_{1}\dots\sigma_{s}$. We have

$(\overline{f_{1}\times f_{2}})(x_{i})=(f_{1}\times
f_{2})(\sigma_{1})\dots(f_{1}\times f_{2})(\sigma_{1}\dots\sigma_{s})=\langle
f_{1}(\sigma_{1}),f_{2}(\sigma_{1})\rangle\dots\langle
f_{1}(\sigma_{1}\dots\sigma_{s}),f_{2}(\sigma_{1}\dots\sigma_{s})\rangle,$

and

$(\overline{f_{1}}\times\overline{f_{2}})(x_{i})=\langle\overline{f_{1}}(x_{i}),\overline{f_{2}}(x_{i})\rangle=\langle
f_{1}(\sigma_{1})\dots f_{1}(\sigma_{1}\dots\sigma_{s}),f_{2}(\sigma_{1})\dots
f_{2}(\sigma_{1}\dots\sigma_{s})\rangle.$

Note that the output of $(\overline{f_{1}\times f_{2}})(x_{i})$ and
$(\overline{f_{1}}\times\overline{f_{2}})(x_{i})$ contain the same occurrences
of letters, arranged differently. Hence, the same holds for
$(\overline{f_{1}\times f_{2}})(X_{\ell})$ and
$(\overline{f_{1}}\times\overline{f_{2}})(X_{\ell})$. Therefore,

$|\\{(\overline{f_{1}\times f_{2}})(X_{\ell})\mid
f_{1}\in\mathcal{F}_{1},\,f_{2}\in\mathcal{F}_{2}\\}|=|\\{(\overline{f_{1}}\times\overline{f_{2}})(X_{\ell})\mid
f_{1}\in\mathcal{F}_{1},\,f_{2}\in\mathcal{F}_{2}\\}|,$

and hence

$N(\overline{\mathcal{F}_{1}\times\mathcal{F}_{2}},X_{\ell})=N(\overline{\mathcal{F}_{1}}\times\overline{\mathcal{F}_{2}},X_{\ell}).$

Since $X_{\ell}$ is arbitrary, this concludes the proof. ∎

######  Proposition 8.

Let $\mathcal{F}$ be a class of functions $\Sigma^{*}\to\Gamma$. Then,
$G(\overline{\mathcal{F}},\ell)\leq G(\mathcal{F},\ell\cdot M)$ where $M$ is
the maximum length of a string.

###### Proof.

Consider a string $x=\sigma_{1}\dots\sigma_{s}$ with $\sigma_{i}\in\Sigma$.
Consider the sequence of non-empty prefixes of $x$,

$x^{\mathrm{p}}=\sigma_{1},\,\sigma_{1}\sigma_{2},\,\dots,\,\sigma_{1}\sigma_{2}\dots\sigma_{s}.$

For every $f\in\mathcal{F}$, the following two identities hold:

$\displaystyle\overline{f}(x)$ $\displaystyle=f(\sigma_{1})\dots
f(\sigma_{1}\dots\sigma_{s}),$ (1) $\displaystyle f(x^{\mathrm{p}})$
$\displaystyle=f(\sigma_{1}),\dots,f(\sigma_{1}\dots\sigma_{s}).$ (2)

Now, let $X_{\ell}=x_{1},\dots,x_{\ell}$ be a sequence of $\ell$ strings over
$\Sigma$, and let
$X^{\mathrm{p}}_{\ell}=x_{1}^{\mathrm{p}},\dots,x_{\ell}^{\mathrm{p}}$ where
$x_{i}^{\mathrm{p}}$ is the sequence of non-empty prefixes of $x_{i}$ defined
as above. Then, the identities (1) and (2) imply
$N(\overline{\mathcal{F}},X_{\ell})=N(\mathcal{F},X^{\mathrm{p}}_{\ell})$.
Thus, $N(\mathcal{F},X^{\mathrm{p}}_{\ell})\leq G(\mathcal{F},\ell\cdot M)$,
since $X^{\mathrm{p}}_{\ell}$ is a sequence of length at most $\ell\cdot M$,
and hence $N(\overline{\mathcal{F}},X^{\mathrm{p}}_{\ell})\leq
G(\mathcal{F},\ell\cdot M)$. Since $X_{\ell}$ is arbitrary, we conclude that
$G(\overline{\mathcal{F}},\ell)\leq G(\mathcal{F},\ell\cdot M)$. ∎

The next Propositions 9–11 provide some algebraic identities for functions
expressed in terms of composition, cross product, and our constructors
introduced in Definition 6.

######  Proposition 9.

Let $f_{1}:\Sigma^{*}\to\Gamma$, and let $f_{2}:\Gamma^{*}\to Y$. Then,
$\overline{\overline{f_{1}}\circ
f_{2}}=\overline{f_{1}}\circ\overline{f_{2}}$.

###### Proof.

$\displaystyle(\overline{\overline{f_{1}}\circ
f_{2}})(\sigma_{1}\dots\sigma_{n})$ $\displaystyle=(\overline{f_{1}}\circ
f_{2})(\sigma_{1})\dots(\overline{f_{1}}\circ
f_{2})(\sigma_{1}\dots\sigma_{n})$
$\displaystyle=f_{2}\big{(}\overline{f_{1}}(\sigma_{1})\big{)}\dots
f_{2}\big{(}\overline{f_{1}}(\sigma_{1}\dots\sigma_{n})\big{)}$
$\displaystyle=f_{2}\big{(}f_{1}(\sigma_{1})\big{)}\dots
f_{2}\big{(}f_{1}(\sigma_{1})\dots f_{1}(\sigma_{1}\dots\sigma_{n})\big{)}$
$\displaystyle=\overline{f_{2}}\big{(}f_{1}(\sigma_{1})\dots
f_{1}(\sigma_{1}\dots\sigma_{n})\big{)}$
$\displaystyle=\overline{f_{2}}\big{(}\overline{f_{1}}(\sigma_{1}\dots\sigma_{n})\big{)}$
$\displaystyle=(\overline{f_{1}}\circ\overline{f_{2}})(\sigma_{1}\dots\sigma_{n}).$

∎

######  Proposition 10.

Let $f_{1}:\Sigma^{*}\to\Gamma$, and let $f_{2}:\Gamma\to Y$. Then,
$\overline{f_{1}\circ f_{2}}=\overline{f_{1}}\circ\overline{f_{2}^{*}}$.

###### Proof.

$\displaystyle(\overline{f_{1}\circ f_{2}})(\sigma_{1}\dots\sigma_{n})$
$\displaystyle=(f_{1}\circ f_{2})(\sigma_{1})\dots(f_{1}\circ
f_{2})(\sigma_{1}\dots\sigma_{n})$
$\displaystyle=f_{2}\big{(}f_{1}(\sigma_{1})\big{)}\dots
f_{2}\big{(}f_{1}(\sigma_{1}\dots\sigma_{n})\big{)}$
$\displaystyle=f^{*}_{2}\big{(}f_{1}(\sigma_{1})\big{)}\dots
f^{*}_{2}\big{(}f_{1}(\sigma_{1}\dots\sigma_{n})\big{)}$
$\displaystyle=f^{*}_{2}\big{(}f_{1}(\sigma_{1})\big{)}\dots
f^{*}_{2}\big{(}f_{1}(\sigma_{1})\dots
f_{1}(\sigma_{1}\dots\sigma_{n})\big{)}$
$\displaystyle=\overline{f^{*}_{2}}\big{(}f_{1}(\sigma_{1})\dots
f_{1}(\sigma_{1}\dots\sigma_{n})\big{)}$
$\displaystyle=\overline{f_{2}^{*}}\big{(}\overline{f_{1}}(\sigma_{1}\dots\sigma_{n})\big{)}$
$\displaystyle=(\overline{f_{1}}\circ\overline{f^{*}_{2}})(\sigma_{1}\dots\sigma_{n}).$

∎

######  Proposition 11 (Left-distributivity of function _composition_ over
_cross product_).

Consider three functions $f_{1}:X\to Y$, $f_{2}:Y\to Z$, and $f_{3}:Y\to W$.
Then, $(f_{1}\circ f_{2})\times(f_{1}\circ f_{3})=f_{1}\circ(f_{2}\times
f_{3})$.

###### Proof.

We have

$\displaystyle[(f_{1}\circ f_{2})\times(f_{1}\circ f_{3})](x)$
$\displaystyle=\big{\langle}(f_{1}\circ f_{2})(x),(f_{1}\circ
f_{3})(x)\big{\rangle}$
$\displaystyle=\big{\langle}f_{2}(f_{1}(x)),f_{3}(f_{1}(x))\big{\rangle}$
$\displaystyle=(f_{2}\times f_{3})(f_{1}(x))$
$\displaystyle=(f_{1}\circ(f_{2}\times f_{3}))(x).$

This concludes the proof. ∎

###  A.6 Proof of Lemma 1 (Functional Description of an Automaton)

See 1

###### Proof.

The function implemented by $A$ is the one implemented by the induced
automaton
$A^{\prime}=\langle\Sigma,Q,\delta_{J,\phi},q_{\mathrm{init}},\Gamma,\theta_{J}\rangle$,
where $\delta_{J,\phi}(q,\sigma)=\delta(q,\phi(\pi_{J}(\sigma)))$, and the
output function is $\theta_{J}(q,\sigma)=\theta(q,\pi_{J}(\sigma))$. In turn,
the function implemented by $A^{\prime}$ is
$A^{\prime}(\sigma_{1}\dots\sigma_{m})=\theta_{J}(\delta_{J,\phi}(q_{\mathrm{init}},\sigma_{1}\dots\sigma_{m-1}),\sigma_{m})$.
Thus, the function implemented by $A$ is

$\displaystyle A(\sigma_{1}\dots\sigma_{m})$
$\displaystyle=\theta_{J}(\delta_{J,\phi}(q_{\mathrm{init}},\sigma_{1}\dots\sigma_{m-1}),\sigma_{m}).$
(3)

Observe that

$\displaystyle\phi(\pi_{J}(\sigma_{1}))\dots\phi(\pi_{J}(\sigma_{m}))=\overline{\phi^{*}}(\pi_{J}(\sigma_{1})\dots\pi_{J}(\sigma_{m}))=\overline{\phi^{*}}(\overline{\pi_{J}^{*}}(\sigma_{1}\dots\sigma_{m})).$

Thus,

$\displaystyle\delta_{J,\phi}(q_{\mathrm{init}},\sigma_{1}\dots\sigma_{m})=\delta(q_{\mathrm{init}},\overline{\phi^{*}}(\overline{\pi_{J}^{*}}(\sigma_{1}\dots\sigma_{m})))=D(\overline{\phi^{*}}(\overline{\pi_{J}^{*}}(\sigma_{1}\dots\sigma_{m}))).$

Now, going back to (3), we have

$\displaystyle A(\sigma_{1}\dots\sigma_{m})$
$\displaystyle=\theta_{J}\big{(}\delta_{J,\phi}(q_{\mathrm{init}},\sigma_{1}\dots\sigma_{m-1}),\sigma_{m}\big{)}$
$\displaystyle=\theta_{J}\big{(}D(\overline{\phi^{*}}(\overline{\pi_{J}^{*}}(\sigma_{1}\dots\sigma_{m-1}))),\sigma_{m}\big{)}$
$\displaystyle=\theta_{J}\big{(}D^{\triangleleft}(\overline{\phi^{*}}(\overline{\pi_{J}^{*}}(\sigma_{1}\dots\sigma_{m}))),\sigma_{m}\big{)}$
$\displaystyle=\theta\big{(}D^{\triangleleft}(\overline{\phi^{*}}(\overline{\pi_{J}^{*}}(\sigma_{1}\dots\sigma_{m}))),\pi_{J}(\sigma_{m})\big{)}$
$\displaystyle=\theta\big{(}D^{\triangleleft}(\overline{\phi^{*}}(\overline{\pi_{J}^{*}}(\sigma_{1}\dots\sigma_{m}))),\pi_{J}^{*}(\sigma_{1}\dots\sigma_{m})\big{)}$
$\displaystyle=\theta\big{(}D^{\triangleleft}(\overline{\phi^{*}}(\overline{\pi_{J}^{*}}(\sigma_{1}\dots\sigma_{m}))),I^{*}(\overline{\pi_{J}^{*}}(\sigma_{1}\dots\sigma_{m}))\big{)}$
$\displaystyle=\theta\big{(}D^{\triangleleft}((\overline{\pi_{J}^{*}}\circ\overline{\phi^{*}})(\sigma_{1}\dots\sigma_{m})),(\overline{\pi_{J}^{*}}\circ
I^{*})(\sigma_{1}\dots\sigma_{m})\big{)}$
$\displaystyle=\theta\big{(}(\overline{\pi_{J}^{*}}\circ\overline{\phi^{*}}\circ
D^{\triangleleft})(\sigma_{1}\dots\sigma_{m}),(\overline{\pi_{J}^{*}}\circ
I^{*})(\sigma_{1}\dots\sigma_{m})\big{)}$
$\displaystyle=\theta\big{(}((\overline{\pi_{J}^{*}}\circ\overline{\phi^{*}}\circ
D^{\triangleleft})\times(\overline{\pi_{J}^{*}}\circ
I^{*}))(\sigma_{1}\dots\sigma_{m})\big{)}$
$\displaystyle=\big{(}\big{(}(\overline{\pi_{J}^{*}}\circ\overline{\phi^{*}}\circ
D^{\triangleleft})\times(\overline{\pi_{J}^{*}}\circ
I^{*})\big{)}\circ\theta\big{)}(\sigma_{1}\dots\sigma_{m})$
$\displaystyle=\big{(}\overline{\pi_{J}^{*}}\circ\big{(}(\overline{\phi^{*}}\circ
D^{\triangleleft})\times
I^{*}\big{)}\circ\theta\big{)}(\sigma_{1}\dots\sigma_{m}).$

The last equality is by Propostion 11. This concludes the proof. ∎

###  A.7 Proof of Theorem 5 (Growth and Sample Complexity of Infinite Classes
of Automata)

We prove Theorem 5 in two lemmas. First, we prove the bound on the growth in
Lemma 3, then we prove the bound on the dimension in Lemma 4. Then, the
asymptotic bound on the sample complexity follows immediately by Propostion 2.

######  Lemma 3.

Let $\mathcal{A}$ be a class of automata
$\mathcal{A}(\Phi,\Delta,\Theta;a,m,\Pi,\Gamma)$, and let $M$ be the maximum
length of a string. The growth of $\mathcal{A}$ is bounded as:

$G(\mathcal{A},\ell)\leq\left|\pi^{a}_{m}\right|\cdot\left|\Delta\right|\cdot
G(\Phi,\ell\cdot M)\cdot G(\Theta,\ell).$

###### Proof.

By Lemma 1 the class of functions implemented by $\mathcal{A}$ can be
expressed as

$\mathcal{A}=\overline{(\pi_{m}^{a})^{*}}\circ\left((\overline{\Phi^{*}}\circ\Delta^{\triangleleft})\times
I^{*}\right)\circ\Theta.$

Then,

$\displaystyle G(\mathcal{A},\ell)$
$\displaystyle=G\left(\overline{(\pi_{m}^{a})^{*}}\circ\left((\overline{\Phi^{*}}\circ\Delta^{\triangleleft})\times
I^{*}\right)\circ\Theta,\ell\right)$ by Lemma 1, $\displaystyle\leq
G\left(\overline{(\pi_{m}^{a})^{*}}\circ\left((\overline{\Phi^{*}}\circ\Delta^{\triangleleft})\times
I^{*}\right),\ell\right)\cdot G(\Theta,\ell)$ by Proposition 4,
$\displaystyle\leq G\left(\overline{(\pi_{m}^{a})^{*}},\ell\right)\cdot
G\left((\overline{\Phi^{*}}\circ\Delta^{\triangleleft})\times
I^{*},\ell\right)\cdot G(\Theta,\ell)$ by Proposition 4,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot
G\left((\overline{\Phi^{*}}\circ\Delta^{\triangleleft})\times
I^{*},\ell\right)\cdot G(\Theta,\ell)$ since $\pi_{m}^{a}$ is finite,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot
G\left(\overline{\Phi^{*}}\circ\Delta^{\triangleleft},\ell\right)\cdot
G\left(I^{*},\ell\right)\cdot G(\Theta,\ell)$ by Proposition 5,
$\displaystyle=\left|\pi_{m}^{a}\right|\cdot
G\left(\overline{\Phi^{*}}\circ\Delta^{\triangleleft},\ell\right)\cdot
G(\Theta,\ell)$ since $I^{*}$ is a single function,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot
G\left(\overline{\Phi^{*}},\ell\right)\cdot
G\left(\Delta^{\triangleleft},\ell\right)\cdot G\left(\Theta,\ell\right)$ by
Proposition 4,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot
G\left(\overline{\Phi^{*}},\ell\right)\cdot G\left(\Theta,\ell\right)$ since
$\Delta$ is finite,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot
G(\Phi^{*},\ell\cdot M)\cdot G(\Theta,\ell)$ by Proposition 8,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot
G(\Phi,\ell\cdot M)\cdot G(\Theta,\ell)$ by Proposition 6.

This proves the lemma. ∎

######  Lemma 4.

Let $\mathcal{A}$ be a class of automata
$\mathcal{A}(\Phi,\Delta,\Theta;a,m,\Pi,\Gamma)$, let $M$ be the maximum
length of a string, and let
$w=\log\left|\pi_{m}^{a}\right|+\log\left|\Delta\right|+\operatorname{dim}(\Phi)+\operatorname{dim}(\Theta)\geq
2$. The dimension of $\mathcal{A}$ is bounded as:

$\displaystyle\operatorname{dim}(\mathcal{A})$ $\displaystyle\leq 2\cdot
w\cdot\log(w\cdot e\cdot M\cdot|\Pi|\cdot|\Gamma|).$

###### Proof.

By Lemma 3 the upper bound on the growth $G(\mathcal{A},\ell)$ is

$G(\mathcal{A},\ell)\leq\left|\pi^{a}_{m}\right|\cdot\left|\Delta\right|\cdot
G(\Phi,\ell\cdot M)\cdot G(\Theta,\ell).$

Applying Proposition 1 to $G(\Phi,\ell\cdot M)$ and $G(\Theta,\ell)$ we
obtain,

$G(\mathcal{A},\ell)\leq\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot\left(e\cdot\ell\cdot
M\cdot|\Pi|\right)^{h}\cdot\left(e\cdot\ell\cdot|\Gamma|\right)^{g}.$

We loosen the bound on $G(\mathcal{A},\ell)$ by collecting the factors with an
exponent,

$G(\mathcal{A},\ell)\leq\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot\left(\ell\cdot
e\cdot M\cdot|\Pi|\cdot|\Gamma|\right)^{h+g}.$

Next we show the claimed upper bound on the dimension of $\mathcal{A}$. By the
definition of dimension, in order to show that a number $\ell$ is an upper
bound on the dimension of $\mathcal{A}$, it suffices to show that
$G(\mathcal{A}_{\mathrm{bin}},\ell)<2^{\ell}$—note that
$G(\mathcal{A}_{\mathrm{bin}},\ell)=G(\mathcal{A},\ell)$ when the output
alphabet has cardinality two. Then, since
$G(\mathcal{A}_{\mathrm{bin}},\ell)\leq G(\mathcal{A},\ell)$ by Proposition 3,
a number $\ell$ satisfies $G(\mathcal{A}_{\mathrm{bin}},\ell)<2^{\ell}$ if it
satisfies $G(\mathcal{A},\ell)<2^{\ell}$, and in turn if it satisfies

$\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot\left(\ell\cdot e\cdot
M\cdot|\Pi|\cdot|\Gamma|\right)^{h+g}<2^{\ell}.$

We show that the former inequality is satisfied for $\ell=2\cdot
w\cdot\log(w\cdot e\cdot M\cdot|\Pi|\cdot|\Gamma|)=2\cdot w\cdot\log(w\cdot
e\cdot C)$, where we introduce $C=M\cdot|\Pi|\cdot|\Gamma|$ for brevity. We
keep proceeding by sufficient conditions. Specifically, at each step, either
we replace the r.h.s. with a smaller expression, we simplify a common term
between the two sides, or we just rewrite an expression in an equivalent form.

$\displaystyle\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot\left(\ell\cdot
e\cdot M\cdot|\Pi|\cdot|\Gamma|\right)^{h+g}$ $\displaystyle<2^{\ell}$
$\displaystyle\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot\left(\ell\cdot
e\cdot C\right)^{h+g}$ $\displaystyle<2^{\ell}$
$\displaystyle\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot\big{(}2\cdot
w\cdot\log(w\cdot e\cdot C)\cdot e\cdot C\big{)}^{h+g}$
$\displaystyle<2^{2\cdot w\cdot\log(w\cdot e\cdot C)},$
$\displaystyle\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot\big{(}2\cdot
w\cdot\log(w\cdot e\cdot C)\cdot e\cdot C\big{)}^{h+g}$ $\displaystyle<(w\cdot
e\cdot C)^{2\cdot(h+g)}\cdot(w\cdot e\cdot
C)^{2\cdot(\ln(\left|\Delta\right|\cdot\left|\pi_{m}^{a}\right|)/\ln 2))},$
$\displaystyle\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot\big{(}2\cdot
w\cdot\log(w\cdot e\cdot C)\cdot e\cdot C\big{)}^{h+g}$ $\displaystyle<(w\cdot
e\cdot C)^{2\cdot(h+g)}\cdot(w\cdot e\cdot
C)^{2\cdot(\ln(\left|\Delta\right|\cdot\left|\pi_{m}^{a}\right|))},$
$\displaystyle\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot\big{(}2\cdot
w\cdot\log(w\cdot e\cdot C)\cdot e\cdot C\big{)}^{h+g}$ $\displaystyle<(w\cdot
e\cdot C)^{2\cdot(h+g)}\cdot\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|,$
$\displaystyle\big{(}2\cdot w\cdot\log(w\cdot e\cdot C)\cdot e\cdot
C\big{)}^{h+g}$ $\displaystyle<(w\cdot e\cdot C)^{2\cdot(h+g)}$ $\displaystyle
2\cdot\log(w\cdot e\cdot C)^{h+g}$ $\displaystyle<(w\cdot e\cdot C)^{h+g}$
$\displaystyle 1$ $\displaystyle<\bigg{(}\frac{(w\cdot e\cdot
C)}{2\cdot\log(w\cdot e\cdot C)}\bigg{)}^{h+g}$

The term on the r.h.s. is strictly greater than $1$ whenever $w\geq 2$,
considering that $C\geq 1$. This proves the lemma. ∎

###  A.8 Proof of Lemma 2 (Functional Description of an Automata Cascade)

See 2

###### Proof.

Let $C_{d}=A_{1}\ltimes\cdots\ltimes A_{d}=(A_{1},\dots,A_{d})$. We show by
induction on $d\geq 1$ that

$\overline{(I^{*}\times A_{1})}\circ\dots\circ\overline{(I^{*}\times
A_{d-1})}\circ A_{d}.$

considering $C_{1}=A_{1}$ as the base case, which holds trivially. In the
inductive case, $d\geq 2$, and we assume that the function implemented by the
cascade $C_{d-1}=A_{1}\ltimes\cdots\ltimes A_{d-1}$ can be expressed as

$\overline{(I^{*}\times A_{1})}\circ\dots\circ\overline{(I^{*}\times
A_{d-2})}\circ A_{d-1}.$

From the definition of cascade, at each step, the input to component $A_{d}$
consists of the input to the component $A_{d-1}$ together with the output of
$A_{d-1}$. Over an execution, the sequence of such inputs to $A_{d}$ is the
function

$\overline{(I^{*}\times A_{1})}\circ\dots\circ\overline{(I^{*}\times
A_{d-2})}\circ(\overline{I^{*}\times A_{d-1}}).$

Then, the overall output of the casacade is returned by $A_{d}$ applied to
such an input string, and hence the function of $C_{d}$ is

$\overline{(I^{*}\times A_{1})}\circ\dots\circ\overline{(I^{*}\times
A_{d-2})}\circ(\overline{I^{*}\times A_{d-1}})\circ A_{d}.$

This concludes the proof. ∎

###  A.9 Proof of Theorem 6 (Growth and Sample Complexity of Infinite Classes
of Automata Cascades)

We prove Theorem 6 in two lemmas. First, we prove the bound on the growth of
cascades in Lemma 5, then we prove the bound on the dimension of cascades in
Lemma 6. Then, the asymptotic bound on the sample complexity follows
immediately by Propostion 2.

######  Lemma 5.

Let $\mathcal{C}$ be a class
$\mathcal{C}=\mathcal{A}_{1}\ltimes\dots\ltimes\mathcal{A}_{d}$ of cascades of
automata
$\mathcal{A}_{i}=\mathcal{A}(\Phi_{i},\Delta_{i},\Theta_{i};a_{i},m_{i},\Pi_{i},\Gamma_{i})$,
and let $M$ be the maximum length of a string. The growth of $\mathcal{C}$ is
bounded as:

$G(\mathcal{C},\ell)\leq\prod_{i=1}^{d}\left|\pi_{m_{i}}^{a_{i}}\right|\cdot\left|\Delta_{i}\right|\cdot
G(\Phi_{i},\ell\cdot M)\cdot G(\Theta_{i},\ell\cdot M).$

###### Proof.

By Lemma 2 the class of functions implemented by $\mathcal{C}$ can be
expressed as,

$\mathcal{C}=\overline{(I^{*}\times\mathcal{A}_{1})}\circ\dots\circ\overline{(I^{*}\times\mathcal{A}_{d-1})}\circ
A_{d}.$

Then,

$\displaystyle G(\mathcal{C},\ell)$
$\displaystyle=G\left(\overline{(I^{*}\times\mathcal{A}_{1})}\circ\dots\circ\overline{(I^{*}\times\mathcal{A}_{d-1})}\circ
A_{d},\ell\right)$ by Lemma 2, $\displaystyle\leq
G(\mathcal{A}_{d},\ell)\cdot\prod_{i=1}^{d-1}G(\overline{I^{*}\times\mathcal{A}_{i}},\ell)$
by Proposition 4, $\displaystyle\leq
G(\mathcal{A}_{d},\ell)\cdot\prod_{i=1}^{d-1}G(\overline{I^{*}},\ell)\cdot
G(\overline{\mathcal{A}_{i}},\ell)$ by Proposition 5 and 7,
$\displaystyle=G(\mathcal{A}_{d},\ell)\cdot\prod_{i=1}^{d-1}G(\overline{\mathcal{A}_{i}},\ell)$
since $I^{*}$ is singleton,

Next we derive an upper bound on $G(\overline{\mathcal{A}},\ell)$ for an
arbitrary class $\mathcal{A}=\mathcal{A}(\Phi,\Delta,\Theta;a,m)$.

$\displaystyle G(\overline{\mathcal{A}},\ell)$
$\displaystyle=G\left(\overline{\overline{(\pi_{m}^{a})^{*}}\circ\left((\overline{\Phi^{*}}\circ\Delta^{\triangleleft})\times
I^{*}\right)\circ\Theta},\ell\right)$ by Lemma 1, $\displaystyle\leq
G\left(\overline{\overline{(\pi_{m}^{a})^{*}}\circ\left((\overline{\Phi^{*}}\circ\Delta^{\triangleleft})\times
I^{*}\right)},\ell\right)\cdot G\left(\overline{\Theta^{*}},\ell\right)$ by
Proposition 10 and 4, $\displaystyle\leq
G\left(\overline{(\pi_{m}^{a})^{*}}\circ\big{(}\overline{(\overline{\Phi^{*}}\circ\Delta^{\triangleleft})\times
I^{*}}\big{)},\ell\right)\cdot G\left(\overline{\Theta^{*}},\ell\right)$ by
Proposition 9, $\displaystyle\leq
G\left(\overline{(\pi_{m}^{a})^{*}},\ell\right)\cdot
G\left(\overline{(\overline{\Phi^{*}}\circ\Delta^{\triangleleft})\times
I^{*}},\ell\right)\cdot G\left(\overline{\Theta^{*}},\ell\right)$ by
Proposition 4, $\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot
G\left(\overline{(\overline{\Phi^{*}}\circ\Delta^{\triangleleft})\times
I^{*}},\ell\right)\cdot G\left(\overline{\Theta^{*}},\ell\right)$ since
$\pi_{m}^{a}$ is finite, $\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot
G\left(\overline{(\overline{\Phi^{*}}\circ\Delta^{\triangleleft})}\times\overline{I^{*}},\ell\right)\cdot
G\left(\overline{\Theta^{*}},\ell\right)$ by Proposition 7,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot
G\left(\overline{(\overline{\Phi^{*}}\circ\Delta^{\triangleleft})},\ell\right)\cdot
G\left(\overline{I^{*}},\ell\right)\cdot
G\left(\overline{\Theta^{*}},\ell\right)$ by Proposition 5,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot
G\left(\overline{(\overline{\Phi^{*}}\circ\Delta^{\triangleleft})},\ell\right)\cdot
G\left(\overline{\Theta^{*}},\ell\right)$ since $I^{*}$ is a single function,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot
G\left(\overline{\Phi^{*}}\circ\overline{\Delta^{\triangleleft}},\ell\right)\cdot
G\left(\overline{\Theta^{*}},\ell\right)$ by Proposition 9,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot
G\left(\overline{\Phi^{*}},\ell\right)\cdot
G\left(\overline{\Delta^{\triangleleft}},\ell\right)\cdot
G\left(\overline{\Theta^{*}},\ell\right)$ by Proposition 4,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot
G\left(\overline{\Phi^{*}},\ell\right)\cdot
G\left(\overline{\Theta^{*}},\ell\right)$ since $\Delta$ is a finite class,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot
G\left(\Phi^{*},\ell\cdot M\right)\cdot G\left(\Theta^{*},\ell\cdot M\right)$
by Proposition 8,
$\displaystyle\leq\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\cdot
G\left(\Phi,\ell\cdot M\right)\cdot G\left(\Theta,\ell\cdot M\right)$ by
Proposition 6.

Using Lemma 3 we derive an upper bound on the $G(\mathcal{A}_{d},\ell)$,

$G(\mathcal{A}_{d},\ell)\leq\left|\pi_{m_{d}}^{a_{d}}\right|\cdot\left|\Delta_{d}\right|\cdot
G(\Phi_{d},\ell\cdot M)\cdot
G(\Theta_{d},\ell)\leq\left|\pi_{m_{d}}^{a_{d}}\right|\cdot\left|\Delta_{d}\right|\cdot
G(\Phi_{d},\ell\cdot M)\cdot G(\Theta_{d},\ell\cdot M).$

Then,

$G(\mathcal{C},\ell)\leq\prod_{i=1}^{d}\left|\pi_{m_{i}}^{a_{i}}\right|\cdot\left|\Delta_{i}\right|\cdot
G(\Phi_{i},\ell\cdot M)\cdot G(\Theta_{i},\ell\cdot M).$

The lemma is proved. ∎

######  Lemma 6.

Let $\mathcal{C}$ be a class
$\mathcal{C}=\mathcal{A}_{1}\ltimes\dots\ltimes\mathcal{A}_{d}$ of cascades
where
$\mathcal{A}_{i}=\mathcal{A}(\Phi_{i},\Delta_{i},\Theta_{i};a_{i},m_{i},\Pi_{i},\Gamma_{i})$.
Let $M$ be the maximum length of a string. Let
$h=\max_{i}\operatorname{dim}(\Phi_{i})$ be maximum dimension of a class of
input functions, let $g=\max_{i}\operatorname{dim}(\Theta_{i})$ be the maximum
dimension of a class of output functions, let
$\Delta=\operatorname{arg\,max}_{\Delta_{i}}\left|\Delta_{i}\right|$ be the
class of semiautomata with maximum cardinality, and let
$\pi_{m}^{a}=\operatorname{arg\,max}_{\pi_{m_{i}}^{a_{i}}}\left|\pi_{m_{i}}^{a_{i}}\right|$.
Let $w=\log\left|\pi_{m}^{a}\right|+\log\left|\Delta\right|+h+g\geq 2$. The
dimension of $\mathcal{C}$ is bounded as:

$\operatorname{dim}(\mathcal{C})\leq 2\cdot d\cdot w\cdot\log(d\cdot w\cdot
e\cdot M\cdot|\Pi|\cdot|\Gamma|),$

###### Proof.

By Lemma 5 the upper bound on $G(\mathcal{C},\ell)$ is

$\displaystyle
G(\mathcal{C},\ell)\leq\prod_{i=1}^{d}\left|\pi_{m_{i}}^{a_{i}}\right|\cdot\left|\Delta_{i}\right|\cdot
G(\Phi_{i},\ell\cdot M)\cdot G(\Theta_{i},\ell\cdot M).$

Applying Proposition 1 to terms $G(\Phi_{i},\ell\cdot
M),G(\Theta_{i},\ell\cdot M)$ we obtain

$G(\mathcal{C},\ell)\leq\prod_{i=1}^{d}\left|\pi_{m_{i}}^{a_{i}}\right|\cdot|\Delta_{i}|\cdot\left(e\cdot\ell\cdot
M\cdot|\Pi_{i}|\right)^{h_{i}}\cdot\left(e\cdot\ell\cdot|\Gamma_{i}|\right)^{g_{i}}.$

We loosen the bound by collecting the factors with the exponent and by taking
the maximum of each indexed quantity,

$G(\mathcal{C},\ell)\leq\left|\pi_{m}^{a}\right|^{d}\cdot\left|\Delta\right|^{d}\cdot\left(\ell\cdot
e\cdot M\cdot|\Pi|\cdot|\Gamma|\right)^{d\cdot(h+g)}$

Next we show the claimed upper bound on the dimension of $\mathcal{C}$. By the
definition of dimension, in order to show that a number $\ell$ is an upper
bound on the dimension, it suffices to show that
$G(\mathcal{C}_{\mathrm{bin}},\ell)<2^{\ell}$. Then, since
$G(\mathcal{C}_{\mathrm{bin}},\ell)\leq G(\mathcal{C},\ell)$ by Proposition 3,
a number $\ell$ satisfies $G(\mathcal{C}_{\mathrm{bin}},\ell)<2^{\ell}$ if it
satisfies $G(\mathcal{C},\ell)<2^{\ell}$, and in turn if it satisfies

$\left(\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\right)^{d}\cdot\left(\ell\cdot
e\cdot M\cdot|\Pi|\cdot|\Gamma|\right)^{d\cdot(h+g)}<2^{\ell}.$

We show that the former inequality is satisfied for $\ell=2\cdot d\cdot
w\cdot\log(d\cdot w\cdot e\cdot M\cdot|\Pi|\cdot|\Gamma|)=2\cdot d\cdot
w\cdot\log(d\cdot w\cdot e\cdot C),$ where we introduce
$C=M\cdot|\Pi|\cdot|\Gamma|$ for brevity. We keep proceeding by sufficient
conditions. Specifically, at each step, either we replace the r.h.s. with a
smaller expression, we simplify a common term between the two sides, or we
just rewrite an expression in an equivalent form.

$\displaystyle\left(\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\right)^{d}\cdot\left(\ell\cdot
e\cdot M\cdot|\Pi|\cdot|\Gamma|\right)^{d\cdot(h+g)}$ $\displaystyle<2^{\ell}$
$\displaystyle\left(\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\right)^{d}\cdot\left(\ell\cdot
e\cdot C\right)^{d\cdot(h+g)}$ $\displaystyle<2^{\ell}$
$\displaystyle\left(\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\right)^{d}\cdot\big{(}2\cdot
d\cdot w\cdot\log(d\cdot w\cdot e\cdot C)\cdot e\cdot C\big{)}^{d\cdot(h+g)}$
$\displaystyle<2^{2\cdot d\cdot w\cdot\log(d\cdot w\cdot e\cdot C)},$
$\displaystyle\left(\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\right)^{d}\cdot\big{(}2\cdot
d\cdot w\cdot\log(d\cdot w\cdot e\cdot C)\cdot e\cdot C\big{)}^{d\cdot(h+g)}$
$\displaystyle<(d\cdot w\cdot e\cdot C)^{2\cdot d\cdot w},$
$\displaystyle\left(\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\right)^{d}\cdot\big{(}2\cdot
d\cdot w\cdot\log(d\cdot w\cdot e\cdot C)\cdot e\cdot C\big{)}^{d\cdot(h+g)}$
$\displaystyle<(d\cdot w\cdot e\cdot C)^{2\cdot d\cdot(h+g)}\cdot(d\cdot
w\cdot e\cdot C)^{2\cdot d\cdot(\log(|\Delta|\cdot|\pi_{m}^{a}|))},$
$\displaystyle\left(\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\right)^{d}\cdot\big{(}2\cdot
d\cdot w\cdot\log(d\cdot w\cdot e\cdot C)\cdot e\cdot C\big{)}^{d\cdot(h+g)}$
$\displaystyle<(d\cdot w\cdot e\cdot C)^{2\cdot d\cdot(h+g)}\cdot(d\cdot
w\cdot e\cdot C)^{2\cdot d\cdot(\ln(|\Delta|\cdot|\pi_{m}^{a}|)/\ln 2)},$
$\displaystyle\left(\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\right)^{d}\cdot\big{(}2\cdot
d\cdot w\cdot\log(d\cdot w\cdot e\cdot C)\cdot e\cdot C\big{)}^{d\cdot(h+g)}$
$\displaystyle<(d\cdot w\cdot e\cdot C)^{2\cdot d\cdot(h+g)}\cdot(d\cdot
w\cdot e\cdot C)^{2\cdot d\cdot\ln(|\Delta|\cdot|\pi_{m}^{a}|)},$
$\displaystyle\left(\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\right)^{d}\cdot\big{(}2\cdot
d\cdot w\cdot\log(d\cdot w\cdot e\cdot C)\cdot e\cdot C\big{)}^{d\cdot(h+g)}$
$\displaystyle<(d\cdot w\cdot e\cdot C)^{2\cdot
d\cdot(h+g)}\cdot\left(\left|\pi_{m}^{a}\right|\cdot\left|\Delta\right|\right)^{2\cdot
d},$ $\displaystyle\big{(}2\cdot d\cdot w\cdot\log(d\cdot w\cdot e\cdot
C)\cdot e\cdot C\big{)}^{d\cdot(h+g)}$ $\displaystyle<(d\cdot w\cdot e\cdot
C)^{2\cdot d\cdot(h+g)},$ $\displaystyle 2\cdot\log(d\cdot w\cdot e\cdot
C)^{d\cdot(h+g)}$ $\displaystyle<(d\cdot w\cdot e\cdot C)^{d\cdot(h+g)},$
$\displaystyle 1$ $\displaystyle<\left(\frac{(d\cdot w\cdot e\cdot
C)}{2\cdot\log(d\cdot w\cdot e\cdot C)}\right)^{d\cdot(h+g)}.$

The term on the r.h.s. is strictly greater than $1$ whenever $d\cdot w\geq 2$,
considering that $C\geq 1$. The lemma is proved. ∎

##  Appendix B Formal Description of The Running Example

The sequence task of the running example (Example 1) is formalised by the
following Temporal Datalog program—for Temporal Datalog see (Ronca et al.
2022). Let $\mathit{wood}$, $\mathit{iron}$, $\mathit{fire}$,
$\mathit{steel}$, and $\mathit{factory}$ be unary unary predicates. They are
used to model the input. For example, $\mathit{wood}(17)$ is in the input
trace if the agent collects wood at time $17$, and $\mathit{factory}(5)$ is in
the input trace if the agent attempts to use the factory at time $5$.
Additionally, let $\mathit{getWood}$, $\mathit{getIron}$, $\mathit{getFire}$,
$\mathit{getSteel}$, and $\mathit{useFactory}$ be unary predicates. They are
defined by the following rules.

$\displaystyle\mathit{wood}(t)$ $\displaystyle\to\mathit{getWood}(t)$ (4)
$\displaystyle\mathit{getWood}(t)$ $\displaystyle\to\mathit{getWood}(t+1)$ (5)
$\displaystyle\mathit{iron}(t)$ $\displaystyle\to\mathit{getIron}(t)$ (6)
$\displaystyle\mathit{getIron}(t)$ $\displaystyle\to\mathit{getIron}(t+1)$ (7)
$\displaystyle\mathit{fire}(t)$ $\displaystyle\to\mathit{getFire}(t)$ (8)
$\displaystyle\mathit{getFire}(t)$ $\displaystyle\to\mathit{getFire}(t+1)$ (9)
$\displaystyle\mathit{steel}(t)$ $\displaystyle\to\mathit{getSteel}(t)$ (10)
$\displaystyle\mathit{getSteel}(t)$ $\displaystyle\to\mathit{getSteel}(t+1)$
(11) $\displaystyle\mathit{getSteel}(t-1)\land\mathit{factory}(t)$
$\displaystyle\to\mathit{useFactory}(t)$ (12)
$\displaystyle\mathit{getWood}(t-1)\land\mathit{getIron}(t-1)\land\mathit{getFire}(t-1)\land\mathit{factory}(t)$
$\displaystyle\to\mathit{useFactory}(t)$ (13)
$\displaystyle\mathit{useFactory}(t)$
$\displaystyle\to\mathit{useFactory}(t+1)$ (14)

Then, at any given time point $\tau$, the task has been completed if
$\mathit{useFactory}(\tau)$ is entailed by the input facts and the rules
above.

## References for The Appendix

Kakade, S.; and Tewari, A. 2008. Lecture Notes of CMSC 35900 (Spring 2008)
Learning Theory, Lecture 12. Available at:
https://home.ttic.edu/%7Etewari/lectures/lecture12.pdf [Last accessed:
30/11/2022].

Ronca, A.; Kaminski, M.; Cuenca Grau, B.; and Horrocks, I. 2022. The delay and
window size problems in rule-based stream reasoning. _Artif. Intell._ , 306:
103668.