Metric Automata Theory: A Unifying Theory of RNNs
Authors: Adam Dankowiakowski
Alessandro Ronca
Venue: NeurIPS 2025 poster ()
Keywords: RNNs
Recurrent Neural Networks
SSMs
State Space Models
Expressivity
Formal Languages
Automata Theory
Algebraic Automata Theory
Metric Spaces
Topology
Mamba
Linear Recurrent Neural Networks
Cascades
Krohn and Rhodes
Primary area: theory
TL;DR: We present a unified theory for the study of RNN expressivity, with novel results on several popular architectures, and insights on the relationship between linear and non-linear RNNs.

Abstract: We propose Metric Automata Theory, an elegant generalisation of classic Automata Theory to continuous dynamical systems, that constitutes a unifying theory of all kinds of Recurrent Neural Networks (RNNs), including widely-adopted architectures such as xLSTM and State Space Models (SSMs). The theory allows one to analyse RNNs both in the finite and unbounded precision settings seamlessly, while utilising fundamental results of Automata Theory. It also provides a novel notion of robustness that guarantees numerical stability and contributes to stability of learning. We employ the theory to prove a comprehensive set of expressivity results for widely-adopted RNNs, with a focus on robustness and finite-precision. Notably, we contrast the capabilities of xLSTM and SSMs for robustly modelling all star-free regular languages—xLSTM can do so, while SSMs cannot robustly recognize the FLIP-FLOP language. Thus we give a novel perspective on the importance of non-linear recurrences, giving insight for why xLSTM shows superior performance to SSMs on several tasks. We provide an improved understanding of the capabilities of Mamba, a popular SSM model. We show that Mamba is not generally capable of recognising the star-free languages under finite-precision, which is seemingly in contrast with the existing theoretical and empirical results for SSMs. We clarify the picture, by showing that Mamba admits a piecewise-linearly separable state space that allows it to approximate star-free languages, with some
length-generalisation abilities. At the same time, Mamba does not admit such state spaces for languages like Parity. This explains why empirically Mamba performs well on star-free languages, and fails on Parity.

Metric Automata Theory: A Unifying Theory of RNNs
Adam Dankowiakowski University of Oxford adakooviakkorsstt02@maa.. com
Alessandro Ronca IRIS-AI
Abstract
We propose Metric Automata Theory, an elegant generalisation of classic Automata Theory continuous dynamical systems. that constitutes unifying theory all kinds of Recurrent Neural Networks (RNNs), including widely-adopted architec- tures such as xLSTM and State Space Models (SSMs). The theory allows one to analyse RNNs both in the finite and unbounded precision settings seamlessly, while utilising fundamental results of Automata Theory. also provides a novel notion of robustness that guarantees numerical stability and contributes to stability learning. We employ the theory to prove a comprehensive set of expressivity results for widely-adopted RNNs, with focus robustness and mnite-precision Notably, we contrast the capabilities of xLSTM and SSMs for robustly modelling all star-frre regular languages xLSTM can do so, while SSMs cannot robustly recognize the FLIP- FLLP language. Thus we give a novel perspective on the im- portance of non-linear recurrences, giving insight for why xLSTM shows superior performance to SSMs on several tasks. We provide an improved understanding of the capabilities of Mamba, popular SSM model. We show that Mamba is not generally capable recognising the star-free languages under finite- preccssoeeiiion, which is seemingly in contrast with the existing theoretical and empirical results for SSMs. We clarify the picture, by showing that Mamba admits a piecewise-linearty separable state space that allows abilities. At the same time, Mamba does not admit such state spaces for languages like Parity. This explains why empirically Mamba performs well on star-free languages, and fails on Parity.
approximate star-free languages, with some
Introduction
Recurrent Neural Networks (RNNs) encompass all the neural networks that process sequences by maintaining a state though some form of recurrence. Notable RNNs are Vanilla RNNs such as Elman-RNNs [Elman, 1990], LSTM [Hochreiter and Schmidhuber, 1997], GRU [Cho et al., 2014], and the more recent and now widely-adopted xLSTM [Beck et al., 2024] and the family of State Space Models (SSMs) including S4 [Gu al., 2022], Mamba [Gu and Dao, 2023), HiPPO [Gu et al., 2020], and DeltaNet (Yang et al., 2024]. The more recent RNNs achieve state-of-the-art performance, comparable other notable neural networks such Transformers [Vaswani al., 2017]. by leveraging new design principles that overcome the limitations of previous RNNs, enabling key properties such parallel training to take full advantage of modern computer architectures.
Recently, there has been an increasing interested in developing a systematic understanding of the capabilities of sequence models, including RNNs and Transformers, beyond empirical evidence. As of now, there a rich literature of formal results regarding the expressivity both RNN (cf. [Knorozova and Ronca, 2024a.b, Weiss al., 2018, Merrill et al., 2020)) and Transformers (cf. [Strobl et al., 2024, Merrill and Sabharwal, 2024, Hahn, 2020]), with some studies directly comparing the two, e.g. [Bhattamishra et al., 2024]. We focus modelling RNN expressivity in terms of formal
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

languages- an active area, with big impact on the new directions of research for novel architectures. For instance, Sarrof et al. [2024] showed that a family of SSM models, including Mamba [Gu and Dao. 2023], has expressivity restricted to star-free regular languages in the finite precision setting, due to restricting the eigenvalues of the state-update gates to non-negative. Soon after, Grazzi al. [2025] extended the capabilities of SSMs beyond star-free languages, by modifying the implementation of Mamba and DeltaNet models to allow negative soanvallus-narrowwy the gap between SSMs and LSTM models.
The main limitation of this recent literature is that it lacks a principled, cemmonly-acceptee theory or framework providing the a established setting for investigations. For instance, both Sarrof et al. [2024] and Grazzi et al. [2025] provide similar arguments proving that under finite- pratte-preisionn SSMs with gates with non-negative eigenvalues are restricted to star-free languages (with Sarrof et al. [2024] proving a special case). However, the details of the finite-precision frameworks used by the two are completely different, and result in different assumptions. This means that the results are hard to compare without carefully assessing the assumptions and inspecting the proofs.
We propose Metric Automata Theory (MAT) as an elegant and principled theory that generalises Automata Theory to continuous dynamical systems, with RNNs being special case of particular interest. It has the ambition of being a unifying theory for the study of all kinds of RNNs, providing common framework that allows for analysing the expressivity of RNN architectures way, in order to guarantee solid progress in the field. First of all, MAT generalises the notion of finiteness a general metric notion of n-finiteness (Definition 2). which captures the intuitive idea of the finite-precision setup, while retaining generality. Second, we develop correspondence between n--inite systems and finite automata, thus allowing us to apply powerful algehraic results and notions of Automata Theory. Third, the theory introduces a notion of robustness (Definition 4) that guarantees numerical stability, contributes to stability learning, and notably allows one to prove results for real-world finite-precision implementations while abstracting away the difficulties introduced by inite-precision arithmetic. Fourth, we develop the notion of wwweeetriiaall-onssraiiiii (Definition 8). This notion goes beyond the setting of finite-precision, allowing for modelling of languages beyond regular. It captures the empirical properties of systems approximating languages with length-genn generalization properties, which observed in practice. Finally, we showcase the effectiveness of Metric Automata Theory by proving a comprehensive set of expressivity results for aadely- RNN architectures, with focus robustness and finite-precision We argue that results provide an improved understanding of the actual capabilities of RNNs as observed in practice.
uniform
systems
2 Preliminaries
We present the most central and possibly lesser-known preliminary notions here, and we defer notation, additional background metric spaces, background on Recurrent Neural Networks, and additional background on the topics presented below to Appendix A.
Path-connectedness in metric spaces. A path in X from a to is continuous map Y [0, 1] -> X such that (0) = a and >(1) b. We can define relation ~x, where a ~ b when there is path in X from a to b. This relation is an equivalence, partitioning X into disjoint equivalence classes, called (path- connected) components. For space X, we denote the set of its equivalence classes by X. is preserved by continuous functions, which is crucial property to our theory. Notably, continuous function X - Y. with finite codomain Y. has to map all points within a component of X to the same element of Y.
Path-connectede
Dynamical systems. Following [Knorozova and Ronca, 2024a.b]. we adopt dynamical systems as our general formalism. A (dynamical) system is tuple S (X, U, zo. Y, h), where X is the state space, U is the input space, ff XX x U > X is the dynamics function, Zo E X is the initial state, Y is the output space and h X x U Y is the output function. We have that X. U, Y are metric spaces, and f, h are continuous. We call the tuple D = (X, U, f) the dynamics of S. Given To E X and N N, dynamics D define map from sequences uII..N] of inputs to sequences F|I..N] of states with each state given by I,, f fzn-11 u.). Hence, we say that D defines the function D X x U² + X with D(2., =) = 2e on the empty sequence E, and D(x, up..)) = 2, on any input string up..a]- We refer to the function defined by D as state-sequence function. System S defines map from input sequences U(1..N] to output sequences VII.N]] where yn. h(2n, un) for
2

---

all n. Hence, we say that S defines the function S : U - with S(un...)) = Yn. When h is independent of U, we additionally define S(e) = h(zo), extending the definition to S U + Y.
Cascades. The formalism of cascades provides a flexible way to describe dynamical systems consisting of subsystems forming an acyclic network. Their flexibilityy allows us, e.g., to consider not only reed-fowward layers of SSMs as [Grazzi al., 2025, Sarrof et al., 2024], but also more complex architectures with, e.g., mixes of different types of neurons (see Figure 6 in Appendix A.6).
A feed-forward cascade C' is form of dynamics {X, U, with X X1 with a particular factorisation. We may see C' as consisting of dynamics DI...., Dr where D, = (X,, U Xp..t-1)). State updates in a cascade proceed in a feed-forward fashion, with component D; having access to the updated states of the previous components D1...., Di-1. Details of cascades in relation to Automata Theory are deferred to Appendices B.5 and G.2.
x X,= and
Finite Automata and Formal Languages. A (finite) alphaber is finite set E of elements called letters or symbols. A (formal) language over E is a subset of Σ" It is often convenient to charac- terise L in terms of its indicator function Mz. A (finite) automaton is a tuple A = (Q, 2, 6, go, 0). where Q is a finite set of elements called states, called transition function, I' is an alphabet called output alphabet, and 0 Q Σ + I' is called output function. The tuple A' = (Q, Σ, 8) is called a semiautomaton, and in particular A' is the semiautomaton of A.
the finite input alphabet, 8 : Q x Σ - Q is
An automaton A with output alphabet r {0, } is called a language recogniser, and it recognises the language T. whose indicator function is the one defined by A. The languages recognised by finite automata are the regular languages.
Algebraic Automata Theory (AAT). It studies finite automata through the lens of algebraic notions such as semigroups and groups, c.f. [Hartmanis and Stearns, 1966. Ginzburg, 1968, Arbib, 1969, Dömösi and Nehaniv, 2005]. The Prime Decomposition Theorem by Krohn and Rhodes [1965] shows how every semiautomaton can be decomposed into a cascade of prime semiautomata. One prime semiautomaton is the flip-flp. that describes the elementary system with the ability to store and manipulate one bit of information. Formally, FLIP-FL.P == ((high, low), (set, reset, id), 6) with transitions give by 8(g, id) = q, 5(g, set) high, and 8(q, reset) = low for every state q.
Automata that admit a cascade decomposition into flip-flops are called group-free, and they are central since group-free automata recognise the star-free languages, cf. [Ginzburg, 1968]. To relate different automata, we adopt the notion of realisation for Mealy machines, cf. Definitions 1.14 and 1.15 of [Hartmanis and Steams, 1966] and appendix B.4. Realisation describes how machine can imitate another machine after a renaming of inputs and outputs.
Recurrent Neural Network Architectures An Elman-RNN has dynamics D J) where f(z,, u) tanh (Ax x Au + b). State Space Models (SSMs) are based on linear recurrence with particular parametrisations such as Mamba [Gu and Dao, 2023]. To model linear recurrence in general, we introduce Linear Recurrent Dynamics (LRD), defined dynamics (X, U, f), where f(z, A(u) + B(u), with states X C K datate, inputs U Kduapus for K {R, C), We call A(u) E Kdatateooo ddatte the state-transition gate and B(u) E K the input gate. The recently introduced model xLSTM [Beck et al., 2024] makes use of both non-linear and linear recurrences. XLSTM introduces two types of blocks: sLSTM and mLSTM. We provide the parametrization of mL.TTM blocks in Appendix G.3.
3 Metric Automata Theory
We present Metric Automata Theory (MAT), a generalisation of Automata Theory dynamical systems. Next we present preliminary considerations on automata and the preliminary notion of language recognition for dynamical systems. Then we present the central notions of the theory.
Automata as dynamical systems. We start by observing that finite automata are special case of dynamical systems. Our goal to establish a framework to analyse Recurrent Neural Networks (RNNs), with a focus on the study of their expressivity in terms of the ability to recognise formal
3

---

7--initte Dynamics
Semiautomaton C(D)
X2
tranitionn
[D] tranitioon
Po
Zo
[Pt]
ins
Figure System dynamics and corresponding canonical semiautomaton, given Definition
languages. Every automaton A = (,, 9o. r) is dynamical system if we endow Q, E, I with the discrete metric, giving them a discrete topology. In particular. this implies that the functions and 0 are trivially continuous, and hence it shows that automala are continuous systems. The connection to dynamical systems makes clear that a semiautomaton is special case of dynamics, and clarifies how automata define functions F Σ+ + T.
Σ - U and dec Y T, we say that a system Š implements a function F Σ+ + r, with encoder enc and decoder dec, Σ+, where enc(w) U+ applies We also say that S can-implement F it implements F for some choice of enc and dec. When T {0, 1}. we say that S recognises a language L if implements its indicator function II, and that S can-recognise if it can-implement II.
Definition 1. Given alphabets E and r, and continuous functions
if F(w) dee o.((enc(u)), for every
element-
3.1 The Notion of Fi-Finiteness for Dynamical Systems
We show that the metric setting allows for general notion of finiteness of a given space, capturing the fact that is essentially finite even its cardinality net-details in Appendix B.
Definition 2. For X set with X C Rd or X C Cd, we say that X is n-finite if is a finite union of compact, path-connected components. Then, say that dynamics (X, f) are n-finite if both X and U are finine. Finally, system S is 1f-fnite if its dynamics are r--finite.
We refer to the components of the definition as n-components of the space. For example, finite alphabets are n-finite with each element being its own n-component. As path-connectedness and compactness are preserved by continuous mappings, the notions of nj-finiteness and n-component have very favourable theoretical properties. Any continuous mapping f X Y, with X and Y f-fiiitt, is guaranteed to map any n-component of X entirely into single n-component of Y.
As result, all points within the same yielding equivalent behaviours of the system; and all points within the same input or output r7- component will correspond to the same inputs and outputs modulo encoding and decoding.
17-ommooentt will be interpreted equivalent states,
All automata are fi-iitt systems since they are discrete. Conversely, every ri-finite system admits canonical automaton, which fully captures its dynamics and capabilities. It gives way to employ the powerful characterisations and results of AAT to any fininete system dynamics. Figure visualizes the way in which the canonical (semi)automaton is a discrete interpretation of the continuous dynamics.
Any y-finite dynamical system S = (X,U, zo, Y, admits a unique canonical automaton, and any ni-fnnit dynamics D V.9.) admits unique canonical semiautomaton, which are respectively given by C(S) = (X,U, U,f.S [ Im h h). and C(D) (2, V.)).
Definition 3.
Theorem 1. An Tf-inite system S can-implement the same functions its canonical automaton, which are necessarily regular.
Canonical automata are core tool we use to develop an algebraic theory of continuous systems. Generally, it allows us to abstract away the local details of continuous behaviour that do not affect the global expressive capacity of the system. use to, e.g., apply the decomposition theorems of AAT to RNNs, and to create the appropriate analogue of realisation of continuous system.

---

Strongly robust system + e-covering approximation
18
5
E-robust B(f(z. EX
"Transitions have margin of error"
X
Figure 2: Given sufficient precision, the transitions of strongly e-robust dynamics can be realized with approximate dynamics on finite datatype, whenever the datatype gives e-covering for the state-space.
MAT applied to finite-precision. We explain how Metric Automata Theory provides the founda- tions to study dynamical systems in a principled way, with the study RNNs as a special case that is of particular interest for us. First, we note that y--finttneess ensures that the 77-omppoents of the considered space are bounded and separated by some positive non-zero distance. Thus, in all 17-finite systems, sequences of states converging to limit will eventually lic in single 17-state- note that this is the key property of the finite-preciss precision arguments in [Sarrof et al., 2024]. Additionally, in every inite-precision implementation of system (e.g., with states represented tensors of floating-poin numbers), the state space has finite cardinality, and hence it is trivially 17- 17-finite. Similar considerations apply the input and output spaces. Altogether, Metric Automata Theory equipped with the notion of g-finiteness allows for studying finite-precision (implementations of) dynamical systems without restricting the analysis to any specific representation of the relevant spaces. The next section develops the theory in the case of system implementations based on concrete datatypes.
3.2 Robust Systems
The central notion that allows us to extend Metric Automata Theory to the study of finite-precision implementations the notion of e-robustness. Intuitively, it describes stability of the dynamics under transition perturbations. It provides a way to connect 17- 17-finite systems to their floating- point implementations on real-world computer architectures, without requiring us to commit to any particular standard of floating-pont operations. We let Ba(æ, r) (v Ω || - yll S r), which denotes the closed Qt-bal at x of radius r.
Definition 4. For c > 0 and X S Ω dynamics D = (X,U, f) are c-robust (in f2) if, for every x E X and every u E U, it holds that (n(f(x, u), C -ie-iee, E X for all y E Q s.t. (z, u) - I e.. We say that dynamics D) are strongly e-robust (in Q2) if they are e-robust (in Q2) and each ny-component of contains an Ω-hall of radius at least e.
We call dynamics robust (resp. strongly robust), if they are e-robust (resp. strongly e-robust) for some O. Note that the property of robustness is with respect to the ambient space R, which contains the state space X. It is possible that dynamics is e-robust w.r.t. some ambient space (c.g., IR), and not e-robust w.r.t. another ambient space (e.g., C). Next we discuss how notion of robustness allows for drawing conclusions on datate- implementations of a system.
Definition A finite datatype is a set D C Ω = Rd having finite cardinality. A finite-datatype implementation of system S is then system whose input, state, and output spaces finite datatypes, and whose dynamics and output functions are implemented using floating- point operations.
Theorem 2 (Informal version). Every fi-inite system with strongly e-robust dynamics, for 0. can be implemented with floating point operations given sufficiens precision.
By sufficient precision we mean that the state space is sufficiently covered by the finite datatype, and that the floating-point approximation of the dynamics has error at most e. In Appendix C we show two examples of floating-point parametrisations for which the former condition can always be achieved using sufficiently-mait many bits of precision.
5

---

Considerations on training. Training any machine learning model that can be seen as dynamical system amounts optimising a parametric dynamics function fo. with learnable parameter 0 O, along with optimising the output function. In Section C.2 of Appendix C, we prove that, under some mild regularity assumptions, when dynamics Dg = (X, U, fo) are robust, there 6 > such that for all 0' E θ with ||0 0'll S 6, the function far X x U - X is a well-defined dynamics function, and the corresponding dynamics De = (X, U, for) have the same 77 dynamics as Dø-i.e,, they both have the same canonical semiautomaton. Thus, replacing fo with for in a system will not change the system behaviour. Given the previous consideration, an argument should be possible by which models enjoying this form of robust parametrisation are more likely to be produced by training algorithms, compared to models that do not admit robust parametrisation. However, a systematic development of this argument is beyond the scope of our work.
4 Expressivity Results for Vanilla-RNNs, xLSTM, and SSMs
Metric Automata Theory allows us to establish a rich ensemble of expressivity results in the finite- precision setting and beyond finite- precte-preiiion. The elegance and generalisability of our setup enables us to compare capabilities of wildly different models. For example, Theorem 4 applies to SSMs with both real and complex state spaces.
4.1 Expressivity Results for Robust Language Recognition
We prove that linear recurrences do not admit robust dynamics, whenever they have an identity transformation on their yy-states.
Theorem 3 (Non-robustness of LRDs). Suppose q-finite LRD D is such that its canonical semiautomaton DA has at least two states, and an input inducing an identity transformation. Then D cannot be e-robust for any O.
In fact, we show that upon iterating any single input the whole state-space of an 1y-finite e-robust LRD collapses to a single 7-component, We call such dynamics contracting. Furthermore, we show that cascade of contracting dynamics is contracting, and that contracting dynamics cannot implement a FLIP-FLOP, We defer the technical details to Section D.3.
Theorem 4 (LRDs cannot do FL.IP-II.OP robustly). FL.P-FFLOP cannot be implemented by cascade of q-fitte c-robust LRDs for any 6 > O.
XLSTM. We provide constructions for strongly robust realisations of the FLIP-FLOR dynamics for Elman-RNNs and for an sLSTM block-see Appendix G.3 for the details. The Elman-RNN construction is similar to one provided in [Knorozova and Ronea, 2024a], with the high and low 1t-states located around the attracting fixed-points of tanh. For xL.TTM fixing a particular parametrisation of sLSTMM block allows non-linearity. By Fact 1, this proves that all star-free languages can be implemented cascade of strongly-robust xLSTM blocks. Such a cascade strongly-robust.
use very similar construction, with a sigmoid
Theorem 5 (XLSTM does start-free robustly). All star-free languages be recognised by xLSTM cascades, as well as by floating-pon implementations of XLSTM cascades given sufficient precision.
4.2 SSM Expressivity in
We prove that finite SSMs with tateetrranstion gates having non-ne non-negative eigenvalues are restricted to group-free dynamics, and hence can only implement star-free languages, in line with the theoretical results by Sarrof et al. [2024] and Grazzi et al. [2025]. in their respective precision setups.
SSMs with non-negative eigenvalue gates are star-free. To transfer the group-free notion into the continuous 17- finite dynamics setting introduce notion of aperiodic dynamics. We say that an infinite sequence in a f-nitite space X is convereeg in X if all terms of the sequence are eventually in the same comompnett of X.
Definition 6. We say that r--finite dynamics D = XXUU are aperiodic if, for every 3o E X and every input sequence (un)a21 that is -)convergeet in U, we have that the corresponding state sequence (Ix)xz) is 7-convergent in X.

---

sequence aperindic D
ststate sequence of C(D)
Vn May E [1]
[x--]
Figure 3: Definition of aperiodicity means that the state sequence of aperiodic dynamics under iterated input from the same 17-ompooent always 77-onvvrres.. In particular, if the state sequence always converges to some limit under iterated inputs, then the dynamics are aperiodic. This the case e.g., for LRDs with diagonal gates with entries in (-1,1).
In Section D.2 of Appendix D, we show that cascades of aperiodic dynamics are aperiodic. Moreover, we show, that 1y-finite dynamics are aperiodic iff their canonical semiautomaton group-free. Thus, aperiodic fi-fintte systems can implement only star-free regular languages.
Theorem 6. Let D be 7-finite Linear Recurrent Dynamics, with its state-transition gates having all non-negative eigenvalues. Then aperiodic.
The proof structure is similar to the proof of Theorem 1 in [Grazzi et al., 2025], with significant simplifications afforded by our theory. We show that, iterating fixed input, the state converges, by considering the Jordan Normal Form of the state-transition gate. We also show that finite context length convolutions are aperiodic. Thus, SSMs like Mamba, which are cascades convolutions and LRDs with non-negative eigenvalue gates, can only recognise free languages they are --finite.
Mamba cannot implement FlipFlop in finite- phnite-recision. The FlipFlop dynamics construction presented in [Sarrof et al., 2024] makes use of the identity ttanc-transition gate. Parametrisation of Mamba prevents it from making use such gate. fact, we prove that in the 77- n-finiteness framework, Mamba blocks contracting dynamics, and thus cannot implement a FLIP-FLOP.
Theorem 7. SSMs with Mamba parametrisation cannot recognise FL.P-FL.OP.
4.3 Geometrically Constrained Systems
The case of Mamba successfully length- gengrhhgnnralising on star-free tasks, despite being unable model the dynamics for unbounded length inputs, motivates us to expand our theory beyond fi-finite systems. The intuition behind the following setup to allow only for output functions that are sufficiently regular to expect them to be learnable from short input sequences, with length-genent generalisation. Ultimately, this section provides an example of how Metric Automata Theory can be used develop theories alternative n-finiteness, motivated by phenomena observed empirically and defined by geometric properties of the dynamical systems.
Definition Let 52 Rdd Ω Cd. We call C S l convex-covering if is a finite union of open, convex sets in Q2. Then, we say that X C Ω is comve-covered by C if X C.
components, which are open. The path-connected components of C' can be arbitrarily classified by output function with piecewise- linear decision boundaries, with finitely many vertices. Such output functions include all -orwwrd networks with ReLU activations,
convex-covering consists of finitely-many path-connee
Proposition 6.1 in [Zhang al., 2018).
Definition 8. Let Ω Rd or Ω Cd, and let C C Ω. We say that dynamics D = (X.U.)) are comvex-covered by C is convex noveeee by C. We call a system Sc = U, S. Co Y,h) geomerrically-consttrineed by C if its dynamics De = (X, U, J' are convex-covered by C.
Geometricalll-connstn systems (GCS) are a generalisation of fi-inite systems, as any finite can be extended to caammttrccally-conttaainn system with equal capabilities. GCSs can in fact express dynamics beyond finite-state, e.g., Construction 1. The GCS framework is presented in Appendix E.
Construction 1. Consider Linear Recurrent Dynamics with state-space = Z, input space {a, b} and dynamics function f(n, a) + 1; f(n.b) n 1. The space C = (-xc, -0.5) U
7

---

I
21
C2
[C1]
[C2]]
[Cs]
[C]]]
Sepurating hyperplanes
12
++0
30
21
72
1x+1 = Au Cn + Bu A. with e- v-vuuess 2 0
X
Figure 4: SSMs with state transition gates without negative eigenvalues are not capable of alternating around any separating hyperplane under iterated input. Thus, eventually the state must be mapped to a constant output. This makes such SSMs unable e.g., implement Parity GCSs.
(-0.5, U (0.5, oo) is a convex for this dynamics. We may define the output function h: C' {0, 13 map points in (-oo, -0.5) (0.5, oo) to 0 and points in (-0.5, 0.5) Picking initial state zo = 0, we have that this GCS outputs precisely when the input has the same number of as and bs.
Connection to automata. In the case of dynamics (X, f) constrained by X, we recover the correspondence to Automata Theory via canonical semiautomata, and hence we can use the theorems of AAT-details in Section E.2. The next construction shows that, as a GCS. Linear Recurrent Dynamies with Mamba parametrisation realise TT.IP-F..O unlike in the robust fi-iiite setting.
Construction 2. FLIP- FLOP dynamics
be realised by constrained Linear Recurrent Dynamics with diagonal tranttttannition gate, with entries in 1 31.
ql. Take D = (X,U, with = J U B, where (A,, B,) A,
where X (-1, X (0, 1), U (i, h3 and fax a)
(3/4, 0); (A, Bi) = (1/4, -122); (A,, Ba) = 1/2, With output function X₁ + low and XA + high (indeed continuous), D realizes FLIP-FLOPP, and X is convex-covering of D.
In particular, given the realisation of FL.I--FLOP in Construction 2, we obtain the following:
Theorem 8. SSMs with Mamba parametrisation can recognise star-free languages as GCSs.
Modular counting. We extend the notions of cascades this setup, with restriction how components depend on inputs from other components, corresponding to the idea of joining the cascade with connecting functions. Similarly, extend the notion of aperiodic dynamics, with the modification that we require the state-sequence to be y-convergent in C, instead of in the usual definition. Appendix E explains how aperiodicity is preserved by constrained cascades in this setup. In the GCS framework, we can no longer equate aperiodic dynamics with group-free semiautomata-ttee GC-system in Construction is aperiodic, but implements language which is not even regular. We can still obtain more specialised expressivity results. Aperiodicity prevents a GC-system from modelling any function for which iterating the same input can alternate between distinct outputs indefinitely. We call a function F E - I' is alternating if. for some = Σ, the sequence (F(a")) n21 changes value infinitely many times. All alternating functions are group-like. As an example, functions that perform modulo-M counting are alternating.
Theorem 9. Let D be an f-finite Linear Recurrent Dynamics, with its state-transition gates having all non-negative eigenvalues. Let C be a covex-regular covering of D. Then D is aperiodic w.r.l. C.
The proof is similar to that of Theorem 6. By considering the Jordan Normal Form of the state- transition gate, we show that the state sequence cannot alternate around the separating hyperplanes of the convex components making up C. Overall, we obtain that SSMs such as Mamba are not able to systems.
implement alternating functions as geometrically-
5 Empirical Validation of Our Results
Mamba performance on star-free tasks. The experiments presented by [Sarrof et al., 2024] demonstrate that Mamba can effectively learn star-free languages with wongth-generalisation abilities. the benchmark from [Bhattamishra al., 2023], Mamba performed perfectly on all 11 star-free tasks, also on ofitt--diit input lengths. This is consistent with its expressivity described by

---

reset
high
low
read
set
read
Figure 5: FLIP-FLOP task [Liu al., 2023]. PCA of trained I-layer Mamba states for each channel: red and blue are state sequences under 10 inputs, starting from w1 and wo respectively. After =1000 inputs, both state sequences give the same predictions on the read instruction r, incorrectly.
Theorem 8. We performed additional experiments on the dataset from [Liu et al., 2023]. It introduces the task of realizing the F1.IP-FI.OP by predictively modelling sequence of instructions. We found that in the case of training 1-layer Mamba, despite achieving accuracy 1 on all validation datasets, iterating the ignore instruction indeed leads to incorrect outputs, as predicted by our results for ry-fniite systems, namely Theorem 7, See Figures 5,10 and Appendix F for details.
Non-star-free tasks. Our negative results for SSMs the 7-finite setup predict that SSMs with non- negative eigenvalues (non-negative SSMs for short) for the state-transition gate cannot implement non- star-free tasks. The experiments performed by Sarrof et al. [2024] on Mamba with the datasets from [Bhattamishra et al., 2023] show that Mamba struggles model non-star- free tasks. The empirical evidence presented in [Grazzi et al., 2025] similarly validates our results, with results for non-star- stan-sta--free free languages from the Chomsky Hierarchy benchmark by Deletang et al. [2023]. Remarkably, both the Chomsky Hierarchy and Bhattamishra's 's benchmarks have the worst results for non-negative SSMs languages involving modulo counting. Our negative results in the geometrically cennsticlllyyconttrainedd framework suggest that this is caused by the inherent geometry of the state-space for these models.
Significance of robustness. Beck al. [2024] and Grazzi et al. [2025] evaluate their proposed architectures on the Chomsky Hierarchy benchmark [Deletang et al., 2023]. Even though, as shown in [Grazzi et al., 2025], DeltaNet with negative eigenvalues is capable of modelling the Modular Arithmetic w/o Brackets task, it falls short of perfect accuracy on all sequence lengths. On the other hand, sLSTM achieves perfect accuracy on this task, reported by Beck et al. [2024] (although Grazzi et al. [2025] failed to reproduce these results). Theorem 3 gives a possible explanation for why linear recurrences may perform worse in practice than non-linear recurrences. This effect can also be observed for star-free we defer further discussion to Appendix F.
Beyond regular tasks. Contex-free and context-sensitive tasks remain challenging for the recent recurrent archtectures, as evident by the performance of XLSTM, DeltaNet and Mamba on the Chomsky Hierarchy benchmark, reported in [Beck al., 2024] and [Grazzi et al., 2025]. This indicates that f-finite systems are largely a good model for the finite-precision setting. Sarrof et al. [2024] report that Mamba achieves good results for counter languages, but with limited length- generalisation. We conjecture that counter-like dynamics, which are permitted in the GCS framework, are not possible for Mamba, as its dynamics are space-contracting.
Limitations
The limitations of Metric Automata Theory (MAT) in its current, initial, state of develoment revolve around three aspects, that we discuss below.
Limitations inherited from AAT. MAT allows one to employ Algebraic Automata Theory (AAT) for the purpose of analysing RNNs. However, AAT is underdeveloped in many ways, with limitations on its current ability to describe certain fine-grained expressivity aspects, which clearly transfer to MAT. key limitation is that AAT does not focus on the complexity of the functions that connect the stateful components in a cascade, and specificically it provides no results on how the complexity of such functions influences the expressive capacity of a model. Now that our MAT makes AAT relevant for the study of RNNs, there is new motivation in futher developing AAT.

---

Dynamics-dependenn state space. Requiring continuity throughout means that the main work of assigning meaning to states is done in selecting the state space X. Further, the dynamics f need to have codomain X, which can make verifying constructions complicated. In the context of learning parameters for f. as the parameters vary, the state space must change accordingly, making it less straighforward to derive results regarding learning. Nonetheless, MAT already allows for indirect analysis of learning stability, via the notion of robustness, as discussed in Section 3.2.
Focus on unbounded-length expressivity. Most of our work studies the ability of RNNs to recognise languages where the length of strings is unbounded. Additional results could be proved regarding the ability of RNNs to recognise languages where strings have bounded length. Some of our notions and results- e.g., robustness or can still be applied in this context, but otherwise MAT may require to be extended significantly.
7 Related Work
Our dynamical systems approach follows the framework by Knorozova and Ronca [2024a.b]. This set of results focuses on RNC+, which are cascades of 1-dimensional Elman-RNN neurons, with dynamics function f fIr u) tanh(w ( + u) having w 2 O. Expressivity of RNC+ in terms of regular languages is shown to be exactly the star-free languages. Their setup is not directly relatable to ours under 17- finiiteness, but it implicitly assumes that the state-space is compact, and uses similar convergence arguments as Sarrof et al. [2024] and Grazzi et al. [2025], combined with AAT. The authors hope to further develop the theoretical foundations of expressivity theory, and to incorporate further theories, such as the work in [Knoroooaa and Ronca, 2024a,b), into Metric Automata Theory.
Related expressivity results for SSMs are given in [Sarrof et al., 2024, Grazzi et al., 2025, Merrill al., 2024], and for ReLU-activated Elman-RNay and LSTMs in [Weiss et al., 2018]. We defer the discussion of such results to Appendix H.
8 Future Work
The framework methodology, as well as understanding of empirical phenomena. At the same time, it opens up new avenues for future research in connection automata theory, model design, and learning. We especially see robustness as being of practical interest and as a subject of future research. Next we discuss few concrete points that are on our research agenda. First, we plan to devise additional experiments to fully understand the impact of our results on learning models-e.g. measuring on star-free tasks. Second,
up fills in the gaps in the existing literature in terms of general theoretical
robustness trade-offs between xLSTM and SSM we plan to study how tokenization affects the models ability to perform state-trackinn and realise automata transitions. For example, Grazzi et al. [2025] (paragraph under Theorem page 7) note that allowing more input symbols per transition (e.g., "3 + 2 + 4") allows simpler gates to implement automata. Third, we would like explore the potential of robustness in driving design decisions behind model architectures and training algorithms. For example, the inherent robusteuss of linear RNNs suggests that the solutions that may be learned for the model's parametrisation are very sensitive, especially when it comes to GCS theory for investigating the ability of RNNs to recognise languages beyond regular. A notable family of languages to consider is the one of counter languages, already mentioned in Construction 1 and in the analysis of the performance of Mamba in Scction 5. Finally, we would like to use the GCS theory to further clarify length-gent geggraaeneriiiitioonn phenomena.
abilities. Fourth, we plan to employ the
Conclusions
We have presented Metric Automata Theory, an elegant and principled theory that generalises classic Automata Theory to dynamical systems, and to RNNs in particular. The fundamental notions and key properties of the theory we have described, as well as the deep understanding of several widely- adopted RNNs that we were able to provide using the theory, justify the ambition of the theory to be a unifying theory for the study of RNNs, and also dynamical systems general. The introduced notions, e.g. of robustness, leave many exciting avenues for deeper study.
10

---

References
Jeffrey I.. Elman. Finding structure in time. Cogn. Sci., 14(2):179- 2911 1990.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9()): 1735-1780, 1997.
Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülgehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1724-1734, 2014.
Maximilian Beck, Korbinian Pöppel. Markus Spanring, Andreas Auer, Oleksandra Prudnikova, Michael Kopp, Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. xLSTM: Extended long short-term memory. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. In Proceedings of the Tenth International Conference on Learning Representations (ICLR), 2022.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. CoRR, 0bs/2312.00773 2023.
Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. HiPPO: recurrent memory with optimal polynomial projections. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
Songlin Yang. Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim. Parallelizing linear transformers with the delta rule over sequence length. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz. Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems (NeurIPS), 2017.
Nadezda Alexandrovna Knorozova and Alessandro Ronca. On the expressivity of recurrent neural cascades. In Proceedings of the Thirty-Eigtth AAAI Conference on Artificial Intelligence (AAAI), pages 10589-10596, 2024a.
Nadezda Alexandrovna Knorozova and Alessandro Ronca. On the expressivity of recurrent neural cascades with identity. In Proceedings of the 21 International Conference on Principles of Knowledge Representation and Reasoning (KR), 2024b.
Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite precision RNNs for language recognition. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL), pages 740-745, 2018
William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. A formal hierarchy of RNN architectures. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (ACL), 2020.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? A survey. Trans. Assoc. Comput. Linguistics, 12:543-561, 2024.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations, 2024.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput. Linguist.. 8, 2020.
Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the repre- sentational capabilities of transformers and recurrent architectures. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
11

---

Yash Sarrof, Yana Veitsman, and Michael Hahn. formal language perspective. In Proceedings of the Thirty-Eightt Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
The expressive capacity of State Space Models: A
Riccardo Grazzi, Julien Siems, Arber Zela, Jörg K. H. Franke, Frank Hutter, and Massimiliano Pontil. Unlocking State-tracking in linear RNNs through negative eigenvalues. In Proceedings of the Thirteenth International Conference on Learning Representations (ICLR), 2025.
Juris Hartmanis and R. E. Stearns. Algebraic structure theory of sequential machines. Prentice-Hall international series in applied mathematics, Prentice-Hall, Englewood Cliffs, N.J, 1966.
Abraham Ginzburg. Algebraic Theory of Automata. Academic Press, 1968.
Michael A. Arbib. Theories of abstract automata. Prentice-Hall series in automatic computation.
Prentice-Hal Hall, Englewood Cliffs, N.J, 1969.
Pál Dömösi and Chrystopher L Nehaniv. Algebraic theory of automata networks: An introduction. SIAM, 2005.
Kenneth Krohn and John Rhodes. Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. Trans. Am. Math. Soc., 116, 1965.
Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. Tropical geometry of deep neural networks. In Proceedings of the 35th International Conference Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 5819-5827. PMLR, 2018.
Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. Simplicity bias in transformers and their ability to learn sparse boolean functions. In Proceedings of the 6lst Annual Meeting of the Association for Computational Linguistics (ACL), Volume 1: Long Papers, pages 5767-5791, 2023.
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Exposing attention glitches with flip-flop language modeling. In Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS), 2023.
Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A Ortega. Neural networks and the chomsky hierarchy. The Eleventh International Conference on Learning Representations (ICLR), 2023.
William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in State-Space Models. In Proceedings of the Forty-first International Conference on Machine Learning (ICML), 2024.
Stephen. Willard. General Topology. Dover Books on Mathematics. Dover Publications, Newburyport 1st edition, 2012.
Marcel Paul Schütteeberrger. On finite monoids having only trivial subgroups. Information and Control, 8(2):190-194, 1965.
Nadezda Alexandrovna Knorozova and Alessandro Ronca. On the expressivity of recurrent neural cascades. CoRR, abs/2312.09048,, 2023.
George Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control. Signals Syst. 5(4):455, 1992.
Kurt Horiik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-366, 1989.
Stephen P. Boyd and Lieven. Vandenberghe. Convex optimization. Cambridge University Press, Cambridge, 2006 2004.
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks sequence modeling. CoRR, abs/1412.3555. 2014.
12

---

Hava T. Siegelmann and Eduardo D. Sontag, On the computational power of neural nets. J. Comput. Syst. Sci., 50(1), 1995.
Joe Kilian and Hava T. Siegelmann. The dynamic universality of sigmoidal neural networks. Inf. Comput., 128(1), 1996.
J. Nicholas Hobbs and Hava T. Siegelmann. Implementation of universal computation via small recurrent finite precision neural networks. In 2015 International Joint Conference on Neural Networks (IJCNN), 2015.
Stephen Chung and Hava T. Siegelmann. Turing completeness of bounded-precisinnn recurrent neural networks, In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems (NeurIPS), 2021.
13

---

Appendices
The appendices provide proofs of the theorems stated in the main body, well as detailed exposition of preliminary notions, and illustrative figures. It structured as suppleental body of work which can be read from top to bottom, and which gives detailed presentation of Metric Automata Theory and its main results. While the main body gives a big picture overview of the key notions and results, the appendices aim serve foundational text, showcasing how Metric Automata Theory can be used to develop new theories and draw novel insights about RNN architectures in addition to providing full proofs of all results stated in the main body.
Appendix A provides standard preliminary notions, required for later sections and in particular for proving our results.
Appendix B presents the foundations of Metric Automata Theory (MAT), which build on several different fields-metri spaces, dynamical systems, algebraic and classic automata theory. Also establishing novel and fundamental connections across such fields. We prove Theorem in this appendix.
Appendix C introduces the novel notion of e-robust dynamics, which allows us to argue about real-world floating point implementations of models. It also describes numerical and parametrisation stability properties of systems, thus going beyond the phenomena which can be described by discrete systems. We provide proofs of Theorem 2 and Theorem 5.
Appendix D employs Metric Automata Theory and its connection Algebraic Automata Theory show a collection of expressivity results in the 77-fnnite setting, including Theorems 3, 4, 6 and 7.
Appendix E explores the setting of Geometrically-Consteee Conttraindd Systems (GCS), in connection to the empirical -eggthhennralisttion capabilities Mamba, which go beyond its finite-precision expressivity. We give proofs of Theorem 8 and Theorem 9.
Appendix F gives further details on the visualisation experiments we conducted to showcase the state-space collapse suffered by Mamba SSMs.
Appendix G contains technical proofs and constructions deferred from other sections, which necessary to fully comprehend the overall argument they are used in.
Appendix H continues the discussion of related work from Section 7, notably contrasting the frameworks of Sarrof et al. [2024] and Grazzi et al. [2025].
A Additional Preliminaries
In this Appendix, we introduce the preliminary notions for the remainder of this work.
Section A.1 covers basic mathematical notions and notation used throughout.
Section A.2 introduces the necessary background in Metric Spaces and Topology, notably properties of compactness and cathh-comeettdness..
Section A.3 defines the language of Dynamical Systems, which our theory.
describe RNNs and to build
Section A.4 shows the key Algebraic Automata Theory results and notions which we use in our work.
Finally, Section A.5 and Section A.6 cover MLPs and introduce relevant RNN architectures.
A.1 Basic Concepts and Notation
We introduce basic mathematical concepts and notation required later sections.
A.1.1 Numeric Domains
We write B = {0, 1) for the Boolean domain, we write N = {0, 1,... for the natural numbers, we write No. = (1,2,...) for the natural numbers excluding zero, we write for the real numbers, we write R- for the positive real numbers including zero, we write Rx for the positive real numbers

---

excluding zero, i.e., Rso = R2 \. {0), and we write C = {(a,b) a. RR} for the complex Saabersswherts every pair (a, b) is to be seen as the complex number a + ib.
For i E N with m I n, we define the notation [i..]] = {i, i+1, ,..,,,,,)))) j). In the rest of the section, let Z be set.
A.1.2 Powersets
We write P(Z) for the powerset of Z, and we define P+( = P(Z) (0).
A.1.3 Tuples and Matrices
For n E N, the set of Z-valued n-vectors, or n-tuples over Z, Z f21..... .n) 4 E Z}. We typically write an element of Z" 2 (Z), : For m, N. the set of Z-valued (m x n))-ectors, or m X n matrices over Z, znxn (Z),.... 2m) 2s E ]n). We typically write an element of Zmxn as Z = (Z1, ................................ 7n)-
We use the compact notation Z|..g| to specify the set Z, x Zy resulting from the Cartesian product of the sets Z..... , Zj. meaning that they are contextually introduced by the notation.
A.1.4 Sequences
sequence over with indices C a function s: 1 Z' C Z,which we commonly present as (zi)xer where = s(i) for every E I. A sequence is finite if so is its index set, and it is infinite otherwise, When is an infinite sequence with index set the form / {m, m+1,.... we adopt a simplified notation and write the sequence (2))22m instead of (2))EE- When is finite sequence, the cardinality of its index set is called the length of s. The empty sequence, denoted by E, is the sequence having length zero, i... the sequence with indices I = 0. Any finite sequence with indices = [i...]] can be presented as the list 2;, 2;...., 2j by letting 25 = s(k) for every k E [i..j]: in this case, the sequence
also be written in compact form as [[{.]]] We write 7 for the set of all infinite sequences on Z, we write Zt for the set of all finite sequences all non-empty finite sequences on Z, and we write Z' for the set of all sequence of a given length f E N-noting that this definition of Z clearly corresponds to the definition given above of z as the set of all é-tuples over Z.
Z, we write Z for the set of
We often say that property holds eventually for sequence (z)).2m if there exists m' 2 such that it holds for the sequence (z))2mm. That is, the property holds for some tail of the sequence.
A.1.5 Strings
string over finite set > is concatenation (juxtaposition) of elements of Σ. Namely, a string an expression 01 with E Σ, for every i E [1..n]. In this context, we call Σ an alphabet, and we call each element o; letter or symbol of the string We can equivalently see a string 0202- ..... on as the finite sequence [I...) following the definition of finite sequence given above, and hence apply all notions already introduced for finite sequences. In particular, we have that the length of string 0102- is that & is the empty string, that E is the set of all strings of given length e e N over alphabet Σ, that E the set of all strings over alphabet Σ, and that E)+ the set of all non-empty strings over alphabet Σ.
A.1.6 Functions and Transformations
The image of a function f: X + Y is Im ( (x(=) C.. We say that f is an identity f(x) = x for every X, and we say that f is permutation if it is a bijection. A transformation of X is a function f X + X where the codomain coincides with the domain. Note that every identity transformation is also permutation, and hence it is sometimes important distinguish permutations that are not identities by referring to them as non-identity permutations.
A.1.7 Equivalence
For ~ an equivalence relation on Z, the equivalence class of z w.r.t. ~ is the set [=], == (=' E
z' z}. We denote by Z/~ the set of equivalence classes of Z w.r.t

---

A.2 Metric Spaces and Topology
We follow [Willard, 2012] as a general reference for this section, revisiting the notation. Let X be set fixed for the rest of this section.
A.2.1 Metries
metric, distance function, is function properties for every T, U; E X:
X X - Rss that satisfies all the following
a) d(z, y) = = x x=
b)
d(z, v) 2 0
(positivity)
c) d(x, y) = d(y, x)
(symmetry)
d) d(x, v) + d(y, z) 2 d( x 2)
(triangle inequality)
Notable metrics, relevant to us, are the following ones.
The Euclidean distance, L norm distance, is defined
L (x, ||x yll (x1 11)3 + (In yn)
* The discrete metric is defined as
{ if yy,
(x(x,))
if x
We will omit X from a metric when it clear from the context. For instance, we will write I,2 and D for 2 and Dx. respectively.
A.2.2 Metric spaces
metric space is a tuple S (X where d X X X + R is metric. Given metric spaces (X, dx) and Y = (Y, dy, an isometry between X and Y (or disttance-preeservingg (unncttsrrriinnfnntooonnno) is bijec- tive function f X + Y such that, for every 1, 22 E X, we have dx (x1, x2) ) = (f (x²)). When isometry exists, the spaces X and Y are said to be isometric. Intuitively, two isometric spaces are essentially the same metric space. Notable metric spaces, relevant to us, are the following ones, for Noo.
The Euclidean n-space 1
The complex n-space (C" I.?), seen as isometric to (R22, 1222nII'' L.?), by the following isometry:
f(a: + ibi, .... On + ib,)) = ((a), bi),..., (an, b,))
In particular, by the isometry above, all our results for Euclidean n-spaces transfer to complex n-spaces seamlessly.
We omit the metric when referring to metric spaces, since in the following sections we only consider Euclidean n-spaces (TR", I.2) and complex n-spaces (C", T.2), that are always equipped with the T,2
as described above. Thus we simply refer to them R and C", respectively.
A subspace dy) of (X, dx) is metric space with Y C X and dy given by restriction of dx to x Y.
We define the open ball (x, and closed ball B (x r) at x e X of radius r 2 0 in (X, d) as the set of points in X with distance and 5 < from x, respectively:
(x, = ty e X d(x, v) <r). Bx = (y e X d(z,y) sr)
A subspace (Y,dy) of (X,dx) is metric space with Y C X and dy given by restriction of dx to
Y x Y. We say that a subspace S C X is bounded, if there some x E X and oo > M 2 s.t. S C (x(r, M). We call subspace S C X is open in X if for all E S there is some 6, 0 s.t. open X.
6x) C S. S is closed in X if X \
Example 1. The open intervals (a, b) and (a, xo) are open in RR (with the usual metric). The closed interval (a, b) is closed in IR. The subspace {0, 2 2-n m E N) is closed in R, while (2-": N) is neither closed nor open in R.

---

A.2.3 Topology
The notion of open subspaces in terms of open balls defines topology any metric space, which determines what functions are contimuous. Formally. topological space is tuple (S, with S being the underlying set, and T S P(S) being the collection of open sets, such that S and 0 the union of any collection of open sets is open, and the intersection of any finite collection open sets is open. The open sets definition in terms of open balls for a metric space satisfies these properties. Many aspects of Metric Automata Theory could be easily restated in the language of Topology Theory, but choose more concrete setting, to make it more accessible.
Intuitively, the closed subspaces of X are precisely the ones which contain all their limit points, i.c. if (In)n2) S S converges to some limit E X, then E S.
Fact A.2.1. For metric space X, subset S X closed iff for all sequences (#n))21 S converging to 7 X we have that E S. (see $ $10, Cor. 10.5 of Willard [2012], as every metric space is first-countable)
Note that the notion of opennes/closeness is not inherent to the subspace S: it also depends on the superspace X, since the definition involves balls X. In fact, any subspace S S X is by definition both open and closed as subspace of itself, regardless of whether is open closed in X. Any time we use opennes or open balls, we need to excercise caution and be clear which space the openness referring to.
Example 2. Consider M = R2 and X R x {0} = {(z, 0) E E :2:22 E RJ. (-1,1) x {0} S X is an open ball (0, 0) of radius 2 in X, and thus open set. However, it is not M! For any 6 > we have [0, 0) (0, c)ll = c, but (0, c) & S, and so no open X-ball centred at (0, 0) is wholly contained in S.
open set in
In fact, any subspace S C X is by definition both open and closed as a subspace itself, regardless of whether is open closed in X.
(M', d') the set function f M + M' such that for all sequences (In))211 C M converging some E M, the mapped sequence (J(..)) M' converges f(x) E MM. The 6 definition of continuity, as well as the topological definition of continuity (Y C M' open + (-( S M open) are equivalent the metric space setting.
continuous function f (M,
Example 3. Let S be subspace of X. Then the inclusion map :: S + X, given by set-theoretical inclusion S C X, is continuous.
The topological definition of continuity makes clear the following:
Fact A.2.2. All functions f (M, d) - (M', dd) are continuous for a discrete metric space (M,
Next, we introduce two elementary notions in Topology and Metric Space Theory: compaciness and path-comectedness.
A.2.4 Compactness
Definition 9. A space X is called compact if all coverings of X by open subsets of X admit finite subcover. For metric spaces, equivalently X (sequentially) compact, all sequences X have subsequence converging to limit in X (see 17G.3 of Willard [2012]).
The following a characterization of compact subspaces of IR..
Fact A.2.3. (Heine-Borel) X C Ω is compact subspace iff. X is bounded, closed subset of Rd (see 17.9 of Willard (2012]).
Example 4. Subspaces (a, b), {a}, {0, 2 E N} compact in R. (a, b), (2- E N) are not closed, and so they are not compact. IR is not bounded, and so it is not compact.
Turns out that compactness, unlike openness, is inherent to the subspace, as demonstrated by the following theorem:
Fact A.2.4. A continuous image of compact space is compact (see 17.7 of Willard [2012])
Finally, Tychonoff Theorem tells us that compactness a property which preserved by cartesian products.

---

Fact A.2.5. (Tychonoff) The cartesian product of two compact spaces is compact (see 17.8 of Willard [2012])
A.2.5 Path-connectedness
Definition 10. A path in X from a to b a continuous function 7 [0, X such that 7(0) and (1) b. space X is called path-connected for all a, there is path from
cott--oonnetedeess partitions the space into components, which we will later think as atomic parts of the state-space for dynamical system. any continuous decoder assigning discrete symbols the state-space must be constamt on a path-connected component, see Lemma 22.
See Section 27D of Willard [2012] for the following:
3 there is a path from to b in is an equivalence. The equivalence classes of ~ are the maximal path-connected subspaces of X. Example 5. Any convex subspace of R is path-connected, in particular open and closed IR -bllls
Fact A.2.6. The relation ~ on X given by a
path-connected. (-1.0) J (0, has path-connecter components: (-1,0) 0) and (0. 1).
Just like compactness, path-connen nathhconnectedness is inherent property of the subspace, and is preserved by Cartesian products (see 27B of Willard [2012]):
Fact A.2.7. A continuous image of path-connected space is path-connected.
Fact A.2.8. The cartesian product of two path-connected spaces is path-connected.
A.3 Dynamical Systems
Following Knorozova and Ronca [2024a], we adopt dynamical systems as an general formalism describe all systems that operate by maintaining a state recurrently. This allows for treating such systems in uniform way despite their differences. In this work specifically, systems to formalise Finite Automata and several RNN architectures in Section A.6.
will use dynamical
Definition 11. A (dynamical) system U is the imput space, f X x U + X is the dynamics function, zu E X is the initial state, Y is the output space and X and f, h are continuous. In our analysis it will be useful to refer to the tuple D (X, U. f as the dynamics of allowing us focus on just the state transitions.
tuple S (X.U, f. Y. h). where X is the state space,
Y is the output function. We have that X, U, Y are metric spaces,
Given To E X, D defines a map from sequences of inputs (un)x21 S U to sequences of states (In)n20 X, given by
En+1 {xa, Un+1) for n
With this, we can define the sute-sequence function X U - X D(x, uI..) = En
D(xo. 2) No:
defines a map from sequences of inputs (un)n21 C U to sequcences of states (In)nz1 S X and sequences of outputs (yn)n21 C Y, given by
yn = h( un) = (D(oo 4[1..])): un.
Hence we say that S defines the function U + Y. with S(up..ni) = yn- In the special case that is independent of U. may define S(c) h(zu), extending the definition to S U + Y. Lemma 10 (State continuity). Let 5 U.f) be a dynamics, and for input sequence (u,) ( S
U and Fo X let (an) C X be the sequence of states
In = f Un))
Then In is a continuous function of Io, u1,..., Un for all n E I..N, Consequenily yn. = hilnns Un) also continuous function of zo. UI...., ., Uny for any continuous h.
Proof. By induction. Writing on (uI,,.... .,, Un) we have that
Fn+1 = [ 01..... ., Un), Un+1)
also a continuous function of 2o, U1, .,., Un+1-
5

---

The formalism of cascades provides flexible way to describe dynamical systems consisting of subsystems forming an acyclic network. Their flexibility will allows us, e.g,, consider not only feed-forward layers of SSMs as in Grazzi et al. [2025], Sarrof et al. [2024], but also more complex architectures with, e.g., blocks in parallel, and mixes of different types of neurons.
Definition 12. A feed-forward cascade Cs form of dynamics (X, U, with X X1 ...... X
and dynamics function of the form
f( Jn), (0% : x/p))
where
2/- = (2 (1..,......11..
We may see C' as consisting of dynamics D1,.... Dn where
Dj (X;U x X (t)
and write C = D1
Du.
Thus, the cascade is evaluated in feedforward fashion: input u, first the state of Dj is updated, then for all subsequent components D; the state of D; is updated based on u and the updated states of Di...., D--1. This differs from some recurrent neural network literature, where D; is updated based on u and the initial states of Di...., D;-1, i.e. the update happens at the same time for all components. We refer to such cascades as serial cascades.
Definition 13. A serial cascade C' is form of dynamics (X, f) where states are of the form X = X1 x ... Xn, and the dynamics function
the form
f((11...., u) (fi (11,,1),... u1),... : (Z un)), We may see C' as consisting of dynamics Di.....D Dn where
with u (u, 21 ..... 24-1)-
D, = (X,,U x X 11,
and write C= = D1 x .......... Dn.
Serial cascading can be achieved with feed-forward cascades, and the distinction between the two is irrelevant for our purposes. For details, see Appendix G.2.
In further sections, it will be useful to allow connection functions in cascade, transforming the inputs between components. will not alter the expressivity results, but allows us to e.g. define one canonical FI.IP-FI FT.OP dynamics, rather than family of Fr.IP-FI.OP-B like dynamics for every possible input and output set.
Definition 14. For dynamics D1, Da with D; = (X,;; U., Ji) for all E [1..2]. and for continuous i U - U1 and U x X1 - U2, we define the feed-forward cascade with input and connection
g. written 3. D1 2. D2. and the serial cascade with input i and connection g. written ix Di g D2 as the dynamics (X, x X22 f), (X1 x U, f") respectively, where f and f are given by
[(x1,, x2), u) = (x1,=<);
where
1 [1
J = (2 g(u, x1)),
and ((( x2), u) = (zi i(w)), f2(22, g(u, 1)). Note that for U₂ = U, x X2 and g = id, we recover the usual notion of feed-forward cascade and serial cascade/.
For dynamics D = (X,U,) and continuous function g 2 + U, we define the dynamics with input function D, = (x, Z, (x, 2) + fx, g(2))). With the notation from the previous definition,
note that D1.; D2.5 ب D1 9. D22 and D1,; & D2.g xD1 & Dz. In our expressivity results we will not care about how the dynamics of neuron interpret the input function, only about the induced transformations of the state-space. Thus, in further sections in proofs we will only consider feed-forward cascading without connection functions, without loss of generality, in order to simplify notation. Further discussion about serial cascades and connecting functions is deferred to Appendix B.5. The next lemma shows the intuitive fact, that it does not matter in which order we "connect" the components of the cascade. In the following propositions, will be useful to view a cascade D2
~ Dr, as (Di
Dn-1) D, for inductive proofs.

---

Definition 15. For dynamics D1, where D, (X,, Ut, for all i [1..2], write D1 D2 if X1 X2. U1 U2 and f2-
Lemma 11. The cascading operation is associative, i.e. have
Dm (D2 ~n D3) = (D1 ~n D2) ~a D3.
where 's' as introduced in Definition 15
Proof. Say we have D; = (X;,U U x X p,4) Ji) for i E 1..3. Both the LHS and RHS dynamics have state space X1 x X2 x X3 and input space U. Consider a state (Ii, #2, E X1 x X2 x X3 and input u U.
= fz (u, x11). zyy = fa(as, (f, x2,))) Also write fzx for the dynamics function of D2 D3 and fi2 for the dynamice function of Dj D2. Then the state update of the LHS system is as follows:
Write zi = (11, u).
(N's J2a (102, na), (u, ((1)))))
22,,
a (2lz, fo (I3, (u, 24 xb,
where the second line follows from the definition cascade dynamics for D2 D3, and the third line follows from associativity of the cartesian product. Analogously,
fIHI((E11 (2,, xz), u) = (112. forfss(en fa (u, ((2))
where 412 = f12((01,
Now, we have 2112 = (2)( = (z f2(22, (u, (u, = (z), and so
fRHS((01, 22, 22) u) (0'22: fo (23, (u, x(22))
(a' x42), fo (Ias (u, 24, x(,)))
(2 x22,2/)) x//)-
Thus both ways of composing the dynamics D1, D2, D3 results in the same dynamics function. 17
A.4 Algebraic Automata Theory (AAT)
We present extended version of the background on Algebraic Automata Theory given in the preliminaries of the main body.
Algebraic Automata Theory (AAT) allows for studying finite automata through the lens of algebraic notions such as semigroups and groups, c.f. [Hartmanis and Stearns, 1966. Ginzburg, 1968, Arbib, 1969, Dömösi and Nehaniv, 2005). Its fundamental theorem is the seminal Prime Decomposition Theorem by Krohn and Rhodes [1965], that shows how every semiautomaton can decomposed into a cascade of elementary prime semiautomata. One prime semiautomaton is the flip-flp. that describes the elementary system with the ability store and manipulate one bit of information.
Definition 16.
The flip-flop is the two-state semiautomaton defined
FLIP-FLOP == (fhigh, low}, (set, reset, id], 8)
where
8(g, id) =q 8(g, high, 8(g, reset) 1ow.
AAT often focuses on state trunsformations rather than on the transition function 8 of an automaton. State transformations are the functions 6- 5z) == ō(g, ar) obtained by fixing an input They allow us characterise semiautomata terms of semigroups and groups. In particular, the transitive closure of the state transformations of an automaton forms semigroup, and monoid group in special
7

---

cases. From this algebraic point of view, the flip-flop is characterised by the flip-fop semigroup. which is in fact given by the set of state transformations of FLIP-FLOP. All the other primes are characterised by finite simple groups, and for this reason they are called group-like. Specifically, their state transformations form a finite simple group.
Automata whose semiautomaton can be decomposed purely into flip-flops are called group-free, and they play a central role in our theory and in general, due to the following theorem whose proof also involves the celebrated theorem by Schützenberger [1965]) on aperiodic semiautomata, cf. [Ginzburg. 1968].
Theorem 12. The star-free languages is the class of languages recognised by groupfree automata.
All other automata, that do not admit the above decomposition, are called non non-group-frre, since their prime decompositions always include group-like semiautomata. They admit the following characterisation in terms of state transformations, relevant to our results.
Theorem 13. (Lemma 9 of [Knorozova and Ronca, 2024al') If a semiautomaton (Q, 2,E.6) is not group-free, then there exist Q' S Q and a E Σ such that the state transformation 6,- Q - Q is a non-identity permulation on Q'.
Our theory will extend the applicability of AAT to the study of general dynamical systems. And in particular to analyse the structure of such systems using algebraic means like group theory. A notion from AAT that is key our results is the notion of realisation for Mealy machines (cf. Definitions 1.14 and 1.15 of [Hartmanis and Stearns, 1966]).
Realisation describes how machine that actual names of inputs and outputs are not important in order to characterise what functionalities machine is fundamentally able implement.
imitate another machine after renaming of inputs and
We recall that a Mealy machine is a tuple (Q, Σ, 6, r,,) where (Q, (Q,2, 8) a semiautomaton, an output alphabet, and 0 Q x Σ + I' is an output function.
Mealy machine defines the mapping Q Σ+
given by
M(q, w) = 0 (DM (g. w-1).
where DM is the semiautomaton of M.
Given a (finite) automaton A = (Q, E 6, go. I',, 1),0). the associate Mealy machine MA = (Q, Σ, 8, 1, 0) is obtained by dropping the initial state from automaton A.
Given a semiautomaton D = (Q, Σ, 5) we define its canonical Mealy machine as M(D) (Q, E,,,T,,0, where [ Q E, and 0 id. Definition 17 (Definitions 1.14 and 1.15 of [Hartmanis and Stearns, 1966)). If M = (Q, and M' (Q', > 8', I', 8') are Mealy machines, then the triple (a, 4, () is called an assignment of M into M' when the functions
a a: - P+ E: E, ':
satisfy the two conditions below for every a E Q every of E ax()), and every E E.
I) 8' ('''' ((o) E a()(9.0))
II) <o (g' (())) ((
If an assignment of M into M' exists, then M' is said to be realisation of M.
The following results tells us how machine M' that is realisation of another machine M actually implements its behaviour. Any trajectory through M factors through M', with i and acting as the encoder and decoder, respectively, and with providing an initial state to start from.
Theorem 14. (Theorem 1.5 in $1.3 of [Hartmanis and Stearns, 1966]) If M' "','"'8'' D' 0') 1,,0 0) through assignment (a, C), then for all E Q Et realisation of M (Q, E, 8,1,
and d ax(z))
((D w), w_1 C 0 (D'(2), (()),
ie., M(o, w) = Ç M (1h. 1 (w)).
'Lemma 9 of [Knorozova and Ronca, 2024a] can be found in the appendix of its extended version [Knorozova and Ronca, 2023].

---

We will use the following version of the Krohn- decomposition theorem, presented in [Hart- manis and Stearns, 1966]. which uses the notion of realisability.
Theorem 15. (Theorem 7.8. $8, Hartmanis and Stearns [1966]) Let M be Mealy machine, with group-free semiautomaton. Then M can be realised by a machine with serial cascade dynamics, consisting of FL.I--FLOP components.
A.5 Multilayer Perceptrons
Multilayer Perceptron (MLP) is a tuple
= (d.n.UUYYYa,,,W.b))
where E Noo called the depth or number of layers, n = (n. 122, n3,, Da.....,,,,,,, architecture, U C R is the imput domain, Y C R is the output domain (or codomain), a: R IR is called activation function, 3 IR + R is called activation function of the last layer, W (W1, (...... Wa) with W, E R called weight matrices, and b (bi...., ba) with b, Rm.
Dd. m) is called
called bias vectors. Then, N defines the function f U C RR" + + C I given by the composition
fi ....o fa of the functions : IR. + P defined as
f1(x)) aWW, + b,) Vi (1.dd 1},
fa(x) B(W]x bb)
We often identify N with the function f. and hence see the network as a function N U + Y. The functions Sa called layers, with the first layer Ji called the input layer, the last layer Sa called the oulput layer, and the other layers called hidden layers. The (maximum) width of N is max n. Typical choices for the activation function a are sigmoid(z) = I+exp(-x) and the Rectified Linear Unit ReLU(z) = max(0, x). The same choices are valid for the last-layer activation function B; however, it computes the output of the network, it is often specialised by choosing 3 to be: the identity function (e.g.. for regression tasks), sigmoid (e.g.. for binary classification), softmax (e.g., for modelling distributions).
MLPs are universal approximators as long as their activation function a non non-polynomial, as established by several well-known Universal Approximation Theorems for feedforward neural networks, cf. [Cybenko, 1992 Hornik et al., 1989].
Theorem 16 (Universal Approximation), Let a be any non-polynomial activation function. Addition- ally, let X C R" be compact, and let f X C Ra - Y C R. be continuous. For every e >> 0, there exists a 2-layer MLP N with activation cuniionfunntton function a, and identity as last-layer activation function, such that the following inequality holds:
sup [1((z) - N <E zex
Note that ReLU and sigmoid are non-polynomial activation functions.
In light of the above theorem, in the rest we will focus on MLPs having non-polynomial activation function as well as identity as their last-layer activation function B. This will be relevant in all expressivity results for RNNs whose architecture includes MLPs-an as also discussed in Section A.6.
A.6 Recurrent Neural Network Architectures
We present the Recurrent Neural Network (RNN) architectures studied in the following sections.
Classical RNNs are networks of neurons with hidden state h E Rdditto and update rule of the form
h (1h,1,, for E dipput
where @ is commonly a linear transformation composed with a non-linearity, like sigmoid or tanh. We model such neurons dynamical systems, with hidden state taking values in X, and inputs taking values in U. The hidden state of the neuron at step may be available to other neurons in the network part of their input time +
In modern Machine Learning applications, notably NI.,, the networks are in the form of feed-forward connections, with learnable transformations between the neurons. Also some neurons may appear in

---

parallel, and some neurons might additionally include residual connections. Most generally, we can model such RNNs as acyclic networks, and for nodes , , consider the connection functions Wa.j. describing the transformation which is applied to the value going from neuron N, to neuron Nj. The network input also may given to Ni, after going through some transformation 44. As the network is acyclic, we may assume that there are no connection functions V1,5 for i > j. Finally, the imputs to N; are accumulated by some ag, Now, we may express the network as a feed-forward cascade Di ~ ~a DL. with D, (X,, U Xp..nl: ft), where X; is the state-space of neuron N;. U is the input space the network, and fi given by
f (I, = o a,, (x))) (,-,,(=--))))
This is how our framework allows to pull the details about the state-less transformations of the input or state-space into the dynamics function.
Classical (Vanilla) RNNs. Vanilla RNNs are networks where the state is updated through a linear combination of the previous state and current input, followed by the application of non-linear activation function. A prominent example of a vanilla RNN architecture is the Elman RNN, which is given by dynamies D (X,U, f) with state space X C Rstate input space U C Rinput and dynamics function
f(x, tanh (Ax x + A b),
where Ax pstatexstate is matrix defining linear transformation of the state, Au Retttexioppt is a matrix defining a linear transformation of the input, and b E igstate is the bias vector.
State Space Models. State Space Models (SSMs) are family of models based on linear recurrence with particular parametrisation. Notable ones are Mamba [Gu and Dao, 2023] and S4 [Gu et al., 2020].
To model linear recurrence in general, we introduce Linear Recurrent Dynamics, defined as dynamics D (X, U, f). with state space X C Kddtate input space U Kdipput, where K R or KK C, and with dynamics function
(x, A(u) x B(u),
where A(u) E Kdaartt X datate is the state-transitin gate and Buu) Kd is the input gate.
SSM architectures often combine linear recurrence blocks with linear projections, noneaiicasssses, residual connections and convolutions. Our theory can easily model such setups with cascade compositions introduced in Section Consider the Mamba block:
[ = SSM o o Conv o lineari (MI...))
V|1..n] = o linear2(M[1...)
[1..]] lineary linearg(:1...) X Vp....))
where the input sequence up...]] E U and output sequence op..n E Y are processed sequentially, each linear, is linear projection, is non-linearity, SSM is SSM block, Conv is a causal convolution, and x is glement-wise multiplication. Only Conv and SSM are stateful transformations here. In Figure 6, present it in the form of system with cascade dynamics.
We introduce a general class of dynamics as an abstraction for convolution blocks.
Definition 18. Finite Context Dynamics (FCDs) with context length l are dynamics D (X, U) such that their state depends only on the most recent inputs. That is, in view of Lemma 10, there is continuous function C: U + X such that
D(z, w) =
w-1)
for all x E X and U* with |w| > L, where is the i-th-to-last element of w.
The recently introduced model xL.TMM [Beck al., 2024] is successor of the LSTM architecture [Hochreiter and Schmidhuber, 1997], and it achieves performance competitive with transformer architectures. It makes use of both non-linear and linear recurrences. xL.STM introduces two types of blocks: sLSTM and mLSTM. In this work will focus the sLSTM block.
XLSTM.
10

---

Mamba block
SSM
U
lineari
lineura
Conv
SSM
SSM
lineary
Figure 6: The feedforward cascade structure Mamba block. Only Conv and SSM are stateful, so the cascade has 2 components. Structure on the left it presented in [Gu and Dao, 2023].
The state space of a sLSTM is R3, and the input space is Rd for some d 2 1. The dynamics function of the form (fc, n, h) (felle, n, ht, u). fn((e, h), fh n, h), u)), where
folle, n, It,, u) = (1, u)) c+ exp(li(k,, u)) (1,,(h,,,) u)) fal(c, h), u) ((ly(h, u)) n exp(((h
(,(c.,n,),.. Salte, n, h1, u) alooh, u)) fn((c, n, h)
where each 4 o, i, z, f is function of the form w a + Ts h b. for w. Rd. rs, R. ab is either exp or a, and is tanh.

---

B Foundations of Metric Automata Theory
In this appendix, develop the key notions of Metric Automata Theory within the 77- f-ffiiteneess framework.
In Sections B. and B.2 we introduce the basic properties of 17- 17-finite spaces and dynamics.
In Section B.3 develop the correspondence between 77-finite systems and finite automata, which is crucial to unlocking the powerful theorems of AAT. We provide the proof for Theorem 1.
In Sections B.4 and B.5 we import the notion realizability to continuous systems, via the correspon- dence with automata, and use to translate algebraic decomposition theorems into the setting of finintenees..
B.1 The Notion of n-Finiiteness
We begin by introducing n/-initeness, which is central notion of Metric Automata Theory and novel finite-precision framework.
Definition 19. Let X Z for some d 2 1. Call X f-fintte if it is finite union of compact, path-connected sets.
Immediately from the definition we have that am 17 17-finite space is necessarily compact in the case of metric spaces, finite union of bounded, closed sets is bounded and closed. The next result resolves the technicality, that the defining sets in the union
rj-finite need not be disjoint.
Lemma 17. Let X be n-finite. Then X has finitely many path connected components, say XI...., X shall refer to them as the 1-components of X.
and each of X3 is compact.
Proof. By def, X = - Y; for some compact and path-connected subsets. By induction on N: If N = 1, then the claim is immediate. Now, consider the inductive hypothesis for N 2 2, that X" - Y; has finitely many path connected components X1,... 1...... X each compact. The path connected components of X are then unions elements from {X, [X....., .....,,,,, ]- Each of these sets compact, and each such finite union is compact: clearly still bounded, and finite union of closed sets is still closed.
O
Example 6. Any finite alphabet q-finite, with each symbol in separate ny-component. The subspace
[-2, U [2] C IR. is n-finite. The subspace (-2, U (2) is not n-finitt, since it is not compact. The
subspace (0, 2- : n E N] is compact but not ry-finite, since it not a finite union of path-connected sets.
Both compactness and path cath-conmeetedness are preserved by continuous mappings and (finite) Carte- sian products, see Facts A.2.4, A.2.5, A.2.7, and A.2.8. This gives us the corresponding results for finite spaces.
Lemma 18. Continuous image of an n-finite space is n-finite.
Proof. Write X x= = X; for path-connected, compact sets X,. Let f f be continuous. We have:
N
f(x)
f(()
-=1
By Facts A.2.4 and A.2.7, each f(X,) is compact and path-connected. Thus by definition f(X) is finiiiite
Lemma 19. The Cartesian product X x Y space of n-finite spaces is n-finite. The n-components of X are the products of n-components of X and ny-compoeenss of Y.
Proof. Let X XI,..., X, and Y....,,, Y. be the C-components of X, Y respectively. We have X
Uh_ X1, = - - Y, and so
m
n
m
XxY ( x (UY) Y2) xUxXY, i=1
j=1
==1==1
12

---

By Facts A.2.8 and A.2.5 each X; X Y is path-connected. Therefore by def. X x Y is 17finiit. Moreover, the 7-components X Y are unions of the products X; Y. Now, fix i E [1..]] E [1-j]. Let Z be the n-componentof X x Y containing X; x Yj- consider the projection map X. As the projection continuous, the image, x (Z) path-connected in X by Fact A.2.7. Moreover, X; E x Thus, as X; is a maximal path-connected subspace of X, we have X; = x (Z). Similarly, considering the projection my X x Y + X, we have Y; = x (Z). Since X; Yj S Z. we therefore must have X; Yj Z. Therefore X x Y has finitely many y-components, and they are the products of n-components X and n-components Y.
xx X
Lemma 20. Let X be 7-finite, with n-comppoent X , Xn. For some å > 0 we have inf | vll 2 8 for all xxX,
Proof. It is sufficient show this in the that X has n-components, say X1, X2. Define
f: X1 x X2 + Ryo by (2) ) = || I2ll This is continuous, and so Tm f is compact, as X1 X2 compact. Since X1, X2 are disjoint, 0 & Im Thus 0 not limit point of Im and so for some 8 > 0 we have that (0,5) g I.
Corollary 21. Let X C Q be n-finite and (#n) S X converge in Q. Then (Fn)n21 is eventually contained in a single nycompooent of X.
Lemma 22. Let X be an r--finite space and Σ a finite alphabet. Then a function f X - E is continuous and only if is constant the n-components of X
Proof. (+) Suppose f : X + constant on n/coomonnents X. Let (#n)n21 S X converge to E X. Then by Lemma 20, (In)n21 is eventually contained in the same 17-ompooent as Thus fmn) (x) eventually, in particular (x..) (x) as > oc. Hence continuous.
(=) If f is continuous, then it maps n-component of X to path-connected subspaces of Σ. Therefore must be constant on 1-coomponents
B.2 Dynamical Systems and n-Finiteness
Definition 20.
We say that dynamics (X, K,U,J) are ff-fnite if both X and U are ---niite. A system S ypfimite its dynamics are ry-finite.
Example 7. Take Define f X x U + +X bb:
--1,-1/2] [1/2,1] and U {-1,0, 0 1}. The both X and are n finitee.
f(r,u) if 0 uf=11-1
Thus under input = 0 the dynamics function performs the identity transformation on X. and under inputs u -1,1 X is mapped to 1, 1 respectively. The dynamics (X, U, f) is -initee.
Note, that by Lemma 19, cascade of fi-finite components is itself -i-fintte
Lemma 23, Let D = (X, U, J') be q-finte dynamics, and h X x ~ Y be continuous. Then the image of h, Im h C Y, f-fittte.
Proof. Immediately follows from Lemma 18.
Lemma 24 (Path-connected = same state). Let D f) be dynamics. and consider
Do. vog E X, and input sequences (un)n21 (1/) (/)n>1 C and the corresponding state sequences (In)a21, (x', (2n)221 C X. Suppose that for all n 2 th my uly- and zo ~x 2/y- Then for all 2 1 we have that En ~x The Le..
D(Io up...) ~x D(2hy u(1..))
Proof. Let By 10, we have that there is for each n a continuous function x,, (2o, W1 u,) determining the nith state. Now, since each pair u, ui for i E 1..n is path-connected in U, we have
13

---

that (u1..n) and (u'...) are path-connected in U the path connecting them applies the corresponding 1-d paths pointwise. Thus by continuity of zn.
Tn In (T0, (uI..)) tnn - =xn(20: (u1..))
path-connected in X.
Corollary 25. Let S (X,U, ()) 1-finite system, and let us consider input sequences
(un)n21; (1/)221 CU such that for all n the and ui are in the same path-connected component. Then the corresponding state sequences (In)a21s )2221 S X, and the corresponding outpu sequences (3n) M2))21, (22)21 S Y are such that for all n In and x' in the same path-connected component of X and yn and yn are in the same path path-connected component of Im h
In light of the above results, we introduce the notion of equivalent sequences, for convenience in later proofs.
Definition 21. Let X be 7--finite space. Call sequences (Ix) 2: (1,)) S X equivalent, if for each n we have that Vnn and x' are in the same component of X. Call these sequences eventually equivalent, if they have equivalent tail sequences.
Overall, the notions of n-finiteness and 7-component have very favourable theoreticul properties. Any continuous mapping f + Y, with X and Y n-finite, is guaranteed to map every element of an 1)-component of X into a single y--ompooent of Y.
In the case of n-finite systems, this means that the dynamics function acts on the n-components of the state-space (referred to as 7-states) in the same way for each input within an n-component of the input-space (referred to as 17-inpu).. Moreover, every point within an n-component of the output function image (which is always finitee.). must be decoded as the same alphabet symbol. We formalize these properties in the following section.
B.3 Representing 77-iii Systems as Automata and Proof of Theorem 1
For A and equivalence on A, write A/w for the of its equivalence classes. For A write [a]a for the ---equivalence class containing a.
For 7--fniite spaces A, will write A for the set A/~Ay with ~A being the path-connectedness equivalence. For X,Y being finitt spaces, have by Lemma 19 that X x Y = x
Definition 22. Any fi-innit dynamical system (X, U, f, zg. Y, h) defines its canonical automa- ton
As UX, [au] h,) Similarly, any f-ninite dynamics D f) defines its canonical semiautomaton Da ()..
Note that by Lemma 23, Im h is indeed finite. F: (X)
(X) is defined as [x]~xx [u]] + [f w))~x. T X x T Im h is defined as [x] [u]] may + [h(z, u)]~ This is well defined
by Lemma 25.
For 1y-finite dynamical system $ = (X,U. Jo. Y, h). define the canonical regular function 1 Imhh to be the function defined by the FSA As. The following lemma shows that the dynamics of the canonical automaton determine-up up to path-conneetednnss: the dynamics of the system.
Fs:
Lemma 26. Let = f) be r-finite dynamics, and DA be its canonical semiautomaton.
Then
DA (a (w]wv) ((p())(<(<<o>>>>>
[D(zo, w)
Vu E U*
(1)
where [w]~y E U* denotes the word with each letter of w replaced by its equivalence class.
14

---

Proof. By induction on the length of w. For the base case = we have DA (10ol (Elmu) DA ( [ and by definition ((ro, E) = zo. that [D ~x [
Now, suppose for w E U we have DA ( (w]-o) = [D w) ~ and let [w)wor E U. Write w(u)~g for the word obtained by appending [w)~6 at the end of w, we have
D Da(uol>xx [we]>o] = (TDA((zolas) [w]~e)) (2)ww)
(([D(zo) (zo. w) Juy (alwo) by def. of [f (D(oo, w. u) 1ax
(ara, wu) ~x
Thus by induction the statement holds for all w E EU*
Lemma 27. Let S be a u-finite system and Fs be its canonical regular function. Then, Fs is implemented by S with encoder enc U U given by [u]=e u' with u' E [u]-u chosen arbitrarily, and with decoder dec: Im h Im h, given by M
Proof. enc continuous, since U is a finite alphabet, dee continuous by Lemma 22, Let DA be the dynamics of Ag, and let D3 be the dynamics of S. Then we have
Fs(w) h (DADDDAAA (Da(Iro)>x) w-i)
Yu E U
where w denotes the last symbol in word w. Now consider w E (V/=r)* and write [u]=w for W-1- By Lemma 26, we have D (<rll>x w) [Ds (vo: [nd(w))] so that
DA (1 w), h Ds Ds(2oo (s( -x |u]mo u' enc(lu)~e) E [w]=u
h Ds D (wd(w)) -x |u')ar
by def. h
h Ds((z (nco, ut
Tm
h DDs( (Ds(Fo,cnc(w)) (nc(w)) end (w_
Im
S(and(w))
dec S (end(ww)
Im
This concludes the proof.
Lemma 28, Let q-finite system S = U, f. No. Y.h) implement function F Σ+ with encoder enc Σ > U and decoder dec Im h + т. Then there are (continuous) functions enc' + U and dee' .lmh h + such that
F(w) dec' a Fs(end Ye E+
where F's: (U)+ (Imh) is the canonical function for S.
Proof. Define enc' as o + (enc(o)) for all a E Σ.
As for dec', define it as [v]=ım + dec(y). This is well-defined: Consider yı, E Tm such that U1, y2 E [y] [y)=m=* Since y/, 1/2 are path-connected in Im h, by continuity dec Im I we have that h hyy))) ). h(y2) are path-connected in I'. Therefore necessarily h(y1) h(y2).
15

---

Let As be the canonical FSA of S. Denote the dynamics of S as Ds and the dynamics of As as DA- By Lemma 26, we have
DA (a(l
(2s [Dss(rc,cn(w))]_ Vw E
Thus we have for all w E Σ+
dec' FFss (nnc (w)) dee' oh DA (Izo]~x enc' (w)( enc' (w-1))
doe' oh [Ds enc(w))) ~x [onc(w[>)]
dec' [M1 Dss((to enc(w)) eno(w-))) mmm
dee o5( (enn(w))
Finally, enc' and ded' are continuous, since their domains are finite alphabets.
Theorem 1. An n-finite system S can-iimpemmnt the same functions as its canonical automaton, which are necessarily regular.
r, with encoder enc Σ + U and decoder dec : Y + r. By Lemma 28, we have that the canonical FSA of S, say As = (X U. J, [zo]~x Im/, h). implements F with encoder enc' and decoder dee'..
Proof. Suppose
U. zo. Y.h) implements function
Moreover, consider the FSA (X, E, 8, [x0]~xx I' 0), where 8: X x E + is given by
[[1]~~x σ) = [[xx]=()e))))))))))))))))) enc' (o))
and 0 X x E + [ is given by
[[xx)~x,0] 0) dee' o <[([=)>> enc
Then we have that F(w) = A' (ww for all w E Σ+. Thus F is necessarily regular. Now, suppose that As implements function F : Σ r, with encoder enc Σ - U and decoder dec Im h - r. By Lemma 27, S implements Fs with encoder enc and decoder dec. Thus we have the following: for all E Σ
F(w) dec As (enncww))
dec Eis( enc(w))
dec dec
(enc enc(w))
so that S' implements F with encoder enc enc and decoder dec odec.
B.4 Algebraic Theory of F-Finite Systems
The connection between finite systems and canonical automata is extremely useful. It gives way to employ the powerful characterisations and results of AAT to any finiitt system dynamics. Namely, we can extend the notion of realisability to continuous finite systems, via the canonical automaton.
Definition 23. We say that n-finite dynamics D' are a realisation of r-finite dynamics D when M(C(D)) is realisation of M(C(D)) of D.
that automaton A' a realisation system A, if the associated machine MA a realisation of of the associated machine MA via assignment (a.4, {), and the respective initial states z/y 2g such that 2 E a(2))-
Say that finite system S' is realisation of system S, if Agr is realisation of As. where As, As are the canonical automata.
The notion of realisation for machines is transitive. See $1.3 of Hartmanis and Stears [1966].
16

---

Fact B.4.1. If M is realisation of M' and M' is realisation of M", then M realies M easy to see that the notion of realisation for dynamics and systems also transitive.
Lemma 29. Suppose that semiautomaton D' is realisation of semiautomaton D. Then
for any machine M with dynamics D, the canonical machine M(D") of D' is a realisation of M, 2) for any automaton A with dynamics D, initial state can be picked for M(D') such that the resulting automaton is a realisation of A.
Proof. Say D = (Q.E, and D' "'..''8') Suppose we have an assignment (a, (,5) from D E' + Σ
to D'. That is, -
Let M (Q, 0) be Mealy machine with semiautomaton D. The canonical machine for D is
M(D') = = -000=//2,,,.0'---000000
id)
Define Ç': (Q' ) + by Ç' = O Ç. Want to show: (a, 4, (") give an assignment of M into satisfied.
M(D). We already have that the condition
Now, for any y E Q a E Σ and q' E aQ)) we have that ( (q' (()) = id(q, σ) og, since (a) give an assignment of D into D'. Thus
<' o 0' ('d,', (())) = 0 0 o (q, 0(q, o)
So (a, 4') also satisfy condition II). Thus the 1) part of the statement holds.
Now for the part 2): Let A (Q, E, 6, qo. r, be system with dynamics D. By part 1), the
associated machine MA = (Q, r. qo- r, 0) has some assignment (,,4, into Mp a(xg) ) is a non- empty set, and so we may arbitrarily pick a/ E a(zo). Then the automaton A' (Q', > 8 % Q' >", id) obtained from setting initial state z for machine Mr. by definition is realisation of A. O
We have the following proposition to connect our notion of dynamical systems with Algebraic Automata Theory.
Before proceeding, we remark that Definition must be made fully precise by saying that a decoder is function dec Im h I where h is the output function of system S, (rather than function dec Y + r).
Theorem 30. Let S and S' be n-finite systems, and As, As: their respective canonical automata. If Agi is realisation of Ag. then S' can implement all the functions that S can implement.
Proof. Say we have Ag
Im h) and Ag (X),
U S 2 Im lm)
Say that an assignment of Ag into As is given by a X P U - and Ç Im h h. Let Fs (U)+ - Im h be the canonical regular function for By Lemma 28, suffices to show that Ag can implement Fs.
Define the encoder enc + U as enc = and decoder dec Im + Im h as dec = Ç. Let D. D' be the dynamics of As,As resp. By Theorem 1.4 in $1.3 of [Hartmanis and Stearns, 1966]. we have for all x' E a(aa) and w (U)) that
(DD(To, w), w-1) = (D'(s', ((w))))(ww()))) ((w-)).
Thus, for all (
have
Fs(w) = As(w) = Th D(D(oo w) w-1)
= = V D' ((w) ,e(w
dec o S' (' (enc(w)).
This concludes the proof.
17

---

Example 8. The reverse implication to Theorem 30 does not hold in general. Consider Σ = E' = { Q == b}. Q' = {a} and unary dynamies functions Q x Σ - Q defined as 6(q. 0) 9 for every q E Q, and depicted next.
And similarly 8 x Q' defined as 0' q for every Q', and depicted next.
Define system S (Q,E, a. = Q. 0) with 0 (1,0) + y, and system S' (Q', M, 8', 40 = a, = Q") with 0' (q.0) -
The only possible state trajectories for either systems are the constant trajectories In 20 = a and 5 2/ a. Thus, a function Σ + can be represented by either system if and only it is constant. So we have that both systems implement the same functions.
However, there is assignment (a, 1, () from S to S'. This is because I' is singleton, and any potential ( 1 + must be constant. At the same time, it must hold that ar(a), a(b) are non-empty and
(oold', 0(a, Vy E a(a), Ço B( (())) = 0(b, = b Aa E ab))
This is contradiction, as ( must be constant.
Theorem 31. Let D, D' y-finite dynamics. Suppose that a realisation of D. Then any function implemented by system with dynamics D can be implemented by some system with dynamics D'.
Proof. Let DA (X,U,) and DA' ( (',,,') be the canonical semiautomata of D and D', respectively. Then A realises A
Let S be system with dynamics D implementing function F. Its canonical automaton As has dynamics AA and so by Lemma 29 there is an automaton A' (X', U' T Fo, 1V,0", 0') with dynamics DA which realises As.
Consider the system S' (X' U f 2 U² id), where oi X' is s.t. [ Ty Its
canonical automaton is As ( U F " x U id)). As realises A' with the assignment X P g.b. v' + ( c: T + T' g.b. 7' गे and finally Ç X' T' I' g.b T.. Thus by Theorem 30, S" can implement all functions that S can implement. O ( T - (T
B.5
Cascade Decomposition and Finite Systems
In this section bridge the gap between the AAT decomposition results, which apply to serial cascading, and our qifinite framework, which focuses on feed-forward connections. We begin by showing how taking the canonical semiautomaton 'commutes' with feed-forward cascading.
Lemma 32. Let D
Dr, be i-finite feed-forward cascade dynamics. Then we have C CD1 ~ ...... Dn) = C(Di) ~ C(Da),
where is as per Definition 15.
Proof. By induction, it suffices to show the statement for 2.
We have D1 (X,,U,f1) and D2 = (X2, Un x X1, f2). Now, C(D,) X1,U1,f1 and C(D2) = (X2, U, x X1, F2). Note, that here we use that, by Lemma 19, (U1 X1) = U1 X1.
18

---

Thus, we may write the cascade
C(D1) (X1
where f is the dynamics function of the feed-forward cascade ((1,) ~M C(2)). At the same time, writing D1 x D2 (X1 X2, J'), we have
C(D1 ~ D2) [x x X2 f,,)),
where again we use Lemma 19 get (X1 X2) x X2. It remains to show that f f'. For [m]]~x, E X1, [ [w]=er we have
f ((1z1>>x, [02l~x,) [alwe,) = (11(lr)xx, (ulwo,),
T2(12el~xx ((u)uu, F2((a1ll (ul=e,))))
([i((r) [f2(12) (u, fi f1 ((l1,u)))) w)))]
[(fi un) f2 (u, fi w))) xxxxx2
[f'((11)22) m) = J (mm))x (22)~xa) (ulwor))
=7 (1(02, xxxxx [ulwer)
~ NNIX82
This concludes the proof.
Note: we treat objects such as X, x X₂ and (X1 x X2) identical, even though one is product of equivalence classes, and the other an equivalence class of a product. However, from Lemma 19, can identify the two in natural way, that is in a way that is consistent with applying functions component-wer
Next, we show that cascading interacts well with realisability, up to introducing connection function.
(X, U. fi) are such that D is realisation for Di- h. for each E [1..2]. Then, for any feed-forward cascade d. D2 ~ D2 with imput and connection h,
Lemma 33. Suppose D, =
h there is continuous function g Uf x X( + U22 such that D 3, D22 realises i, D ~4 D2-
Proof. Let (as, ( St) be the assignment of M(C(D.)) = (X,,U.,,,,, x U,,id) into M(C(D))) U,, and = id, i... we can consider the usual feed-forward cascade D1 ~n D2. by replacing D1 with D1, and D2 with D2 In that case, we have U2 U1 x X1.
x U, id), for each i [1.2]. We assume w.l.o.g. that h id
Define g : U X - U2 given by x(") = 12(u, x)) E U2 where (a, (( X1 U Uz.
Define
a: :Xi X2) + PX xX
as aF = (1 azz
+U,+
as 4=
x x
as <(<') 25), u1) = (a, b, where (1,c,a) So (2 x(1(,
Let (I), E X1 X2, E U, and (I, E a(T))T))) Let f and f' be the dynamics functions of C(Di) ~ C(D2) and C(D() ~ C(D)), respectively. We have that (. = (T -
). where
_ 1_ne = (1 E (f,
19

---

by Property I) of assignment, and
22 T2 (1 ((((T),)(( k(,w)w))
Now, by Property II) of assignment we have (i (1 i(u)) (Ji ū1), un), since 2een a1 ( (21, Thus
2 new = J2 (22. ( E1)) E az (2 (TI, [T,,,,(
So. altogether (I L mow) E (F u1)). so Property I) of assignment is satisfied. Now
Fznwww ((T)) (a.b,c)
where (b,c,a) (on)=C((z))
Co = new If ((((u)); 24 (. Co (2 (2 12 (ui, J (x m))) Thus
( 22 m. ((TI)) (
and so Property II) satisfied. We may now choose a continuous g' : Uf x X + U22 such that g' = by Lemma 22. Then we have that C(D2gg = C(D))g Overall, the cascade D ~. D22gi realises D1 D2.
The decomposition theorems of AAT are stated for serial cascades, while RNNs in practice usually work with feed forward cascades. In Appendix G.2, we show how D1 k D2 can be realised by
D1 21 Rx
38 D: for some continuous functions 91 92. and the repeat dynamics Rx over state-space
X
Dr.
Definition 24. The repeat dynamics on state space are the dynamics Rx = (X², Xx?,X,ya rx),, where Fx ((oold #now); 2)) (Jnow, x))
Thus we have that with initial state (a E X2 and input sequence (u,)221 E X", the state sequence is (sn = (In-1, E (x with x- = a, Fy = b. Note that a repeat dynamics is Finite Context Dynamics.
For finite spaces, Rx be decomposed in terms of 2-state repead dynamies.
Theorem 34. Let X be an rifinite space. Then the repeat dynamics X, Rx, realised by ford-forward cascade of the repeat dynamics R2 on 10.1}.
Proof. Let XI....,X X, be the n-components of X. We can think of the canonical automaton as the repeat dynamics on X, Rx (X" ,x,x).
Consider Cn l4 Dj f D2... la Dn (f0, 1]2xn X, fc), with D; = Rg for all i [1..]].
and with fi X {0, 1] {0,1} given by
M(z,) = 10 i [1 if
Thus, each D2 works in parallel, treating inputs T. as 1, and others as Then we can retrieve the state of Rx by checking which Dę has 1 at the old position, and which D, has 1 at new position. This corresponds state (z,,
The assignment this corresponds to is the following: define X² + P+((0,1) 1)2") by
a()),,,))) = (Fey), where Fi, E {0, 1] s.t. F, = [F = and remain-
ing entries are all 0. We also define i X X as the identity, and ( (0, 1]2xn X x" X
as mapping (Fi,, 7) + ((1,, with other inputs mapped arbitrarily.
20

---

Altogether, we have recipe for proving positive results. It is sufficient to show that an architecture can realise FLIP-FLOP, to show that it can implement all group-free functions with serial cascades. it further can realize R2, then it can implement all group-free functions with feed-forward cascades.
Theorem 35. Suppose that q-finite dynamics D is realisation of FLIP-FLOP, and 1-finite dynamics E realization of R2. Then werd-fo cascades of D and E. components can implement all group free functions.
Proof. Let F be a group-free function. By Theorem 12, F implemented by a serial cascade of FLIP-FLOP'S s, say C. By the construction in Appendix G.2, we have that C' is realised by forwaforward cascade of FLIP-FLOP's and repeat semiautomata, say C². By Lemma 34, each repeat semiautomaton is feed-forward cascade of R2 components. Therefore C' is realised by feed-forward cascade of FI.I--FI.P's components and R2 components, say C", By Lemma 33, feed-forward cascade of D) and E components realises C", say C" Thus, by transitivity of realisability, C" realises C, and thus by Theorem 31, C" can implement F.
21

---

Transition in e-robust dynamies
2 (X,)
u
X2
Figure 7: The image of n--component under e-robust transition lies inside the target coommpnnet, within e-distance of its boundary.
C Robust Systems
In this appendix we introduce central notion of robustness that allows us extend Metrie Automata Theory to the study of concrete inite-precision implementations.
Arithmetic operations with floating point numbers difficult to analyse, since addition and multipli- cation are not exactly commutative, associative and distributive. Thus, for example, the recurrent form and the convolutional form of the SSM update are not exactly equivalent (also noted by Merrill et al. [2024]-see footnote in Definition 2. A theoretical framework which specifies an explicit datatype either is hard to analyse, introduces additional simplifying assumptions.
The central notion that allows us to extend Metric Automata Theory to the study of finite- saite-precisio implementations is the notion of e-robustess. Intuitively, it describes stability of the dynamics under transition perturbations.
In Section C.I we prove Theorem 2, thus showing that robustness provides a way to connect 17- finite systems to their floating point implementations on real-world computer architectures, without requiring to commit to any particular standard of floating-point operations.
In Section C.2 show that robustness provides stability under perturbing the parametrs of model which describes the dynamics. We will later present a strongly robust dynamics based on the sLSTM model, which uses particular choice of parameters. Our results show, that in such cases the parameters may be perturbed by some amount and the robust system will retain its behaviour.
Lastly, in Section C.3 prove Theorem 5 and further describe what kind of connecting functions are required for strongly robust fi-finite cascades, by showing that 2-layer MLPs suffice.
Robustness marks the departure of Metric Automata Theory from Classical Automata and Formal Languages Theory, allowing us to study phenomena that not occur with discrete state-spaces.
For completeness, we restate Definition 2 paying closer attention to the role of inputs in the notion of strong e-robustness.
Definition 2. For > 0 and X C Qx U S Su dynamics D (X,U,) are e-robust (in Ωx if. for every x: E X and every u E U, it holds that Bax (f(x, c), S X-iee,, y X for all y Ωx s.t. [I, u) - yil S c. Furthermore, we say that dynamics D are strongly c-robust (in Q and Pty) they are e-robust (in (xx), each n-component of X contains an Ωx-bball of radius at least e and each n-component of contains an ball of radius at least e.
Note that the property of robustness with respect to the ambient space Ωx which contains the state space X. Thus, it is possible that dynamics is e-robust w.r.t. some ambient space (e.g., R), and not e-robust w.r.t. another ambient space (e.g.. C). This captures the property, that for fi-iinte dynamics, function approximating f within and taking values in Ω will implement the same transitions.
Lemma 36. Let C = Dj ~s me Dn, be cascude, with D; (X;,U x X Si) and X, S D2 U C Dy. Then C is (strongly) e-robust w.r.t. Ω x ... x Qu if Dr is (strongly) e-robust W.r.t. Ωt for all i 1..n.
22

---

Proof. By induction, it suffices to show the statement for n = 2. First, suppose that D; is c-robust for i 1,2. Let (2), E X1 X2, u U and take (v1. E 22 x G2 s.t. Ilf (Zz 22), (y), 32)ll2 S e. We have, by def of cascading
f((11, = (2)
where 01 = fi u), 2l - f2 (2),
By definition of the L2 norm, since [| x2) - (2) S we also have
|| - yıll S and || y2ll -
Thus, by e-robustness, we have that yr E X, for E 1,2, and hence (31, 82) E X1 X X2. All together, C' is e-robust w.r.t. 52 x 52..
Suppose further that D1. D2 are strongly e-robust. Let Z be a n-component of X1 X2. Then Z is of the form Z1 x Z2 for Z, n-component of X,, see proof of Lemma 19. We have by strongly- robustness that Ba, (Zg, c) S Z; for some 2; E Z,. By triangle inequality: Ba, xft,
S Zi x Zz. Finally, the input space of D1 D2 is the same the input space of D1, so by strongly-robustness we have that each n-component of contains a closed Oy-ball with radius c.
Ba, (z BB, (22,
C.1 Finite Datatypes and Proof of Theorem 2
We now consider approximations of dynamical systems using finite datatype D C Q. D can for example represent the Python float type. We simply consider D as a discrete subset of Q abstracting away the details regarding arithmetic properties of such datatype.
Definition 25. A finite datatype is a set D S Ω = I having finite cardinality. A finite-dataryp system S is then a system whose input, state, and output spaces finite datatypes, and whose dynamics and output functions are implemented using floating-point operations.
implementation
Definition 26. Call set S an c-covering of X S 92 if for all x E X there is a E $ s.t. ||x - s|1 S c.
Definition 27. Define int {O...., 2p - 1} to be the p-bit unsigned integers. Define int, = (2m-1.... ".....2p-12 - } to be the p-bit signed integers. Define DD, to be floating point numbers with 2p- significand and p-bit exponent:
Dp 2 2 :88 int2p; e intp
Similarly, define D2 to be floating point numbers with p bits of integer precision and p bits of fractional precision:
b 2D intp. b intp
D' a
Lemma 37. X 9 Rdd be compact. Then, for sufficiently large, i.e. with sufficient precision. DVd is e-covering X. X.
Proof. X is compact subspace of Ω and therefore bounded. So, there is some integer k: > s.t. X [-2* 2* 1jd There also some integer / s.t. e/vd 2-1 Take p 2 max(k, (). The set ID, is P-cver of 12-P, 2 1]. Now for any x E X C [- 20,2" 2 1]d, we have that for each i 1...d there is yı E mY s.t. [x]] Val < P Therefore, writing y [-22, 2 1] for (y1....,ya)
| wl1
Σ
[oc] lwle Se
Therefore (I)))d an e-cover of X.
Lemma 38. Let C Ω Red be compact. Then, for p sufficiently large, i.e. with sufficient precision, Dr is e-covering of X.
23

---

Proof. By the previous Lemma, for some we have that D/ is an c-cover of X. We have for each E intp, b int,:
b
2 a
-P
2
2
Now, 2 + 2 - 2 and 2 + - 2" 2p +2 < 2 so that 2 + E
1- Since p+ < 2P+1, we have p E int,+1. So, D' pp+1, and therefore Dp+1 is also an e-cover for X, for sufficiently large
Definition 28. Let X, U be r--inite spaces having components Xp..r) Up...) and subspaces X' C X, U C U, respectively. Let us consider dynamics
D (X,X, and (X',
We say that dynamics D are simulated by dynamics D, with most if have that the disjointness condition (C1) holds for every E [1..r], the disjointness condition (C2) holds for every j E [1..s], and the approximation condition (C3) holds.
(C1) x' x'nX, (C2) U (C2) NUJ 0,
(C3)
sup 1f(x, u) f(x, u)ll c. xE uEU!
Lemma 39. Suppose T--fintte dynamics D = (X, U, are e-robust, and simulated by n--fnite dynamics Đ (X', U", 8) with error Then D is realisation of D.
Proof. Consider the canonical semiautomata DA = (X,U,) and DA = = (X-UU,77
Define X + P
((="))))((1'1--ppp E EX' E [x]~x}
which is indeed non-empty by definition of simulation, and well-defined as X' C X, and so if Ij ~x zi then also 24 ~x 2/2- Also define e: U T' U'by by
((u)~o)= [w'Iwg where u' E U" ( [m]~e is arbitrary,
and <: (X' U + X x U) by
<(112') [M] (u)lrrr)) = ([I']~x Sox,:u''T [u(]~u)
is indeed well-defined: suppose x4, 2h E [x'] and u', u/ E [u'l Then since X' C X and U' CU we also have o1, 2l2 E [x']ax+ since oi ~x 2l2 and un u/ E [u'lees since un ~y u/z
Now, (a,4, () is an assignment of M(DA) into M(Da): for [x)>xx X and [u]=o U. and for all [a'] )xx E <((x)~x) we have
I' [(x' ((ul=e)) = [f' ('',,')) (z) where [u'l~rr = u(u)me)
On the other hand, we have
a[[([x)~x: (u)=o)) = a([((x w)rx))
We have that x' [x] since [x'] a((x)xx) We have by simulation with error at most
(I f(x', 5'
and so f'(z'u") E [f w)]-x, since D is e-robust. Hence [[e")>yrs<((ul> e ([[=]]>x[[u]_p Thus Part 1) of definition of assignment is satisfied.
Moreover, we have
((u)~rr)) ((00~)))((())=p))))))
(|=')~x [w']=o) fcllxx>(u///
so that Part II) of the definition is satisfied.
24

---

Ωx
1|0
ull S
bal
22
X3
Given sufficient precision, the transitions of strongly e-robust dynamics can be realized with approximate dynamics on finite datatype, which gives a c-covering for the space.
Figure 8:
Lemma 40. Consider n-finite dynamics D (X.U,)) s.t. each component of X and U contains closed ball of radius (in S2x. By resp.)
Then given datatypes x C Xx By S U with sufficient precision, there is a function f: Dx x By + Dx s.t. D0x,DU. f) simulates (X, U, with error e.
Proof. Suppose IDx is e-covering of X, and ID is e-covering of U. Let XI, X 2 1 be the connected components of X. Let 1..r, we have by assumption, that for some Iạ E X;
Bla,, 6) C X; Since DDx is an e-covering of X, there is some d, E Dx s.t. ||2; dell S 6, and therefore d; E B(x;, S X,
Similarly, there is an element of Dy in each component of U. Now, we may construct f as follows: for x E x and u By
f(r, u) = arg min ly f(x, 4)ll vEDx
with ties broken arbitrarily. Then, Dx is e-covering of X, [1 [xx S as desired.
We now have the setup, and necessary results for Theorem
Theorem 2. Every r-finite system with strongly robust dynamics can be implemented with floating- point operations, given sufficient precision.
Proof. Apply Lemma 39 and Lemma 40 to obtain a realisation of S using a finite datatype, e.g. using Dr WY for sufficiently large p.
C.2 Parametrised Systems
The stability robust dynamics can also be a desirable property in the context of learning. Consider parametrised model describing the trained model. If the system described by the model is e-robust. and it sufficiently smooth with respect to parameters, then perturbing the model parameters will not change the behaviour of the system. Thus robust system is intuitively more likely to be attained by a learning algorithm.
Definition 29. Let f θ x 22x x Oy - Ω be continuous. Write fo for the function f(0, - dynamics parametrised by θ of the form D, = (X)U,fo).
Theorem 41. (Corollary 36.20 of [Willard, 20121) A continuous functions a compact metric space X uniformly continuous, that is for all 6 > there exists such that for all x. y X
|| - wl1 I 8 = lif(z) - f(w)l <
Theorem 42. Let vy-finite dynamics === (X, Sa) be parametrised by Q and & be compact. Suppose Do is e-robust (w.r. 2x)) Then for some 8 > O, we have that for E O s.L. ||0 - pll S 8 the dynamics Dp = {X, U, fp) is well-defined. Moreover, for any system So with dynamics Do, the system Sp obtained by switching out Do for D, has the same canonical automaton.
25

---

Proof. Since Dg is 7-finite, we have that X and U are compact. Thus the Cartesian product
+ x X x U is compact. Thus, by Theorem 41 for all >> 0 we have some 8 >> 0 such that for all (0, u), (0, Jr u) E θ x
[1(0, x, u) 2,, u')ll 58 = Ilf 2, u) f(p,'', se
Now, take P E 0)). We have for all x E X and u U that
110, u) - (p. x, will = 110 اlم S 11, - [(p u)ll Se
Thus f(p, x, u) E B(f x. u), c) S X, since Dg is e-robust. Moreover, letting X1..,, X, be the components of X and U1,-., U. be the components of U, have that X i X; + 0 for i E 1.r and U UNU, for E 1..8. Thus D, simulates Do with error 6.
Now, the canonical semiautomaton for Dg is (X, U. and the canonical semiautomaton for Dp is (X, U. Jp). By Lemma 39, we have that To and Jp give the same transitions. Therefore the two semiautomata the exact same. Taking So, Sp as in the statement, have the same canonical automaton.
that they indeed must
C.3 Robust Cascade Decomposition and Proof of Theorem 5
Coming back to connecting functions discussed in Appendix B.5, we have the following refinement of the result.
Theorem 43. Let D be strongly robust f-finite dynamics, which are a realisation of FLIP-FLOP. Then all group-free functions can be implemented by some strongly robust serial cascade of D components. Moreover, the connection functions in such cascade can be given by depth-2 MLPs.
1) is strongly e-robust. By Theorem 35, for any group-free function F, there is a serial cascade of D-components which can implement it. By Lemma 36, is also strongly robust. Say, C = gt D1 24 Dz = (x", U", fc), with U an 77 7-finite space. D, = D and 9i U X
Proof. Say D = J)
U.
Let UI,...,US, Un be the nj-components of U. By strong robustness, for each i E [1..m]. there is u; E U, s.t. (w) S U, By Lemma 22, we can w.l.o.g. assume that gi has its image in {ui...., Un ) while still inducing the same mapping U' x XX U.
By Theorem 16, there is a MLP N; Qo x x + Oy which e-approximates gs, since U' x X 1- is
compact and gi continuous. For (u', ,I,,,,,,, x1-1) U" x X we have si( 21, "i,...,;;-.!! vi-))) = uy for some j E [1..n].s. so
((uu, $1, "I,,, E Bau (uj,e) c) SU,
Thus N; sends elements of U Xi-1 to the same n-components of U as gi- Moreover, N₂ is continuous.
Overall, the canonical automaton for 2, D1 ..... E4 Dr, is the same as the canonical automaton for N1 D, No N.... N2 Di.- Thus the strongly robust cascade with D components and MLP connections implement F.
Appendix G.3 shows constructions for strongly robust finiit xLSTM FLIP-FLOP and R₂ dynamics. All together, we obtain Theorem 5:
Theorem 5 (xLSTM does ftart-free robustly). All star-free languages can be recognised by xLSTM cascades, as well as by floating- -pintt implementations of xLSTM cascades given sufficient precision.
Proof. We have that there are strongly robust xLSTM dynamics that realise FLIP-FLOP and Ra- Thus by Theorem 43, every group-free function can be implemented by cascade of strongly robust XL. dynamics. Any such cascade itself strongly robust, by Lemma 36, and thus can be realized by floating-poii operations, given sufficient precision, by Theorem 2
26

---

Moreover, by Theorem 43 we know that for these cascades, it suffices to use MLP connecting functions. By Theorem 42 we also have that the parametrizations of sLSTM blocks which yields FL.P--FIOP and R2 can also be changed, within some 6 retaining the behaviour of the dynamics.
27

---

D Expressivity Results for State Space Models
In this Appendix we reap rewards of establishing the preliminary framework of Metric Automata Theory for r--finite dynamics. We can now prove expressivity results by establishing structural properties of dynamics, which are preserved by feed-forward cascades, and which are generally applicable.
In Section D. introduce the notion of contracting dynamics, which describes dynamics that not able to keep track of a state over unbounded input lengths. We use this notion to prove Theorems 3 and 4.
In Section D.2 we introduce another structural property, called aperiodicity. It is the n-finiteness corresponding notion group-freeness in Finite Automata, We use aperiodicity to prove Theorem 6,
Finally, in Section D.3 we focus on the SSM parametrisation of Mamba, and prove Theorem
D.1 Contracting Dynamics and Proofs of Theorems 3 and 4
Definition 30. Call 7-finiite dynamics (X, J' a contracting dynamics, if for any initial points % X and eventually equivalent input sequences (un)n21, (w/) C U, have that the corresponding state sequences (In)a21, (z)))=21 C are eventually equivalent.
Thus, for contracting dynamics, does not matter what state the evaluation of the inputs starts from-eventually all initial states lead to the same behaviour under a fixed input sequence. The intuition behind the name is the follwwing-eventually all possible states that the dynamics could be in under the input sequence collapse to a single 1y-component.
Example Clearly, all Finite Context Dynamics (Definition 18) are contracting.
Lemma 44. Let C = D1 ~4 contracting dynamics.
Dn be a cascade of n--fnite contracting dynamics. Then C is
Proof. By induction, is sufficient to show the statement for 2.
Let us consider C Dj ~ D2 with D1 = (X, and D2 = -Z,U x f2). The dynamics function of the cascade is:
f((x,2), (1 u), f2,, where u' = (u, fa u))
Consider arbitrary (wra 20); (1/1 26) X Z and (un)e21 U4 eventually equivalent in U. Take
(In 2n) = (D1 ~ D2) (2ro; z0), u)..)):: (1% * (Di D2) =6), v6).,
By inductive hypothesis, Di is contracting, and so since have
En = D(ro, up...a)i I' D(2g, v(I..))
have that (Ix)n21 (4')) E X are eventually equivalent. (n4,))n+)))22 (Wuh, (1+1)) (U
Thus also
x X)" are eventually equivalent.
Note that we have 2a+1 = f2(2:: (ux; xn+1)) and 2/ fz(2,, (u/, 2), Since D2 is by assumption contracting, and the two input sequence are eventually equivalent by continuity of sn. we get that (zn)m21, (2/) E 7" are eventually equivalent.
So, overall ((x,, 2,)), (1=2, 24)) E (X x z)d are eventually equivalent.
Lemma 45. Suppose a fi-finite Linear Recurrent Dynamics is e-robust. Then is contracting.
Proof. Suppose that D (X, f, is c-robust.
Let æo, 00,46 and (u,)n21 (u/)221 n2 C U which are eventually equivalent- -ay for n 2 N. For each component of U. say UI...., UR, define representative element vi,..., Tk- Define (ūn)221 C to be such that ü, Te where U, is the component containing un+ Thus (ūx))21 is equivalent to (u++N) h22 and (u'+N)m21.
28

---

Write An A(ūn) and B, = ((ūn) and (2 = fa, u. For S S 92 define
AS {a (æ y) a E [0, 1), M;, y E E) For B E R20, write 8.5 = {B- s S). Take M = sup, v. yE x || - yll. We have that M is finite, since X is compact, and hence bounded. Also, denote (0) X, X(x(*1)) (f(z, ūn)) - = (xx).
We have, by induction that ((x()) S For n 2 1, by inductive hypothesis we have A ((x(--1)) _ M+ ixc) A(X). Consider u + 0.
Mf
(X): for = 0 this is immediate.
(ne
E A(X()). Take
||u||" We have that
u = 3 (fn(x) fv)) = 3- (z - v)
for some z, ( and B [0, 1]. We have that y ((X(m-1)) S (M+ A(X).
M
so for some x',y' E we have
M
x' 3--'- M + 2(n 1)e
.x
Now:
[[ - | (Ja(z') + +e.0)ll= = and ||5x(1/) - (Ja(3') + +)
so by robustness, fx(2') + E U E X and fn(3') - E. Thus
AX (fn(x') + t. (fi(v') - c.
fn(x') - fn(5') (,(5)+26 2
An(x' -1) + -2
-AM 2(n - 1)e )
M
An(x 8) + 2c
M + 2(n 1)c ) 11-1 +
M
2c
u
|
So, have = -y .. for some E A.X and
M
-1
2e
.3-1
+
M + 2(n 1)c
||
M + 2(n 1)E
2
-3-1
||||||
M + 2(n
1)e
2e
8- and ||u||| S M
M
M
M + 2nc
M
So
M4+2ne M
A(X), and thus indeed A(X(m)) C z'Il + 0 as n cc.
(M
A(X).
Therefore
sup x'
|
Now, consider the sequeneess (Dizo, "p... ()) (D(z') u "/p..n)))22" We have by Lemma 24
D up. = (xx
DxD( upI..n)
and similarly D(r', " NI ~x D(r'r, m)).n)) Now, D(Z'y ml..))); D(aNN up..))
(x)., Thus we have
|| u(..))) D(NN, m)). x(m1|| + 0 x0
Therefore, eventually Dary up) and D(NN, up..)) E (n) are in the same comppnntttt of X.
D
29

---

State sequence of aperiodic D
ststat sequence of C(D)
xt
Vi thy E
[u]
[us]
M1++11
[sr]]]
[ax
Fm
Figure 9: State sequence of aperiodic dynamics under iterated input always ry-converees.
Theorem 3 (Non-robustness of LRDs). Suppose an 7-finite LRD is such that its canonical semiautomaton D has least states, and input inducing identity transformation. Then D cannot e-robust for any e O.
Proof. Let D = (X, U) be an f-nite LRD, such that its canonical semiautomaton D = () has at least two distinct 17-states, say I, H', and an input a inducing identity transformation on X. For contradiction suppose that D is robust. Then by Lemma 45, D is contracting, Thus for 2o I, v E I' and u E u we have that the sequences (z.,. = D(zu, u²)) n211 (2', = D(z w²)) n21 E X are eventually equivalent. Since [u]~u have that the corresponding sequences ([xn)~> )z1, ([="]~>))<> X are constant, equal E, H' respectively. Thus necessarily x². This is contradiction.
induces the identity transformation of X, we
Lemma 46. Contracting dynamics cannot implement the state-sequence function of FLIP-FLOP.
(set. reset, id} U and decoder dee + {low, high]. Suppose that the dynamics D = (X,U, U) of S are contracting. Consider To X and input sequences (un)n21, (1/)221 C given by
Proof. Consider system with some encoder
U1= h; u' = U, v/2 = i for
They are eventually equivalent, and so the corresponding state sequences on D(ro, (ui...)) and z/ = D(ro, (u)..n) are also eventually equivalent. Thus
dec 55( enc(ui....) = dec oS( (enc(u(....)) E (high, low]
for large enough since (high, low] is discrete space.
However, the two sequences of inputs correspond to different flip flop states thus D cannot be dynamics for a system that implements a flip flop.
Theorem 4 (LRDs cannot do F1.IP-FI.OP robustly). Ft.IP-FI.OP cannot be implemented by cascade of q-finite c-robust LRDs for any 6 0.
Proof. A cascade of such LRDs is contracting by Lemmas and 44. Thus, by Lemma 46, it cannot implement FLIP-FLOP.
D.2 Aperiodic Dynamics and Proof of Theorem 6
Definition 31. For a f-finite space X, we say a sequence (In)22) S X convergee in X, eventually all its terms lie in the same n-compooent of X.
the sequence of states a system n-converges, means that the behaviour of that system is eventually the same.
Definition 32. Call a y-finite dynamics D = (X, U,, aperiodic, if for all E X and in- put sequences (un)22 C y-convrrennt U, we have that the corresponding state sequence (z,)n21 C X is converrgen in X.
30

---

An example of a aperiodic dynamics is given by the FLIP-FLOP dynamics. An imput sequence that 17converges must eventually be constantly set or reset. In that case, the state is eventually high, low respectively.
Lemma 47. Let D be a n-finite Linear Recurrent Dynamics, with A(u) having all its eigenvalues being non-negative. Then aperiodic.
Proof. This a similar argument as for Theorem Grazzi et [2025], with some simplifications stemming from the fact that we can use associativity of linear operations freely.
Let D U, f) be an n-finite Linear Recurrent Dynamics, with X S R s.t. A(u) has all its cigenvalues being real, for all u E U. Say f(z, u) = A(u) x + B(u).
Consider a sequence (un)021
U "/-convergent in U, and zo E X. Let (In D( (1....)) n>1 E X" be the corresponding state sequence. We have some s.t. for n 2 N all Un are contained in the same component of U, we may pick representative E U of that component.
Write A = A(r), B(r). By Lemma 25, have for N that In+N ~x d' = D(NN, NN
We consider the state sequence in the diagonalized space of A. Write A P-P for the Jordan normal form of A. Here / is block diagonal, with say blocks Ji,..., Jg, Jb E m being Jordan Block with A on the diagonal being an eigenvalue of A, and I on the right off-diagonal. Also P E Rdxd since all eigenvalues of A are real.
Take H, Pr then we have
In+I P(Ar', + +B) = P(AP
1 En + B)
P(P-1 1oIp-JJPP-1 JPP-1 In B) JIn + PB
We will consider the difference žn = In+1 - In. Unrolling the recurrence we get
in = J (Jāo Øo) J 2o
The i-th entry of this difference, where is in say the b-th block of J, is
my
[zn]
[zols
This is of the form considered in Lemma 64. Thus, [žn]i E ER is eventually monotone, and it either converges in or is unbounded as n - 30.
Now, if 2,, + 0, that is [a for all E [1..d]. then we have that also, by continuity of linear maps, r'a+1 -/ P 2n + so that zr, must eventually be in the same component of X by Lemma 20. Therefore also )211 is coonvergettt in X.
Otherwise, one of the entries of 2n either is unbounded, converges non-zero limit. In both cases, the corresponding entry of x, is unbounded as n - co, and so this is impossible in fi-iiite space X.
Overall, this shows that D must be aperiodic.
Lemma 48. Let D (X.U be a 1/finite Finite Context Dynamics. Then D is aperiodic.
Proof. Let be the context length of D. Let X and (un)n21 U be connvergentt in U. Let E lie in the component of U which contains the tail of (un) M say for n 2 N. For n 2 N we have that un-1+1s ... Un ü. and so
Fr C( C(a')
Thus Zn is in the component of X containing C(al).
31

---

Lemma 49. Let C' = D1 ~9 ....... ms Dj be a cascade of n-finite aperiodic dynamics Di...., Dk. Then C is aperiodic.
Proof. By induction, sufficient to show the statement for n
Let us consider C = Di - D2 with Dr (I, and D2 - UZ x f2). The dynamics function of the cascade is:
f((x, 2),
where v'= (u, fi
Consider a sequence (ur)21 E U n-convergent in U, and ( mo) E X X.
As D2 is aperiodic, the corresponding sequence (rn)n21 C X crcovveggen in X. Equivalentyy (1441) is n--onvergeet in X. Moreover, then the sequence (ul, (Un, #a+1))m21 is n-convergent
in U x X. Since D2 is aperiodic, the sequence (zn)=21 Z is therefore conoeergent in Z.
All together, (( zn)) n21 17-onverreent in X 2.
Theorem 50. 17-finite dynamics are aperiodic if and only if their canonical semiautomaton group- free
Proof. Det () have canonical semiautomaton DA (X,U3)
(=) First, suppose that D is not group-frre. By Theorem 13, there exist some S S X and тł U s.t. J(-,8) 7) induces a non-trivial permutation on S. That is, since S is a finite set, we have X s.t. Da T²) + ( x=*1) for all 2 Here n7 denotes word length consisting of repeated symbol V.
Take E U s.t. [u]w and x E s.t. [x] =. Then, we have that for all 2 that
((zz"")] * [D(x, u 1=+1)]
The input sequence (u") is y-convergent in U, but the corresponding state sequence (s(,)"))) not. Thus, 12 is not aperiodic.
(+=) Now, suppose that DA is group free. By Theorem 12, DA can be realized by serial cascade of FLIP-FLOPS, say C. We also have, that C can be realized by food-forward cascade C' of FLIP- FLOPS and repeat semiautomata, all of which are aperiodic (as repeat semiautomata are FCDs). Thus by Lemma 49, C' aperiodic. It remains show that dynamics realised by aperiodic dynamics are also aperiodic.
Let (a, L () be an assignment of D into C². Consider an coconvereent input sequence (ūn n21 CU and Ty E X, with the corresponding state sequence (H,, = D (To, U(I...))) n20 S X. Since (T,,) S U is n-convergnn,, it is in fact eventually constant, since U is discrete space.
Since C' realizes Da. by Theorem 14, we have, for Ty E a((o))
M(Da) Tp...) C M(C) (TI.))))
where M(DA),M(CC) are the canonical machines for DA, C, respectively. Now, (T,,) is even- tually constant and so also (u(T,)) is eventually constant. is aperiodic, and so the sequence C(T,, (TT)).))) is n7-oovvereent (and thus eventually constant, as C' is semiautomaton). All together
M(Dx) Mp...) M(C)( (up...))) <(C(z', ((up..))) c(u,))
by def. of canonical machines, and therefore this sequence is also eventually constant.
Thus state sequence D (Zo, kp...) itself is eventually constant.
Equivalently, by Lemma 26, for any converett sequence (u,) U and Zo sequence (D(xo, u(..,))) Ç X is r-convergent, and so D is indeed aperiodic.
X the state
D
32

---

D.3 Parametrisation of Mamba and Proof of Theorem 7
Sarrof et al. [2024] show that any star-free language can be recognized by an SSM like Mamba (Gu al. [2022]), using the Krohn and Rhodes Theorem from Algebraic Automata Theory. However, in their construction, they assume that gates of the form A(u) 0 can be used, which is not the case for architectures utilizing strictly positive parametrization, like Mamba.
We show in Construction a modified y-finite system construction, which only requires gates with diagonal entries in the range [c, 1], for suitable 0. As it turns out, further restricting diagonal entries to lie in (-1,1) makes it impossible to implement a flip flop.
Mamba ((Gu et al., 2022]) parametrization is of the form
A(u) Diag( exp (-A, 2 exp(zu))) where zu Rd Au E 20,
and @ is the element-wise product IR x RRd + R4. This gives - [A O exp(2z)]] < for E 1...dd d. and thus A(u); E (0, 1) for E 1...d. d. We will show this section that an SSM using Mamba blocks cannot implement flip flop for unbounded.
However, experimental results in [Sarrof et al., 2024] show that this architecture does well in experimental evaluations and demonstrates length generalization for star-free modelling tasks. For tasks involving periodic modelling, the model fails to length generalize. This motivates us to investigate the geometric complexity of the state space when evaluated sequences of bounded length Appendix E.
Construction 3. There is r--finite system with Linear Recurrent Dynamics with diagonal entries in [e, 1], for some e > O, which realize FI.IP-FI.OP dynamics.
Take e 1/4. Consider X = X2 U XA C I, where
X = B(1,c;; N₁ = B(,
Then Xg X1, Xa are the components of X, and X is n-finite. Take U, e (s,r, - U and f: X x U + X to be such that
(1,0)
if
f(x,e(o)) Ag A + Bd where (Ag, Ba)
(c/4,1)
if
(c/4,2)
if ===
We have X C B(0,2+ c). and so (c/4.))(X) (XX) B(0,c/4 (2+ B(0,c). Thus that f maps X to X, under input r and to X,, under input s. Under input i, f acts as identity. Thus these dynamics indeed realize FLIP-FLOP, through assignment that identifies with a mapping high + X₁, low + Xt, mapping set + 8, reset + r, + and mapping Xt to low and Xд to high.
Lemma 51. Let = (X f) be an f-finite Linear Recurrent dynamics with A(u) diagonal, with entries in (-1, for all U. Then D is contracting.
Proof. Let 2o, E X and (un)n21 C U. For each component of U, say U1,... ......., Uk. define representative element 71 Ti...., Tk- Define (2))n21 S U to such that u', = re where Ue is the component containing thy Thus (2/)n21 is equivalent to (u,)221, and (ul, m22 takes finitely many values ri, ri,...,
Now, consider AI...., Ag. where A, = A(rc). For each E [I.r], let de be the largest size eigenvalue of Ag. Then we have (Ael < 1, and
|A. æ||2 I |Ael- |
Vo X
Let arg max.el..r Del then we have | 1 and
[A(r.) æ112 I |X| ||0||2
Vz E
33

---

Now, we have that for the state sequences (In)n21 h2 corresponding to initial states 2o. %6 resp., and the input sequence (u', n, the following holds;
In - x 12112
|| (A(u)) In-1 + B(u,)) - (A(u,) -'p-1 + B(un))
||A(r)) (fn-1 - x 111
for some c C [1..k]
|\] |n-1 x/2 x/2-1/9 111
...
||| |000 = +0
Thus eventually on and sy must in the same component of X.
Altogether, we arrive at the following result (for r-finite dynamics), restated here more precisely than the main body.
Theorem 7. SSMs with Mamba parametrisation cannot recognise FL.I--FI.PP as 17-fnite systems.
Proof. Mamba blocks are feed-forward cascades of LRDs of the type considered in Lemma 51 and convolution blocks (FCDs) see Figure 6. Thus f-nitte feed-forward cascades of Mamba blocks are contracting, and by Lemma 46, cannot implement FLIP-FLOP
34

---

E Geometrically Constrained Systems
In this appendix, we depart the setting of r7-finiteness, and explore coometrically-constriiic (GCSs). This setting allows for systems implementing functions beyond regular, but shares many properties with the 1i-finite setting. We develop the theory of GCS to explain empirical capabilities of Mamba, and to showcase the flexibility and generalizability of Metric Automata Theory.
systems
In Section E.1 develop notion analogous aperiodicity from Section D.2. We then prove Theorem 9.
In Section E.2 introduce generalisation of 1z- n-finiteness,, called weak 17-finiteness. We use it to argue that the cascade decomposition results for ry-finite dynamics still apply to dynamics with convex-covering state-spaces.
In Section E.3 we show that 77- 7-finitte dynamics are special case of convex-constraiie dynamics. Finally, we show construction of FLIP-FLOP using a Mamba convex convex-constrained SSM, and argue using weakly 17- f7-iiniteness that Theorem 8 holds.
Definition 33, For Ω Rd Cd, we call C' S Q convex-covering if C' is finite union of open, convex sets in Ω. We say that X C Ω is convex-covered by C' C C.
We say X is convex-sepurated by C if (i) it is convex-covered by C' and (ii) each path-connected component of C contains at most one path-connected component X.
Note: any convex set in Ω Rd Cd is path-connected. Thus any convex-covering C has finitely many path-com connected components.
Definition 34. Let 52 = Rd or = C4, and let C Q. We say that dynamics = (X are convex-covered by C' X is convex-covered by C. We define system geametrically-consvvineed by C' as tuple Sc U,UU,, C, Y. where its dynamics (X, ʃ is dynamies convex-covered by C, 20 E X is the initial state, and h C U + Y is the continuous output function.
The difference between a shortcut system and a system is that the dynamics function is defined only on X, while the output function is define the convex-covering C.
We extend the definition of implementing function to shortcut systems: Sc implements F Σ + T
with encoder enc Σ -> U and decoder dec. Im h - r if enc, dec are continuous and F(w) dec oS( enc(w)).
Construction 4. Consider Linear Recurrent Dynamics with state-space X = Z, input space {a.b} b} and dynamics function f(n,
+ 1; (n, n - 1. The space C = (- -0.5) (-0.5, 0.5) (0.5, oo) a convex-covering for this dynamics. We may define the output function h: C - {0, 1} to map points in (-oo, -0.5) U (0.5, oo) to 0 and points in (-0.5, 0.5) to 1. Picking initial state Tog = 0, we have that this GCS outputs precisely when the input has the same number of as and bs. This recognizes the language
fw E {a,b)+ has as many as bs.}.
whose dynamics can be interpreted as a counter, with a corresponding to +1 and corresponding to -1.
Lemma 52. For cascade D = Dj ~ ..... Dn with D; comnexcooeerdcconessssppnndd by C; we have that C is coneexccoerr///oneexeeepprelll by C1 ... Cn
Proof. Suppose D; is convex-covered by C; for E [1..n]. First, C1 X ... Cn is indeed convex- covering. A product of convex sets is convex, and so a product of finite unions of convex sets also finite union of convex sets (by commutativity of set product and union, proof of Lemma 19).
Thus, X1 X ... x Xn, S C and D is convex convex-covered by
Now, suppose further that D, is convex-separated by C; for i E [1..n]. The path-connected com- ponents of C are of the form I G., where G; is a path-connected component of C, Similarly, path-connected components of X X, connected component of X;
X, are of the form [[ Z, where Z, is path-
We have that I Z, intersects IT G3 precisely when Z, intersects G, for each E [1..n]. Hence, there is exactly one component of C intersecting I Z,, i.c., C convex-separates D.
D
35

---

We begin by defining a restricted type of cascade. This model corresponds more to the idea of joining the cascade components by their respective output function. Thus, we require that the connection between sequential blocks respects convex-coverings.
Definition 35. A constrained cascade D1 C Czz1 D, w.n.t covering C₁ x C₂ a dynamics D1 Da, where D; = (X;, U x (i-).( fi) and D; is convex-covered by Cj.
We can think of constrained cascade as feed-forward cascade with connections D1 21 gus! D where each gi is continuous on x C1..i-11.
E.1 Aperiodic Convex-covered Dynamics and Proof of Theorem
We define an analogous notion of aperiodicity for convex-covered dynamics. First we extend the notion of c-convergence to convex-con coverx-cov.iings.
Definition 36. For space X, we say sequence (2n)n21 E X PC-converges in X, if eventually all its terms lie the same path-connected component of X.
This is an identical notion to r-convergence, but give it different name, since it applies to non-ty-finite spaces.
Definition 37. Call dynamics D = U, aperiodic w.r.t. convex-covering C, if convex- covered by C' and if for every sequence (un)n21 E U PC-convergent in U and xo E X, the state sequence (D(ro, uI...)))n2) E X Ç C is PC-convergent in C.
Note the difference in definition: we require that the state sequence eventually in the same component of C, instead of the same component of X!
Lemma 53. Let D = Dj ~ ...... Dn be cascade s.t. Dj is aperiodic w.rl convex-covering C; for E [1..m]. Then is aperiodic w.r.t convex-covering
C1 X Cn-
Proof. Analogous to proof of Lemma 49, applied to the cascade Dí wy ... we D',, where D' (C,, x f()...
Definition 38. call a function Σ+ + P alternating if, for some a Σ, the sequence (F(o")) n21 E T changes value infinitely many times.
Theorem 54, Let be a dynamics aperiodic w.r. convex-covering C. Let Se be a shortcut system constrained by C with dynamics D. Then Se can not implement any alternating function.
Proof. Say D = (X, and Sc = (X, U. C,Y,h). Suppose for contradiction that Sc with encoder enc Σ + U and decoder dee Im h I' implements alternating function F b
Let a be a symbol such that (F(o")) n>1 changes value infinitely many times. Since D aperiodic w.r.t. C' have that (D en)(o)")) n21 X S C is eventually in the same path-connected component C. As decch: C x + continuous we thus have that
F(a") dec (D(zo, enc(a")) enc(a)
is eventually in the same path-connected component of r, i.e. eventually constant. This is contradiction.
We now introduce an elementary theorem about convex sets in Rd (or Cd).
Theorem 55 (Minkowski's Hyperplane Separation Theorem). Let A, B C Rdd be two disjoint, non- empty convex sets. If both are open, then there exists a non-zero zero vector Rd and constant IR s.t.
(a, v) > and (b,u) <c Va A B
with (..)) being the dot product.
36

---

Proof. By Section 2.5.1 of [Boyd and Vandenberghe, 2006 2004], we have that there exists non-zero vector Fd and constant с s.t.
(0,v) 2 and (b,0) c Va E A
Now, these inequalities in fact must be striet. For contradiction suppose that (a, u) for some a E A. Since is open, we have that for some 0 (a,
(a, <) C A. Thus a 6 Teel E A
(/ell22 # 0 as u is non-zero vector). But then (a + T = a + > a by linearity of the dot product. Similarly for B.
Theorem 9. Let D be an n-finite Linear Recurrent Dynamics, with its state-transition gates having all non-negative eigenvalues. Let C be a covex-regular covering of D. Then D is aperiodic w.r.t. C.
Proof. Let D = (X, UK f) be Linear Recurrent Dynamics, with X C R. convex-covered by C, s.t. A(u) has all its eigenvalues being real, for all U. Say f(z u) A(u) B(u).
Consider sequence (un)n2) E U, state-convergent in U, and zo X. Let (I= Dawo uI..a) C X be the corresponding state sequence. We have some N s.t. for 2 all un are contained the same component of U, we may pick representative E U of that component.
Write A A(r), Brr). By Lemma 25, we have for 2 N that
Nn+N ~x s'n D(EN, ""~N
Like in proof of Theorem 47, consider the state sequence in the diagonalized space of A. Write = PPIJP for the Jordan normal form A. Here J is block diagonal, with say blocks J1,... Je. Ju mmm being Jordan Block with λ eigenvalue of on the diagonal, and 1 on the right off-diagonal.
xma
Define Intl In and V/. = P( - x'n), then
sh11 P. (o'+2 xnt12
P. (Ax'r1 B Ar', B)
PA (#'n+1 xzn)) J1hn
Thus, unrolling the recurrence we get
v/2 = Jh
The i-th component of v/, where is in say the b-th block of J, is
Wh] = Σ A
(-1
n
[vb
The binomial coefficients are polynomial n. Thus we may write [v<] = E Bg n af. where by E Z20 and = A 2 0, which is of the form in Lemma 64. Since Py'n- we have
[ale EPPss Whl
which again is of the form in Lemma 64.
Now, for contradiction suppose that æ', is not state-convergent in C. Then, since C' has finitely many components, there are two distinct components of C, say C1, C2 such that x', is in both C₁ and in C2 infinitely often. Furthermore, since C1, C2 are finite unions of open convex sets, there are convex, open sets S1, S2 which are disjoint, non-empty, and x is in both S₁ and S, infinitely often (*).
By Theorem 55, there is a non-zero vector v E Rd and constant IR (81, Vs S and (82, v) > Vs2 E S2.
Thus. (2/, v) iiffinitely often, and (I/n v) infinitely often.
37

---

We have
d
(ya, v)
= 1/
[Un]s
1=1
is again in the form from Lemma 64. Thus it is eventually monotone. Therefore eventually (Vo, 1j S
O, in or (yn, v) 2 O. By linearity the inner product
Wn v) = (In+1, u) (a v))
Thus, eventually also (T v) is monotone-cconrradiition with (*).
E.2
Weakly r-finnite Dynamics
In this section we introduce the topological notion of connectedness, as well the necessary results to establish the finite state properties of GCSs where the state-space coincides with the convex-covering.
Definition 39. A topological space X is called discomeeted,, if there are disjoint non-empty sets H, K in X such that X
K. Then X called connected if is not disconnected.
Connectedness is, it turns out, generalization of path-connectedness.
Fact E.2.1. (Theorem 27.2, [Willard, 2012]) Every path-connected space is connected.
Similarly to compactness and path-coonectednnss, connectedness is preserved by continuous map- pings and products.
Fact E.2.2. (Theorem 26.2, [Willard, 2012]) The continuous image of connected space is connected.
Fact E.2.3. (Theorem 26.10, [Willard, 2012)) A nonempty product space is connected iff each factor space connected.
Similarly to path-connectedness, connectedness induces an equivalence on the space.
Definition 40. For æ E X, define Og the union of connected subspaces of X containing We call it the C-component at a. We write x y when E Ca-
Note, that in [Willard, 2012] C-components are simply referred to as components.
Fact E.2.4, ø an equivalence relation, partitioning X into maximal (with respect to inclusion) connected subspaces of X. C2 is the equivalence class of x containing See Theorem 26.7 and Definition 26. of [Willard, 2012] for details.
Fact E.2.5. (Theorem 26. [Willard, 2012)) The C-components X are closed in X.
Thus, we think of C-components as partition of the space that a coarsening of the path-connected components. For an example of a space that has one C-connected component and 2 path-connected components, see the topologist's sine curve (Example 27.3, [Willard, 2012]).
Definition 41. We call space X weakly 1i-fnitte it has finitely many C-components.
Example 10. Any finite alphabet is weakly ni-inite, with each symbol being in separate C- component.
Our goal now show that weakly 17 finiteensss enjoys the same favourable theoretical properties as -i-initeessss
Lemma 56. A continuous image of a weakly 7-finite space is weakly 1-finite.
Proof. Let CI, Cn be the C-components of X, and let f X Y be continuous, Each f(C)) is connected, and so Im is a union of finiely many connected spaces f(Ci)....,f(C Thus, the equivalence classes of 2im f must be unions of these images. Thus xim/ must have finitely many cquivalence classes.
Lemma 57. The Cartesian product x Y space of weakly q-finite spaces weakly n-finite. The C-components of X x Y are the products of C-components of X and C-components of Y.
38

---

Proof. Let Ci...., Cn and Ei.... E, be the C-components of X, respectively. We have X Uh= C₁ Y Uー= and
T (U 1=1 j=1
UU ==1==1
By Fact E.2.2 each C2 Eg is connected. Thus, the C-components of X x Y are unions of the products C, x Ez. Now, fix E [1..n].j E [1..j] Let Z be the C-component of X x Y containing C, Ej. consider the projection map x X x + X. As the projection continuous, the image, Tx (Z) is connected in X. Moreover, C2 E (Z). Thus, as C, is maximal connected subspace of X, we have C. (Z). Similarly, considering the projection xy X Y + X, we have E xx (Z). Since C; Ej S Z, we therefore must have C₁ x Ej = Z. Therefore X Y has finitely many C-components, and they are the products of C-oompnnents of X and C-components of Y.
Lemma 58. Let X be weakly r-finite and E be finite alphabet. Then f X + E is continuous if and only if it is constant on the C-components of X.
Proof. Let f :X + Σ be continuous. Let C' be a C-component X. By Fact E.2.2, f(C) C Σ is connected, and so f(C) }o} for some E. Le., f is constant on the C-components of X.
(+) Let f + Σ be constant on the C-components. Let Y C Σ be closed. Then (Y) C X must be a union of finitely many C-components, since X is weakly 7-finite. By Fact E.2.5, we have that each C-component closed, and therefore also f ((Y) is closed, finite union of closed sets. Thus f is continuous.
Now, we have all the properties needed to carry out the arguments in Appendix B.3. Definition 42. We call dynamics D (X, U, f) weakly 17-finite if X and are weakly ry n-finite. We call system S weakly 17-finite if its dynamics are weakly 7-finiite
By Lemma 57, we immediatly have that cascades of weakly 77-finite dynamics are weakly n-finite. Example 11. finite dynamics are weakly 17- fininite.
Theorem 59, A convex-covering is weakly r-finite, with its C-components coinciding with its path-connected components.
Proof. Let CI...,, Cn be path-connected components of C. Each C; is union of finitely many open (in IRd) convex sets, and so also open. Let Z C-component of C. Then Z is a union of the path-connected components, and so Z is also open. An open, connected subspace of Rd is path- connected, see Corollary 27.6 of [Willard, 2012]. Thus Z must actually be one of the path-connected components.
Lemma 60. Let D fX be geometrically system, convex-covered by C, with X = C. Then D is weakly ri-finite, and the C-components of X are the path-connected components.
Proof. C' has finitely many path-connecte components, and so it is weakly finiiee, since path- connectedness implies connectedness. Now, each C-component of C' is union of the path-connected components, all of which are open in Ω = Rdd Hence each C-component of C' is open in Ω. By Corollary 27.6 of [Willard, 2012], C-components of C are therefore path-connected. Thus the path-connected components and C-connected components of C coincide.
Since a C-component has to be mapped by a continuous function into a single C-component, we have that version of Lemma 24 also holds for weakly fi-iiite dynamics. For weakly finite system S = {X, U, nn, Y, h) and weakly 77 17-finite dynamics D = (X, U, f), we can thus define the analogous canonical automata
Cwenkly (8) -x (X/Eexx U 1/ZOy F.Toleexx Im h Cweakly (D) -00)) / U/ f)
39

---

with f ([=]=x:[u<x)) - [f(x, and h: ([0]=x:[[]<))) + [h(z, u)]mm
Similarly, replacing path-equivalence with C-coponent-squivalennee in Lemmas 26, 27, 28 and Theorem 1, we get that the canonical automata weakly r7-finite systems have the same capability in terms of implementing functions.
Likewise, the realization results of Appendix B.4 and Appendix B.5 carry over to the setting of weakly j-finiteness. Thus may apply the structural theorems of Algebraic Automata Theory in the case of weakly y-finite dynamics. We defer exploring the properties of weakly ry-finite dynamics in detail to future work.
E.3 7--finite Systems as GCSs and Proof of Theorem 8
We start by showing that fifintte dynamies that are convex-separated by C can implement exactly the same functions in 17- i-miiite system as in GCS constrained by C.
Lemma 61. Suppose q-finite dynamics D are convex-seye senex--eppraate by C. The following are equivalent:
There is system with dynamics D that can implement F Σ+ T
There is a shortcut system Sc constrained by with dynamics that can implement F : +
h.) be system with dynamics D that implements F with some encoder enc Σ U and decoder dec r.
Proof. S=
Let Ci...., C. be the path-connected components of C. Fix Y E I and define h' C U F as follows: for i E 8, if C. X = 0, take N'(c,u)
7, where y E T. C, n # 0. take W'(c, u) = dec oh(x, u) for uc C; x U, where æ X, This is well-defined: For all x, x' E C2 n X,, since C' convex-separatee of X, we have that x and x' are in the same path- path-connected component of X. Therefore necessarily dec oh(x, u) = dee oh(x', u))
Want to show: N' is continuous. Let ((ens un)) n21 CC x U be a sequence converging to (c, e C' x U. Then (cx)221 converges to c in C and (un)221 converges to in U.
Let C, be the component that contains Since C; is open, there some e >> S.t. Bn(c, S C. Since C, + c, we must have that eventually (c,) lies in Ba(c, S Ci.miiilarry, let Uj be the n-component of that contains u. Then, by Lemma 20, as un + u, we must have that eventually (un) lies in Uy- Thus eventually ((Cn, unn) ni1 lies in C; Uj. By definition of h', it is constant on C. x Uy. Thus (h' (un, ca)) n21 is eventually equal (c)
Now, define S. (X, U, zo. C.Y. As h' C X U + Y is continuous, this is well-def. shorteut system constrained by C. Moreover, since h' constrained to X U is equal dec oh, we have that Sc with encoder ene and decoder id r + implement F.
Let S. UX, zo; C, h)) be shorteut constrained by C. Suppose that Se implements F with some encoder enc Σ + U and dec + r. Then taking h x U + to be the restriction of h. we get that the system S (X, f, zo, Y, h²) with encoder ene and decoder dec implements F.
Lemma 62. Let X a Ti-finite space. Then X conver-separated by some convex-covering C.
Proof. Let XI,..., X5 be the components of X. Take
8 min inf
d(z;,I)))
Isisss =,X,a,Ex,
Then have 8 > 0 by Lemma 20. Define
C = (B(x,, 6/2) x; E X.)
Then C. an open cover of X,. Since X, is compact, by definition of compactness there is finite subcover C C Of which also covers X,, Moreover, by definition of 5. this subcover does not intersect other components of X. Taking C; UC! have that C = Ci U... Ck is convex-covering that convex-separates X.
40

---

Construction 5. FLIP-FLOP dynamics can be implemented by a Linear Recurrent Dynamics with
entries in [6. 6). for some >
Let < 1. Take D = (XU with X = X2 U Na. where X₁ = (-1,0), X = (0, 1) and U, such that:
(1 e,-e,00
if 0 =i if =
e(x))(o)) = Ao I Br where (Aa, Bo)
(e/4, -1/2)
(e/4, 1/2)
if h
With output function X₁ + low and Xa high, this implements FLIP-FLOP. The set C' X is convex-covering of this dynamics.
Hence, Mamba implement FLIP- -LLP constrained system, and constrained cascades of Mamba blocks can implement any star- star-free language.
Corollary 63. 17-inite dynamics are in particular convex-separated dynamics, and implement the same functions in 1y-finite systems and in GCSs.
Theorem 8. SSMs with Mamba parametrisation can recognise all star-free languages as GCSs.
Proof. By Construction 5, there a Mamba block dynamics D, with convex-covering state space, and f7-finite input space, that realise FLIP-FLOP as weakly 17-finite dynamics. A Mamba block can also have a convolution, and so there Mamba block dynamics E, with a convex-covering state space, and 17-finite input space, that realise R₂ as weakly n--finit dynamics (details omitted. Also a sLSTM-like 77-finite construction is possible, see Appendix G.3). Thus, by weakly 17-finite analogue of Theorem 14, all group- freu-free functions can be realized by feed-forward cascades of D and E components. Such cascades are actually constrained cascades Mamba block GCSs, since the convex-coverings of D and E coincide with their state-spaces.
41

---

15
04
22-
97 47
11 15
FLIP-FLOP task [Liu et al., 2023]. PCA of trained 1-layer Mamba states for each channel: red and blue are state sequences under i0 inputs, starting from w1 and wO respectively. After 1000 inputs, both state sequences give same predictions on the read instruction r, incorrectly. The 'doubled' state trajectories are due to each transition consisting of input tokens.
Figure 10:
Details of The Experiments
We have created visualizations based on the [Liu al., 2023] FLIP-FLOP task. The dataset is The objective of the task is predictively model sequence of instructions of the form sæ, where i,, E 1. indicates that the next symbol is to be stored, r indicates that the next symbol should be the retrieved value and indicates action. The specific task we trained on corresponds to the "clean" prediction mode, where only prediction following an r instruction need to be predicted. We note that the aim of our experiments was obtain empirical evidence of Mamba having contracting dynamics, and comprehensive experimental study is beyond the scope of our paper.
available at https:// https:://huggnngfacce www.gface.co//aaeeeeeo co/datasets/stteeeccceeeeseseese wetpttsssssttssessseseeeeee
We trained 1-layer Mamba sequence lengths 32, 64, and 512, observing similar state-collapse phenomena, as predicted by our results. Additionally [Sarrof et al., 2024] note that in their experiments Mamba needed more training steps converge than reported Liu al. [2023] for LSTM. This another evidence towards the influence of robustness on stability of training.
The code used to perform the experiments is based on the repository shared in Grazzi al. [2025], with some environment modifications to make it work on the 2025-04-09 Google Colab release. The forked repository is available at https //github. com/ adankow wttp///nllokiigg swtsstttttttteeeeeeeeeeeeee with a Google Colab notebook file containing the set-up, simple training loop, and hidden state visualisation code.
42

---

G
Additional Proofs and Constructions
G.1 Monotone Sequence Lemma
Lemma 64. Let d 2 01, .... ad 0, b1, .., bu E2o and vi,... E R. The sequence
Zn Σ U/ n ai
eventually monotone.
Proof. If all v2 = 0, then In = =0 for all n, in particular the sequence monotone. Otherwise, we may assume that v for all and that
0₂ dif1 or a4 =
a a++1 and b, b++1
If a1 0, then again Fn 0, and it is monotone. Otherwise,
take di 1 S d1 S d such that
a a1 for sis d1 and a, aj for 2 d1 +
We may write
d
In = 0i P(n)=
Σ
03 o..n" 4 a.
i=d++1
where P(n) is the polynomial Σ nt
Case 1: d1 1. We have a1 > 0 and
In a
P(n) +
Σ vs n (a./a1)" i=d++1
We have that (a:/a1) + 0 as co, since a1 a, for d1 + 1111 siss d. On the other hand, P(n) is non-zero polynomial, since its leading term is nn and 01 F 0, and so P(n) + too as n co. Thus, In +f 0 for sufficiently large n. Moreover,
01 n+1
(n + 1)
P(n + 1)/(n 1)th Ei ui(n 1)4- )
En+1
In
n
P(n)/nb Ei v/ n (a
We have P(n)/vb at most polynomially, while (a:/a1)" goes to 0 exponentially, since a; < 01 for di + 1 S i d.
as + co, since Vi n is the leading term of P(n). Also n bcbb grows
Therefore Ei=d+ 0 (aa-bi(aaaaa - as n + co. Lastly we have (x+1) n1
as n + 00.
All together
En+l
V1 +
lim
V1 + 0
In particular, eventually n, is positive, or eventually it is negative. There are cases:
If an E (0, 1) and x, is positive eventually, then s, is decreasing eventually. If Ta E (1, oo) and v. is positive eventually, then s, is increasing eventually.
If E (0, 1) and H, is negative eventually, then 2,, is increasing eventually.
If a1 E (1, oo) and v. is negative eventually, then s,, decreasing eventually.
Case 2: aj 1. We proceed by induction on bj If by = 0. then necessarily d1 = 1, and P(n) = v1- Then we have by Case that F, P(n) = Fn 21 eventually monotone, and so also v, eventually monotone.
43

---

For the inductive step, consider
Un In+1
In
P(n + 1 P(n) +
Σ is a. (a:(n + 1)4, n²)) imd+1
We can again write Σ Li=d, 41 af (n 1) nn as Σd" of -nn (d))", with de < 01 1. On the other hand ((n) = 1) P(n) is polynomial with leading coefficient of degree < by Thus we may apply inductive hypothesis to
yn = Q(n) +
n (d))
2=1
to conclude that Yn is eventually monotone. Thus, either In+1 In Un S eventually, or En+1 In = yn 2 eventually, Hence n, eventually monotone.
G.2 Sequential Cascade Construction
The serial cascade be realised in terms of the feedforward cascade Consider E 1,2 and D, = (X,, U2, fi). Define the repeal dynamics on X1 to be the system Rx, (X3,U x Xi,r), with given by
r((a), 22), (u, xr)) = (222, 2ra) Van, 22,,,2,,0 23 X1, UU
Thus Rx, can delay the propagation of the state of Dj by one time step. Also, define the modified dynamics D/2 (X2,U U x Xf.f)), 12), with l3 given by
fg (22, (u, 2 old Tenww)) = (12, (u, x1,ota))
Note that Rx, is equivalent to the usual repeat dynamics over X1, (XP, XI, but with input function (u, + x.
Now, the ferdrforwwrr cascade D1 Rx, D22 is well-defined, and has the following transitions:
I' ((11, Lnenew: 22), u) (1), x1 oldd: Ti,neu: r/2) where
1 fi u); o = Il.newi ai,new = 411
2 f2 (u, 21, x',new)) fa f2(22, (u, (1,ww))))
Now, suppose we have system S (X1 X2,U, (2100 22,0); Y. h) with dynamics D1 bc
D2- Then there system S' with dynamics Dj Rx, D2 which realises S: take S' = (Xf x X2, U, f', r/y Y,h") with z (I1.0, 21,0 21,0, R2,0), h ((11,,1 21, (2), = 1((11,122) u) and take
a: X1 X2 P
a(21, x2) + {(01, Fold, I1, x22) Fold E X1}
Take : U + U and y:Y: + Y to be the identities. We then have for all (21, X1 x X2, and x' E 22(
f'(x'c(u)) f' Fold, 11 x2), u) (of 21 وbb a((2(,=²6))
where x fi and 2/2 fe( 2il),, so that (z/ f((21,22), u). Moreover 2i a(ro). Finally, we have
(oM(2' = 1'(2' 10 11(((1) ((I111 Fotd, 31 x2), u) 1(((11) (2), u) h( v)
so that indeed S' is realisation of S. Note, that we did not need to introduce any new transitions on X, or X2 in order to carry out this construction. particular, if Dj and D2 are linear recurrent dynamics, then D1, D'2 are linear recurrent dynamics. Also Rx, is a Finite Context Dynamics.
44

---

G33 Robust Flip-Flop realisations
Recall the sLSTM parametrisation: the state space of sLSTM is R and the input space is R for some d 2 1. The dynamics function of the form (,,, h), + (Sel(e, n. h), u), Jal(e, n, h), u) Su((e, n, h), u)), where
folle, h), u) - (1, u)) c+ explliii( u)) (l(s(h, falle, hi,, u) = (h, w)) n exp(((((h,
(c)(e,,,),x)))
falls, n. h), u) = olo(h, u)) fa((c, h)
where each 4 E i, 2, function of the form w² a ro + b.. for wa E -R, E R. either exp or a, and to tanh.
G.3.1 Strongly robust sLTSM FLIP-FLOP realization
We present a construction for a one layer sLSTM FLIP-FLOP, which is strongly robust. The key idea to only use the h state to implement the dynamics. Then, we can use Theorem 42, and similar arguments involving uniform continuity, to extend the construction to be strongly robust in the states h, c, and the input space u. We shall present the arguments in more detail here, to demonstrate how robustness can be used to prove properties of systems, in particular how to extend robustness to strong robustmess.
z. Set by = -3, b. = 2, b, = 0. Then we have 4 3,4, 0. = 2. Thus the updates simplify
Let db = a. Set u. = 0 and rs = for 8 = i,
fel(e, n, f1), u) = o-3)) 3) c + exp(0) tanh(2) = =o(-3) c+ tanh
f,((e, h), u) o(-3)
exp(() o(-3) +1
ma((e,m,)), u) ((, felle, n, h), olo(h, u)) tanh(2) E [0,
fa(le, n, h),
Finally, take d = 1 and (h, u) = u 10h 5.
For now, let us fix e as e* tanh (2)
1-o(-3) ~ 1.01202 and n as n = 1-o1-3] ~ 1.049787, i.c. the fix
points of the linear recurrences given by La and Sn. Then we have that
o(-3)- + tanh(2) c² and (-33) n 1
Moreover, felle xx (...)) Inlle" M).2)
c = tanh 2, so that the update for h simplifies as
f(h,u) u) = fa(lc", nn', h), u) o(u 10h 5) tanh(2)
We can set = {ueer: Ureset, usa}. with Uset = 8, Useset = 8 and Uid = O, and Hiov = [-0.05, 0.2), Hnigh [0.8, 1.05]
Now, for [0, 1] we have
f(le, hi,, Uast. = 088 + 10h - 55) tanh(2)
2 20(3 tanh(2) A 0.9183
Therefore f((e, n, h), Upet) E [0.85, 1). Similarly f((e, n, hi,, Ureset) = 10h - 5) tanh(2)
5o(-3) tanh(2) x 0.04572
Therefore f(fe, n, h), Mreset) a (10h 5)- a(2 - 0.047426 < 0.05
E [0, 0.05) Now. for h S 0.2
and f((c, n, h), usa) 0.05). Also for h 2 0.8
(10h 5) (anh(2) > 0.95 0.9 = 0.855
45

---

and so f((c,n,h), u1a) E [0.8,1] Thus we see that the dynamics
H = Hiw U Hasgn: S,S = (l, + In (ne n ,,,,,,, .)),,))
realise the FLIP-FLOP dynamics, and is 7-finite and e-robust, for = 0.05. Furthermore, we can modify the input space U, to make it strongly e-robust.
Consider U = [0, 10). И x U" is compact, and f is continuous on H x U² so by Theorem 41 it is uniformly continuous on H x U'. In particular, for é' c/2, there exists d >> 0 such that
(1 u) (W, 50 = -1s(h,, J(M, w²)l S
for all (z, u), (x', .') E X'xU' Thus, we may take 8' min(6. 1) and U" |uset -
+
81 juia + 8)) Now, consider h E H, u U and h E IR such that I| - f(h, u)ll S c'. We have I|u w'll I 8' for some u' E (Uzer, Ureeet, Uiah. and
u1 u) (h( se
All together
E c=é+c 2 || f(h, + 115 u) f(h,, w')l 2 [1 - f(h, w)) + (f(h, f(h, ((,
=1lb' - ff(h,
Since uh) H and (H, U. is e-robust, we get that N/' E H. Hence f also gives a well defined dynamics function H x U + H, which moreover is e'rrobust. Thus, we have (H, U" f') is 7-finite and strongly min(e', (e', -robsut It also realizes FLIP-FLOP, since the input components induce the same 17-transitoons {Uget, Ureset: Usa by path-connectedness.
Finally, we extend the dynamics to e and n. We can see f as parametrized by E [c" + 0.5). [n" + 0.5), given by
Sa ou 10h 5) 0
P
So, f fn We see that fe,p is continuous in and p. and |c + 0.5] x [n- = 0.5] is compact. Thus by Theorem 42, there is some y > such that fo., induces the same function H x U + H as fer Also, similarly to how we extended U to U we can choose y such that the resulting dynamics are always e/ e/4-robust
Lets take X = H x C x N where C Ic" + 7 and N = In" = =] We have that the sLSTM dynamies gives a well-defined, robust dynamics function X x U + X: we already have that the restriction of the dynamics to the h component is robust. For the and n components, since (-3) < 1, the state updates given by fc and fn (which are independent of u) are contractions towards c* and n" respectively, with rate (-3). Thus Je sends C - [ct + = to [c* + ( and fn sends N = [n' = 7] to [re #7 (-3).. All together, the sLSTM dynamics are strongly min(e/4, 8', 71 (3))) rrbbsst and realize FLIP-FLOP.
G.3.2 Strongly robust sLSTM repeat dynamies
To realize any repeat semiautomata, as defined in Appendix G.2, sufficient to realize the two state repeat semiautomaton R₂ <(0, 1), (0, 1),r), with r((Eold, knew), ) x)) (Know I))-
Here, the construction is extremely similar the FLIP-FLOP one. We first show robust dynamics on just the h cell, using fh, u) auu + 10h 5) tanh(2) which realize Rg. Then we can use the same argument as before extend it to strongly robust dynamics on all 3 cells.
We can use the h cell to represent Tnew: by simply reusing the previous strongly robust construction for setting the high and low state, with dynamics function f(h, u) fa((e", n²" h)) u), state space H and input space [Uzat + 5'] U [u]. We then have that for some > 0 for all c E [c" + y] and [n" ?] the dynamics function Su n, h), u) still performs
0.015), Xo1 [0.02, 0.05), , X10 = [0.95, 0.98), Xn = [0.985, 1, 01] and uo = -8.1, tn = 8.1. Note that X Xoo Xoi U X10 U X has 4 n-components. Also, define
Define Noo
46

---

Xu = Xo1 110 and X1 X U X11 In our construction Xat will correspond to the state of R2 after the last two imputs were ab, a, b {0,1} 13.
We have
((0.95, u1) - o 9 5) ~ 0.999997 1(1.01, u1) = 00.11 10.1 5) ~ 0.999998.
As a is increasing, we therefore have /(Xi, w1) _ [0.99999, 1] C X11. Similarly, we have
f(-0.01, u1) = (8.1 0.1 - 5) x 0.9526 /(0.05, u1) - (0.11 + 0.5 - 5) 0.9734. Therefore f(Xo, u1) S [0.952, 0.974] C X10. Similarly for to. we have
f(0.95, un) = a - 9.5 - ~ 0.0265 f(1.01, uo) --1 10.1 - 5) ~ 0.0474.
Therefore f(X1, uo) S [0.025, 0.0475] C Xo1- Similarly
f(-0.01, wo) = o (-1 0.1 5) 2z 0.000001 f(0.05, un) o - R 0.000003.
Therefore f(Xo, Mo) S [0, 0.000004] C X Thus (X, {uo. : f) are well-defined dynamics and the n-componeets correspond possible values for the last 2 inputs. Hence clearly they can realize Rg, Moreover, the dynamics are strongly robust. The remainder of the argument is the same as for the FLIP-FLOP construction.
G.3.3 Strongly robust Elman-RNN FLIP-FI.OP construction
The following is modification of construction in [Knorozova and Ronca, 2024a]. Consider the dynamics function
faz u) tanh(2 u)
for x, u E IR. We have that for all v, u, [ax u) E [-1, 1j. Define X100 = (-1.1,, Xnigt [tanh(1), Note that tanh(1) xe 0.76159, tanh(- (-1) 0.76159
We have
f(-1.1,4) = tanh -2. + 4) ~ 0.9468
f(L.1,4) = tanh (2.2 + 4) ~ 0.999992
As tanh is increasing, we have f([-111,11)] 4) S [0.9467, 0.999993] C Xnigh Similarly,
(1111,11.1],, 44) 0.999999,,, -0.9467 C X Moreover
f(tanh(1),0) tanh(2 tanh(1)) 0.909
((111,0) = 1anh(2-1.1) R 0.9757
X1 Thus see that, taking X = X1ev Xnigh. Uset 4, Mreset -4, Usa = 0, the 77-finite dynamics (X, (wat, Uraset, Wsa h: f) are well-defined, and realize FLIP-FLOP. Also clearly they are robust. Now, by the same argument as for the sLTSM FLIP-FI.OP realisation, we can extend the input space, using Theorem 16 and Theorem 42, to obtain a strongly robust construction.
Thus, {Xnngg 0) S [0.908, 0.9757] C Xnigo- Similarly f(X 1ou: 0) S (-0.7757
47

---

H Further Discussion on Related Work
Sarrof et al. [2024] show that, in the inite-precision setting, regular languages that can be modelled by diagonal Ainear-recurrenee
with non-negative entries like Mamba- are precisely the star-free free languages. The setting differs from ours, in that it allows finite fractional precision, but unbounded number of integer bits. With that, number of positive expressivity results for counter languages is given. The empirical experiments show that SSMs indeed can model such languages on in-distribution lengths, but with limited fully formal, essentially ignoring the error of the linear dynamics carried out in finite precision. Weiss et al. [2018] use the same ReLU-activated Elman-RNV RNN and LSTM can implement counting behaviour, while Elman-RNNs with squashing activations and GNU [Cho et al., 2014, Chung et al., 2014] cannot.
The finite-precision arguments in this work are not
setup with unbounded integer bits to show that
Grazzi et al. [2025] extend Mamba and DeltaNet parametrisations to allow for gates with negative eigenvalues. The work proves that linear recurrences, with gates having non-negative eigenvalues, are restricted modelling star-free recurrent languages in the mnite-precision setting. Their framework differs from [Sarrof et al., 2024] and ours, assuming that the linear recurrence is computed in convolutional form in some finite datatype DD, with some operations carried out infinite precision before casting back into D. This setting is more explicit in its assumptions than [Sarrof et al., 2024), but not generalisable to other types of recurrence.
Merrill et al. [2024] use the parallelisability aspect of SSMs to obtain an expressivity classification in terms of Circuit Complexity in the log-precision setting. i.c. precision logarithmic in the input length. Assuming particular datatype is used to carry out the operations, it shows that SSMs, including Mamba, can be simulated in the TC-0 circuit class. Thus Mamba is unable solve the S₃ word problem, even with prr-piiiionn, under the widely-accepted conjecture that TC-0 o NC-1. The log-precision framework offers a unique perspective on the drawbacks of parallelism of SSMs.
The Turing-completeness capabilities of Elman-RNNs as offline models of computation are studied in (Siegelmann and Sontag, 1995, Kilian and Siegelmann, 1996, Hobbs and Siegelmann, 2015, Chung and Siegelmann, 2021]: differently, we study RNNs as online models, reading input elements as they arrive. A form of asymptotic expressivity of RNNs is studied in [Merrill al., 2020], when weights tend to infinity; differently, we consider actual weights. A rich literature surveyed in [Strobl et al., 2024] focuses on the expressivity of Transformers, that constitute an alternative to RNNs as they also operate on sequences.
48

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
49

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
50

---

The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specing well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tes system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
51

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
wotssuubmsssooooocoooy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: // cisiips.cc/uublc/ggiiiccs gwtp///deeeeeeeeee
wttpggddddde/edudbmibmiiii.a (CodeSubmisst onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
52

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma eгrоr bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
53

---

Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/heurips. http::///orrrpe..cpppppllhhhhhca
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
54

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cow com/datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
55

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [No]
Justification: Not used
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.M policy (https: pettps:/nnuurpss htt.:ppp....ccooeeeeeeeeee////2/ for what should or should not be described.
56


Reviews:
[{"review_id": "tTZ3RTCNaY", "reviewer": "Reviewer_RX1U", "summary": "This paper proposes Metric Automata Theory (MAT), a novel theoretical framework that generalises automata theory to continuous dynamical systems and allows the study of expressivity in both finite-precision and beyond finite-precision for a variety of model families. Under MAT, the authors show that xLSTMs can recognize all star-free regular languages, while SSMs with non-negative eigenvalues cannot, emphasising the importance of non-linear recurrences in expressivity. Finally, the authors demonstrate that Mamba with a piecewise-linearly separable state space can approximate star-free languages with some length extrapolation capabilities, however still fails on tasks such as Parity.", "questions": "1. Can Metric Automata Theory be used to also study the expressivity of RNNs beyond star-free languages, such as context-free ones? In lines 382-388 you briefly discuss this.", "limitations": "The authors do not explicitly discuss the limitations of their theoretical framework, but I would encourage them to do so.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n- The paper provides a novel and elegant generalization of Automata Theory to continuous systems, offering a unified framework for analyzing the expressivity and robustness of several recurrent models. Under this framework, the authors prove that non-linear models, such as xLSTM, can recognize all star-free regular languages, whilst linear models cannot. I find these results very relevant with implications on future research in designing recurrent models.\n- Afterwards the authors extend their framework via the notion of Geometrically-Constrained Systems, which addresses empirical phenomena like length generalization, and explains why SSMs with Mamba parameterization cannot learn alternating functions such as Parity.\n- The theoretical claims are backed up by empirical evaluations from the authors, as well as empirical results from related work, further emphasizing the validity of the theoretical framework.\n- The paper is very well written and contains an extensive supplementary material with the necessary background and further details on their theoretical results. The authors also review the related work properly, relating it to their results as well. \n\n**Weaknesses:** (Minor)\n- The paper briefly mentions the implications of robustness for training but does not deeply explore how the framework could guide the design of training algorithms or architectures. I would be curious to know the authors' opinion on this point.\n- The empirical evaluation is limited to a specific task and SSM model. Otherwise, the authors refer to results from previous work (which is totally fine). I would be interested to see the results using xLSTM on star-free languages to back up the theory. \n\nOverall, I found the work that the authors have done in this paper really impressive and even though my background limits me in deeply understanding some of the theory and concepts introduced in this submission, I was able to grasp them in high-level and understand the implications it can have in the field, especially in designing more expressive models in the future. To this end, I recommend acceptance.", "was_revised": true, "final_justification": "I think this is a relevant paper which will be valuable towards developing more expressive recurrent models in the future. I will keep my acceptance score.", "rebuttal": "Thank you for your review of our work. We greatly appreciate your recognition of our work as novel and highly relevant to the field and future model design.\n\nWe address your question, and then concerns raised in your review in order of appearance, and we are keen to hear your further thoughts and questions.\n\n## Question\n> Can Metric Automata Theory be used to also study the expressivity of RNNs beyond star-free languages, such as context-free ones? \n\nMetric Automata Theory can certainly be used to study RNNs beyond star-free languages, and as a matter of fact beyond regular languages. \n\n* First, the Geometrically-constrained systems (GCS) framework we present showcases that MAT is not limited to the finite-precision setup. Specifically, Construction 1 (line 330) shows a system implementing an unbounded counter with infinitely many states, which recognizes the context-free language where the number of $a$s equals the number of $b$s.\n\n* In lines 382-388,    we question the ability  of Mamba to implement “counter-like” functions. Although we have not developed a formal proof of this claim yet, our hypothesis is that Mamba transitions being contracting—as defined in lines 295-299—prevents it from realising such languages. Note that the dynamics in Construction 1 are impossible for Mamba, since they utilises the 1-d identity gate on state $n$.\n\n* We are planning on formally investigating whether this is the case in future work using the GCS framework, as we believe it is the right tool for explaining length-generalisation abilities of SSMs.\n\n## Further Concerns\n\n> The paper briefly mentions the implications of robustness for training but does not deeply explore how the framework could guide the design of training algorithms or architectures. I would be curious to know the authors' opinion on this point.\n\nAs we will further discuss in the Limitations response, the notion of Robustness allows us to draw indirect conclusions about learning. In our opinion it is an interesting avenue of future experiments.\n\n* On the architecture side, it motivates the use of non-linear activations and indicates potential issues involving SSM layers. xLSTM successfully combines linear and non-linear nodes. However in the original xLSTM paper [Beck et al., 2024] Chomsky hierarchy results reported show that the mixed architecture actually significantly underperforms the non-linear only architecture—see Figure 4, Cycle Nav, Mod Arithmetic w/o Brackets, Mod Arithmetic w Brackets, Solve Equation. We suspect that SSM layers are trickier to train because of lack of robust state tracking parametrisations.\n\n\n* Moving onto training algorithms, during our (limited) evaluations we noticed that on the FlipFlop task Mamba tends to converge slowly on the out of sample validation set, while sLSTM tends to converge suddenly. Additionally, Mamba would tend to move away from the local solution and dramatically decrease validation accuracy if no early stopping was in place. Again, we suspect that this is due to the linear RNN solution being unstable under perturbation of parameters, and the non-linear solution being robust according to our definition and thus stable under perturbation of parameters. However to definitively attribute training behaviour of these models to robustness phenomena would require thorough experiments and considering hyperparameters of the used algorithms. We think this is best left for future work.\n\n> I would be interested to see the results using xLSTM on star-free languages to back up the theory.\n\nWe agree it would be valuable to explicitly compare performance of xLSTM with Mamba on star-free tasks. We can expect both to be able to model star-free tasks based on their expressive capacity, the remaining question being how well they can attain these solutions via training. Nonetheless, we can look at existing experiments with (the classical) LSTM.\n\n* Bhattamishra suite results reported in [Bhattamishra et al., 2020] for the classic LSTM architecture, show that it achieves perfect accuracy on star-free tasks, both on in-distribution and out-distribution sequence lengths (Table 9). Meanwhile, the suite results reported in [Sarrof et al., 2024] for Mamba are the same, except for the D_12 task, where the in-distribution/out-distribution accuracy was 93.65/93.35 for 1 layer, 99.9/95.55 for 2 layers and  99.99/99.85 for 3 layers. (Table 3).\n\n* As for the  [Liu et al., 2023] FlipFlop task, in Section 4, paragraph FlipFlop [Sarrof et al., 2024] notes that Mamba converged in 3 times as many steps as LSTM, as reported by  [Liu et al., 2023]. \n\nAgain, we think that further experiments are a valuable direction for future work, to further explore advantages of LSTM architecture on star-free tasks.\n\n> The authors do not explicitly discuss the limitations of their theoretical framework, but I would encourage them to do so.\n\nBased on feedback, we intend to add a separate limitations section and future work section in the main body. The main points we will discuss in the limitations section are the following:\n\n* __Use of the dynamical system formalism:__ this approach yields an elegant and general framework and enables powerful techniques of analysis. However, it comes with a few  draw-backs. Firstly, requiring continuity throughout means that the main work of assigning meaning to the states is done in selecting the state space $X$. Further, the dynamics $f$ needs to have codomain $X$. This can make verifying constructions tedious. In the context of learning parameters for $f$, this also means that as the parameters vary, the state space must change accordingly. Hence, analysing a parametrised model requires considering a family of dynamical systems, which could be further developed as a separate framework within MAT. Nonetheless, the current formulation of MAT allows for indirect analysis of learning stability, via the notion of robustness (as discussed in Section 3.2 on robustness).\n* __Focus on unbounded length expressivity:__ Most of the framework and techniques presented, aside from robustness, study asymptotic behaviour of RNNs. We do not aim to determine e.g. how the number of $\\eta$-components or layers needed grows with input length. Similarly, Krohn-Rhodes decomposition techniques are not suitable for e.g., determining the minimal number of components needed.\n* __Focus on state-space transformations:__ Our framework, and indeed Algebraic Automata Theory, does not directly model the input and output function complexity in the network, which also influences the expressive capacity of the model. We can still indirectly control what transformations are allowed in the network by imposing additional constraints aside from continuity, e.g., like in the geometrically-constrained setting. When we consider cascade constructions, generally connecting functions implementable by MLPs suffice, thanks to separability of components.\n\nWe would like to note that, in our view, points related to the limitations of Algebraic Automata Theory can __potentially motivate a renewed development of the field__, in conjunction with modern expressivity studies. We plan on including a more detailed comparison with alternative frameworks, mentioned in the Related Work section, in the appendix.\n\n## References\n* Maximilian Beck, Korbinian Pöppel, Markus Spanring, Andreas Auer, Oleksandra Prudnikova, Michael Kopp, Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. xLSTM: Extended long short-term memory. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.\n\n* S. Bhattamishra, K. Ahuja, and N. Goyal. On the ability and limitations of transformers to recognize\nformal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural\nLanguage Processing (EMNLP), pages 7096–7116, 2020.\n\n* Yash Sarrof, Yana Veitsman, and Michael Hahn. The expressive capacity of State Space Models: A formal language perspective. In Proceedings of the Thirty-Eighth Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.\n\n* Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Exposing attention glitches with flip-flop language modeling. In Thirty-seventh Conference on Neural Information Processing Systems, 2023"}, {"review_id": "bbL3O0zlGl", "reviewer": "Reviewer_sV21", "summary": "This paper introduces Metric Automata Theory (MAT) that applies to dynamical systems, with the specific case of Recurrent Neural Networks (RNN) typically working on sequences of inputs.\nThe paper presents $\\eta$-finiteness (for a set, being an union of compacts called $\\eta$-component, for a dynamic, having input and state space $\\eta$-finite) $\\eta$-robustness for a dynamic (the transition function always end up in the state space (typically $\\eta$-finite), even if some noise $\\varepsilon$ is added to it) and geometrically-constrained systems.\nThe robustness allows to cover the cases of finite precision implementations without resorting to the general argument of floats being discrete.\nExpressivity results of Vanilla-RNNs, xLSTM and SSM such as MAMBA are derived using MAT, and compared to empirical behaviors for language recognition.", "questions": "- To what extent can the concepts, e.g. finiteness or robustness, be used on actual learned model?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The proposed theory is interesting to take a discrete viewpoint on continuous dynamical systems and understand the behavior of RNNs for language recognition.\nWhile I could not check all the derivations, the paper seem sound.\n\nThe paper introduces many definitions and theorems and it is easy to lose track of the articulation between these and their implications. For instance, some theorems suppose $\\eta$-finiteness and some constructions ensure it, but it is unclear to me if the concepts can be used on trained/learned models beyond these constructions (e.g. can we say or prove that a given model is $\\eta$-finite).\n\nThe paper is probably too dense for the current format (there are 50 pages of supplementary material, which I could not check): while it reads relatively well given the amount of definitions and concepts, the body of the paper would have benefited from illustrations of the main concepts (following some of the figures from the supplementary).\n\nRemarks\n\n- l87: I might be missing a point of definition but how can a continuous function have a finite codomain? \n- l359: about \"predicted by Th. 8\", actually Th. 8 allows mamba to represent the language (\"expressivity\" / \"can recognize\") it but, as far as I understand, nothing is stated about the learnability (the fact that mamba will actually manage to learn the parameters)\n\nLocal comments\n\n- l167: \"give\" -> \"given\"\n- l272: \"start-free\" -> \"star-free\"", "was_revised": true, "final_justification": "This paper is interesting and the discussion period was productive. I am for acceptance, provided the restructuration of the paper is done to improve its exposition.", "rebuttal": "Thank you for your detailed review. We greatly appreciate your in-depth questions and attention to detail.\n\nWe address your question, and then further concerns. We look forward to your response and further suggestions for improving our work.\n\n## Question\n> To what extent can the concepts, e.g. finiteness or robustness, be used on actual learned model?\n\nThe main focus of the paper is to establish a framework to analyse the expressive capacity of RNNs, which concerns whether a certain class of networks admits instances capable of performing certain tasks. Thus, the introduced notions and theorems provide notions and properties that altogether constitute such a framework for the study of expressivity and hence, their primary application is not to learning. Nonetheless, we argue in the paper that they are useful tools for analysing empirical phenomena in learning and for guiding practical decisions. We understand the articulation can be improved, and will do so. Below we provide further discussion for the two central notions: $\\eta$-finiteness and robustness.\n\n**$\\eta$-finitess.** We have developed etafiniteness primarily as a notion for defining our version of the finite-precision framework, while being a more general and easily analisable property. Note, that $\\eta$-finiteness is not necessarily a desirable or undesirable property for a model. Nonetheless, it could be used to analyse the geometry of the state space of trained models, e.g., the number of meaningful “states” a learned model seems to have. For example, using the same approach as was used to obtain Figure 1 (page 8 main body), we can examine how the state sequence of the model looks when processing an input. We have found that for a trained 1 layer Mamba on the FlipFlop task the point clouds for the 1 and 0 states generally form two distinct, linearly separated regions, when looking at the PCA of the inner state channels. This comes with the caveat that not all of the channels show such separation, and sometimes none have perfect linear separability, when looking at the 2d PCA plot. Nonetheless, we can observe that the inner state exhibits “etafiniteness” with this very simple approach. We will add such a visualisation to the supplementary material, to better visualise the connection to actual models behaviour.\n\n**Robustness.** Robustness gives us a way to further connect this notion to concrete finite precision systems, without any simplifying assumptions about floating point arithmetic. We also argue that it is a desirable stability property, separately from the finite precision framework. As for practical applications of robustness, we mainly envision it driving design decisions behind model architectures and training algorithms. For example, the inherent non-robustness of linear RNNs suggests that the solutions that may be learned for the model's parametrisation are very sensitive, especially when it comes to length-generalisation abilities. When it comes to determining what state components a trained model has and whether the state transitions display robustness, we have not pursued this direction, since our work focuses on expressivity. However, the ability to do so could give valuable insight into verifying length-generalisation abilities.\n\n## Further Concerns\n> The paper is probably too dense for the current format (there are 50 pages of supplementary material, which I could not check): while it reads relatively well given the amount of definitions and concepts, the body of the paper would have benefited from illustrations of the main concepts (following some of the figures from the supplementary).\n\nWe plan on adding figures to the main body, to build more visual intuition for the concepts and proof techniques presented. We will add improved versions of the figures present in the supplementary material, as well as new ones. The existing figures we will include in the main body are:\n\n* Figure 3 (page 17 supplementary), visualising correspondence  between the continuous $\\eta$-finite dynamics and the canonical semiautomaton. The last transition will be changed to land in the same component.\n\n* Figure 5 (page 25 supplementary), visualising a concrete datatype covering of a robust dynamics. To the right, we wil merge Figure 4 (page 22 supplementary) together with a symbolic definition of robustness.\n\n* Figure 6 (page 30 supplementary), visualising aperiodicity and the key argument behind Theorem 4\n\n* Figure 1 (main body page 8) visualising empirical behaviour of a trained Mamba model on the FlipFlop task. To the right we will add a diagram of the FlipFlop transitions.\n\nThe new figure we will include in the main body is:\n\n* A figure visualising transitions of a GCS together with the hyperplanes which piecewise separate the state space. To the right we will visualise the key argument behind Theorem 9.\n\nWe will also add figures visualising the constructions in the appendix. Any further suggestions for changes to the figures, or new figures to be added to the appendices, would be greatly appreciated.\n\n>l87: I might be missing a point of definition but how can a continuous function have a finite codomain?\n\nFor a trivial example, any function $X\\to \\set{y_0}$ is continuous–since it is constant, and $\\set{y_0}$ is finite. Alternatively, consider $X_1= [0,1]$ and $X_2=[2,3]$. Similarly, a function on $X_1\\cup X_2$ mapping $X_1$ to $1$ and $X_2$ to $2$ is continuous. \n\nThe key point is that a continuous function can act independently on the disconnected components of the domain.\n\n>l359: about \"predicted by Th. 8\", actually Th. 8 allows mamba to represent the language (\"expressivity\" / \"can recognize\") it but, as far as I understand, nothing is stated about the learnability (the fact that mamba will actually manage to learn the parameters)\n\nThe reviewer is right, the wording is off here. We will change this to more accurately state that  in practice Mamba learns star-free tasks, with length-generalisation—consistent with its expressivity described by Theorem 8."}, {"review_id": "1PtbchP6B0", "reviewer": "Reviewer_MndJ", "summary": "The paper introduces Metric Automata Theory, a novel framework that connects classical automata theory to continuous dynamical systems, particularly focusing on recurrent neural networks (RNNs). It establishes connections between this framework and automata theory to systematically analyze the expressivity of various state-based neural models.", "questions": "Could the authors elaborate more generally on how they envision this framework being utilized in future research? In particular, aside from the demonstrated connection via the \"FLIP-FLOP\" task, what other connections to automata theory might be explored within this new theoretical setting? Making the case that this framework can be extended convincingly, and adding such a section to the paper, will probably result in a raised score.", "limitations": "I feel that the paper would benefit from having a dedicated limitations section, perhaps placed in the appendix. Consolidating caveats (such as those highlighted in the strengths and weaknesses above) into a single location would help readers better understand the context and scope of the presented results.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n1. This paper presents an interesting and powerful framework.\n2. The paper is (at least subjectively) interesting. I enjoyed reading it.\n3. The stated results are strong, insightful, and broadly applicable to a variety of state-based models, including widely-used architectures such as xLSTMs and SSMs.\n4. Although I'm not deeply familiar with all prior related works, the connections drawn are neat and provide a valuable perspective.\n\n**Weaknesses**:\n1. The preliminaries and introduction of dynamics are math-heavy and quite general. The paper's preliminaries are quite heavy. Which is understandable for a paper presenting a new framework, but Iwasn't entirely convinced that all elements presented were strictly necessary. While establishing a connection to automata theory is interesting, it's unclear whether this warrants a fully separate framework.  Specifically, the primary practical usage demonstrated is through the \"FLIP-FLOP\" task, and it's not clear how broadly this connection or generality could be leveraged beyond this specific application. In general, when introducing a new framework, it would be beneficial if the authors explicitly outlined potential future directions, better explained why such generality is necessary\n2. A minor point (much less important then point 1): The results on expressivity assume non-negative eigenvalues for SSMs. However, many widely-used SSM architectures, including LRU, S4, and occasionally Mamba, make use of complex-valued eigenvalues. Prior work has demonstrated that allowing complex parameterizations significantly impacts model expressivity (e.g., \"Provable Benefits of Complex Parameterizations for Structured State Space Models\" and \"Universality of Linear Recurrences Followed by Non-linear Projections: Finite-Width Guarantees and Benefits of Complex Eigenvalues\"). It might thus be worthwhile to mention explicitly that restricting to non-negative eigenvalues constitutes a limitation of the current theory.", "was_revised": true, "final_justification": "I am convinced by the author's claim regarding the importance of the generic connection to automata theory, and therefore, as mentioned in my original review, I raise my score to a 5.\n\nLess importantly, I am also glad the authors will include a limitation section and improve the preliminaries section, as I think this will greatly benefit the paper.", "rebuttal": "Thank you for your review of our work and your detailed questions. We are very glad you found our work interesting and insightful.\n\nWe address your question and then further concerns. We are looking forward to your reply and further questions. \n\n## Question\n> Could the authors elaborate more generally on how they envision this framework being utilized in future research? In particular, aside from the demonstrated connection via the \"FLIP-FLOP\" task, what other connections to automata theory might be explored within this new theoretical setting? Making the case that this framework can be extended convincingly, and adding such a section to the paper, will probably result in a raised score.\n\n__Connection to Automata Theory__. The connection we develop between continuous systems and Automata Theory in the paper serves two main purposes discussed below. Furthermore, Metric Automata Theory is a generalisation of Automata Theory to continuous systems, which is of independent interest. \n\n* The first purpose is using decomposition theorems of AAT to analyse cascades of systems. In our paper, FlipFlop cascade decomposition has a particular importance, because it characterises star-free languages. However, the developed framework is not restricted to FlipFlops and star-free languages. For instance, the modular counting construction in [Grazzi et al., 2025], Theorem 6, is still valid in the etafinite set-up, and so it gives us a positive result for a different class of regular languages. In general, our framework allows for applying AAT to the study of RNN expressivity, in terms of all prime automata, including FilpFlop, modular counters and many others.\n\n* The second reason is more core to the theory as a whole, and perhaps is not emphasised enough throughout the main body. Automata Theory is key in describing the behaviour of a continuous dynamical system in a way that is suitable for theoretical analysis. In particular, the notion of canonical automaton allows us to abstract away the details of behaviour that do not affect expressive capacity.\n\nAs an example, realisability is an algebraic automata concept which is used in proofs of Theorem 2 (realisability of robust systems with sufficient precision) and Theorem 42 (on robust parametrised systems stability), even though the results themselves are not about automata. The general continuous setting is not suitable for considering an analogous definition of realisability, because we do not actually care about realising the local behaviour of a dynamics, just the global behaviour. Thus, the connection to automata is actually __a core tool we use to develop an algebraic theory of continuous systems__.\n\nWe will adjust Section 3.1 to better explain the key part that the connection to automata theory plays in MAT.\n\n__Future Research__. The framework we set up opens up many avenues for future research in connection to automata theory. Krohn and Rhodes decomposition can be further utilised to derive expressivity results using semigroup decomposition hierarchies. Additionally, this connection is central to the overall theory of $\\eta$-finite systems and robustness. We especially see robustness as being of practical interest and as a subject of future research.\n\nWe also believe it has great applicability to natural language tasks, for developing insights on how the way automata arise in the tasks influence models performance. For instance, Theorem 4 states that LRDs cannot robustly implement FlipFlop. However, if we remove the identity transition, that is no longer the case. Essentially, only some kinds of transitions are problematic, and the models performance might improve if it is possible to remove such inputs. Another interesting avenue of future research is on how tokenization affects the models ability to perform state-tracking and realise automata transitions. For example, [Grazzi et al., 2025](paragraph under Theorem 3, page 7) note that allowing more input symbols per transition (eg “3+2+4=4”) allows simpler gates to implement automata.\n\nThe Geometrically-constrained systems theory also utilises the framework of canonical automata, e.g. for Theorem 8. We believe the GCS theory is of theoretical and practical interest, independently of the theory of $\\eta$-finiteness and finite state automata. In particular, we believe it is suitable for investigating expressivity of general formal languages, beyond regular. We are interested in investigating, in future work, counter languages (see e.g., Construction 1) within GCS, e.g. as mentioned in relation to Mamba performance, described in lines 385-388.\n\nWe will add a dedicated Future Research section to the main body to better emphasise these applications.\n\n## Further Concerns\n\n> The results on expressivity assume non-negative eigenvalues for SSMs.\n> It might thus be worthwhile to mention explicitly that restricting to non-negative eigenvalues constitutes a limitation of the current theory.\n\nMost results we present indeed relate to SSMs with non-negative eigenvalues. However, e.g., Theorem 4 applies to SSMs with both real and complex gates and states, without restriction on the eigenvalues. Indeed, a feature of our framework is the ability to work with arbitrary metric spaces. \n\nIn fact, one of the key advantages of the etafinite approach to finite precision is the ability to rigorously consider the state as being a subspace of various ambient spaces, and to e.g., consider the diagonalized space for a particular linear transformation. Such approaches are problematic when working with fixed datatypes, cf. [Grazzi et al., 2025] proof of Theorem 1, where the simplifying arithmetic assumption is needed for diagonalization.\n\nWe will improve the articulation of Section 4.1 to better convey the generality of the results.\n\n> I feel that the paper would benefit from having a dedicated limitations section, perhaps placed in the appendix. Consolidating caveats (such as those highlighted in the strengths and weaknesses above) into a single location would help readers better understand the context and scope of the presented results.\n\nBased on feedback, we intend to add a separate limitations section and future work section in the main body. The main points we will discuss in the limitations section are the following:\n\n* __Use of the dynamical system formalism__: this approach yields an elegant and general framework and enables powerful techniques of analysis. However, it comes with a few  draw-backs. Firstly, requiring continuity throughout means that the main work of assigning meaning to the states is done in selecting the state space $X$. Further, the dynamics $f$ needs to have codomain $X$. This can make verifying constructions tedious. In the context of learning parameters for $f$, this also means that as the parameters vary, the state space must change accordingly. Hence, analysing a parametrised model requires considering a family of dynamical systems, which could be further developed as a separate framework within MAT. Nonetheless, the current formulation of MAT allows for indirect analysis of learning stability, via the notion of robustness (as discussed in Section 3.2 on robustness).\n* __Focus on unbounded length expressivity__: Most of the framework and techniques presented, aside from robustness, study asymptotic behaviour of RNNs. We do not aim to determine e.g. how the number of $\\eta$-components or layers needed grows with input length. Similarly, Krohn-Rhodes decomposition techniques are not suitable for e.g., determining the minimal number of components needed.\n* __Focus on state-space transformations__: Our framework does not directly model the input and output function complexity in the network, which also influences the expressive capacity of the model. We can still indirectly control what transformations are allowed in the network by imposing additional constraints aside from continuity, e.g., like in the geometrically-constrained setting. When we consider cascade constructions, generally connecting functions implementable by MLPs suffice, thanks to separability of components.\n\nWe would like to note that, in our view, points related to the limitations of Algebraic Automata Theory can __potentially motivate a renewed development of the field__, in conjunction with modern expressivity studies. We plan on including a more detailed comparison with alternative frameworks, mentioned in the Related Work section, in the appendix.\n\n>The preliminaries and introduction of dynamics are math-heavy and quite general. The paper's preliminaries are quite heavy.\n\nTo address that, we plan to reduce the content of Section 2 Preliminaries, in favour of giving more details on the proofs and techniques used in Section 4.\n\n## References\n* Riccardo Grazzi, Julien Siems, Arber Zela, Jörg K. H. Franke, Frank Hutter, and Massimiliano Pontil. Unlocking state-tracking in linear RNNs through negative eigenvalues. In Proceedings of the Thirteenth International Conference on Learning Representations (ICLR), 2025."}, {"review_id": "Xxp8u2N8kY", "reviewer": "Reviewer_ycc4", "summary": "## Summary\nIn this paper the authors propose a unifying theory to mainly study the expressivity of Recurrent Neural Networks (RNNs) from a language-theory point of view. The principle linking continuous dynamical systems to finite-state machines such as Automata, is the discretization of latent space (hidden space). In this work, the authors turn to the tools of algebra/topology to partition the latent space into disjoint subspaces forming equivalence classes. Based on this approach, the authors derive a number of notions such as $\\eta-$finiteness, $\\eta-$convergence, $\\epsilon-$rebustness, to name just a few. These notions form the basis of theoretical results on the expressivity power of RNNs, for example, the non-$\\epsilon-$rebustness of SSMs, a widespread class of recurrent neural networks.", "questions": "## Questions\n\n- Have you thought of a way of analyzing the latent space to determine equivalence classes more accurately? If not, do you have in mind a construction of an RNN that has a latent space that is well split into equivalence classes, and that is not the trivial split derived from finite precision?\n\n- The previous question brings me to this one. Do you think there is a non-trivial way to apply the Krohn-Rhodes theorem to RNNs, from a practical point of view? There are algorithms for doing cascade decomposition of semigroups, but the compléxité is often of type $n^n$, which is not tractable at all when the discretization of the latent space is derived from finite precision.", "limitations": "The fact that any RNN implemented in finite precision is $\\eta-$finite is not in doubt, but if we take a vanilla RNN with $h_{t+1} = \\sigma\\left(Ux_t + Wh_t + b\\right)$, where the dimension of the vector $h_t$ is $d\\geq1$. The sigmoidal function has values in $[0,1]$, and the interval $[0,1]$ in finite precision is finite, so $\\Gamma := Card([0,1])$. So if there is not a more refined way of determining $\\eta$ once we want to associate a state machine to the RNN, we will potentially end up with a number of states $\\approx \\Gamma^d$.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## The strengths\n- The article is well written.\n- The subject matter is complicated and of great interest to the community.\n- The ambition of the work is to propose a unifying theory for RNN studies, and indeed the proposed theoretical framework has the potential to fulfill this role.\n## Weaknesses\n- There are no illustrations. For a mathematician, the concepts are accessible, but this may not be the case for practitioners who have no grounding in abstract algebra. I think an illustration or two to represent equivalence classes would be a big plus.\n- From a mathematical point of view, the work is rigorous and all the proofs, in my view, are valid. Nevertheless, the results demonstrated are not innovative. All the proofs are based on known techniques and the assertions are not surprising.\nThe authors propose the notion of $\\eta-$finitness, and provide several constructions of xLSTM and Elman RNN that are $\\eta-$finite and $\\epsilon-$robust. Nevertheless, it is not clear, outside the framework of finite precision, whether RNNs have the characteristic of being $\\eta-$finite. \n- Empirical validation comes from other works, and concerns only SSM-type models.\n- In my opinion, the 9-page format is not at all appropriate for this work. A large part of the notions and proofs ended up in the appendix. I feel that a theoretical article should at least provide a sketch of proof of the theorems announced, in the article section.", "was_revised": true, "final_justification": "Rephrase the article so that ideas for proof techniques appear in the body of the text. Possibly illustrate key concepts to make the article more easily recognizable and digestible for readers.", "rebuttal": "Thank you for your in depth review. We are glad that you found our work well-written, and that it has the potential to be unifying for the field.\n\nWe address your questions, and then concerns in order. However, we feel there might be some overall confusion related to etafiniteness, so we first provide some clarification on this aspect.\nWe look forward to your further feedback and thoughts.\n\n## $\\eta$-finiteness\n$\\eta$-finiteness is primarily a framework for describing RNN expressivity, and deriving results for concrete finite precision implementations. $\\eta$-finiteness is a mathematical property of a continuous system, regardless of whether it is realised in finite precision. It is worth noting that systems with infinite cardinality state space can be $\\eta$-finite.\n\n## Questions\n> Have you thought of a way of analyzing the latent space to determine equivalence classes more accurately? If not, do you have in mind a construction of an RNN that has a latent space that is well split into equivalence classes, and that is not the trivial split derived from finite precision?\n\nWe feel there might be some misunderstanding related to the notion of etafiniteness. See clarification above.\n\nFor an example of such an RNN that is not linear, consider the construction of FlipFlop for a $\\tanh$ activated neuron, Section G.3.3 in the appendix. Its state space has 2 equivalence classes: $[-1.1, \\tanh(-1)]\\approx [-1.1, -0.76]$ and $[\\tanh(1), 1.1] \\approx [0.76, 1.1]$. Now, for a finite precision implementation, we can still assign these equivalence classes, as long as the error with which tanh is computed is less than $0.1$, due to robustness of the dynamics. Note that in this case, the RNN has the state-space well-split (consistent with the dynamics) that is not the trivial split derived from finite precision.\n\n> The previous question brings me to this one. Do you think there is a non-trivial way to apply the Krohn-Rhodes theorem to RNNs, from a practical point of view? There are algorithms for doing cascade decomposition of semigroups, but the compléxité is often of type $n^n$, which is not tractable at all when the discretization of the latent space is derived from finite precision.\n\nWe are not sure there is much practical applicability of computing the full decomposition. Aside from computational constraints, Krohn-Rhodes does not tell us e.g. what the complexity of the connecting functions should be. However, just knowing what prime factors the transition semigroup has can be helpful in picking the architecture. For instance, knowing that the largest factor has $N$ states tells us that it is realisable by a cascade of $N$-state automata. This could potentially guide decisions about dimension size of hidden states, tokenization or quantization algorithms. [Grazzi et al., 2025] on page 7 discusses the connection between the number of tokens per transition and the GH matrix depth required for the transition—e.g. having 2 tokens, like in “3+2+4=4” essentially allows the model two steps per transition.\n\n## Further Concerns \n\n> There are no illustrations.\n\nWe plan on adding figures to the main body, to build more visual intuition for the concepts and proof techniques presented. We will add improved versions of the figures present in the supplementary material, as well as new ones. The existing figures we will include in the main body are:\n\n* Figure 3 (page 17 supplementary), visualising correspondence between the continuous $\\eta$-finite dynamics and the canonical semiautomaton. The last transition will be changed to land in the same component.\n\n* Figure 5 (page 25 supplementary), visualising a concrete datatype covering of a robust dynamics. To the right, we wil merge Figure 4 (page 22 supplementary) together with a symbolic definition of robustness.\n\n* Figure 6 (page 30 supplementary), visualising aperiodicity and the key argument behind Theorem 4\n\n* Figure 1 (main body page 8) visualising empirical behaviour of a trained Mamba model on the FlipFlop task. To the right we will add a diagram of the FlipFlop transitions.\n\nThe new figure we will include in the main body is:\n\n* A figure visualising transitions of a GCS together with the hyperplanes which piecewise separate the state space. To the right we will visualise the key argument behind Theorem 9.\n\nWe will also add figures visualising the constructions in the appendix. Any further suggestions for changes to the figures, or new figures to be added to the appendices, would be greatly appreciated.\n\n> Nevertheless, the results demonstrated are not innovative. All the proofs are based on known techniques and the assertions are not surprising.\n\n\nWe would like to emphasise that our approach is innovative and leads to novel results, including surprising ones. We expand on this by discussing concrete points.\n\n* First, our result on Mamba being unable to implement FlipFlop is in contrast to the existing literature. This is a surprising and important fact, which was missed in the existing experimental evaluation due to limited length of considered inputs. This new result calls for a rethinking of the empirical validation process for unbounded-length expressivity results, as the current approach of testing for limited length-generalisation is inadequate and only shows the partial picture.\n\n* Second, our results on robustness and geometrically-constrained systems (GCS) introduce novel insights into existing experimental results on RNNs. In particular, GCS allows, for the first time, to describe the mode of limited length-generalisation which Mamba displays on star-free tasks such as FlipFlop. \n\n* Third, our framework is innovative and has the potential of accelerating future research, as well as making it more rigorous. We demonstrate this by proving existing results of [Sarrof et al., 2024] and [Grazzi et al., 2024] within the etafiniteness framework. While these particular results are known, within our framework we are able to simplify the proof technique. Moreover, the proofs in [Sarrof et al., 2024] had an issue of asserting without proof that convergence of the analytical form of the state sequence implies it being eventually constant, on account of finite precision, which is not necessarily the case. On the other hand, the set up of [Grazzi et al., 2024] required simplifying assumptions about finite-precision arithmetic. Our approach’s contribution is making the intuitive arguments in Sarrof rigorous, and moreover being able to obtain results on concrete finite precision implementations via robustness. \n\n\n>Nevertheless, it is not clear, outside the framework of finite precision, whether RNNs have the characteristic of being $\\eta$-finite.\n\nDetermining whether a given model is etafinite is an interesting point for further study. Please see also the first paragraph of our response to Reviewer sV21.\n\n>In my opinion, the 9-page format is not at all appropriate for this work.\n\nThe main objective of our work is to present a new unifying framework for RNN research, and motivate its capabilities to explain empirical results and inform future research, so that hopefully it gains adoption in the wider community. Now, we think that the conference format, even though not capable of containing the entire technical work, will expose our framework to a wider audience, increasing its chances of becoming a unified framework for future studies.\n\nNow, we hope that the main body can achieve two objectives. The first one is to provide a digestible overview of our main results, to demonstrate the capabilities of MAT, as well as to share our new insights. The second one is to serve as a starting point to the supplementary material, for those interested in theoretical expressivity study of RNNs, so that they can further investigate the introduced notions, or invent new frameworks within MAT, such as GCS.\n\n>  I feel that a theoretical article should at least provide a sketch of proof of the theorems announced, in the article section.\n\nWe plan to reduce the size of Section 2 Preliminaries in favour of giving more details on the proofs and techniques used in Section 4. Additionally, the figures we will include in the main body illustrate key ideas behind some of the proofs.\n\n> Empirical validation comes from other works, and concerns only SSM-type models.\n\nIt is true that we focus on developing the theoretical framework, deferring new experiments to future work. It should be noted that we also consider results for xLSTM and LSTM, in addition to SSM-type models.\n\n> [...] So if there is not a more refined way of determining $\\eta$ once we want to associate a state machine to the RNN, we will potentially end up with a number of states $\\approx \\Gamma^d$.\n\nWe feel there might be some misunderstanding related to the notion of $\\eta$-finiteness. See clarification above. Please also note that $\\eta$ is not a variable, unlike in the case of $\\epsilon$-robustness or $\\epsilon$-nets. It is just a name, like $\\beta$-reduction.\n\nImportantly, the number of $\\eta$-states is not immediately related to the numerical precision used to implement the dynamics.\n\nRegarding the vanilla RNN within etafinite framework, regardless of any finite datatype considerations, it is possible to implement FlipFlop where we have 2 equivalence classes—the construction is analogous to the $\\tanh$ one mentioned above. Furthermore, this construction can be shown to be robust, and hence by our theory the equivalence classes will be valid in finite precision representation, given sufficient precision. Explicitly, the floating points lying within one of the two equivalence classes will be mapped in a consistent way. Thus it is possible to consider such a finite-precision system as having 2 meaningful states.\n\n## References\n* Sarrof et al., The expressive capacity of State Space Models: A formal language perspective. (NeurIPS), 2024.\n* Grazzi et al., Unlocking state-tracking in linear RNNs through negative eigenvalues. (ICLR), 2025."}]

Author rebuttal:

Meta-review: This theoretical paper introduces a generalization of classic automata theory to continuous dynamical systems named Metric Automata Theory.  This theory provides a unified way  to study the expressiveness of families of models based on Recurrent Neural Networks including xLSTMs and State Space Models. The paper provides results studying the capacity of some models to recognize of approximate star-free regular languages. An important aspect of the framework is its capacity of studying expressivity in both finite-precision and beyond finite precision.   

Based on the reviews, the following strengths have been identified:  
-Novel and elegant generalization of automata theory.  
-Strong and novel results.  
-Interesting discrete viewpoint on continuous dynamical systems.    
-Helpful to understand the behavior of RNNs for language recognition.    

The following weaknesses have also been identified:   
-paper very dense with 50pages of appendix, sometimes hard to follow.  
-lack of illustrations and explanations.   
-the implication of the results for learning was slightly discussed but not really explored.  
-rather limited experimental evaluation.    

During rebuttal, authors have provided multiple answers to the different remarks raised and their answers were globally satisfying for most of the reviewers. During final evaluation and discussion:   
-Reviewer RX1U thinks that this is relevant paper and proposes acceptance.   
-Reviewer sV21 was favorable to acceptance provided that a restructuring of the paper is done to improve its exposition.  
-Reviewer MndJ was convinced by the author's claim regarding the importance of the generic connection to automata theory, he appreciates the scope and strength of the contribution. He is also highly favorable to the inclusion of a limitation section and requires to improve the preliminaries section, to improve the presentation of the paper.  
-Reviewer ycc4 appreciated the solidity of the contribution and the perspective of unification theory for RNN studies. He also required to rephrase the article so that ideas for proof techniques appear in the body of the text and possibly to illustrate key concepts to make the article more easily recognizable and digestible for readers.  

Overall, 3 reviewers propose direct acceptance and the other one leans toward weak acceptance which shows a clear consensus towards acceptance.  
If the weaknesses raised were still present, they are outweighed by the correctness, originality, and usefulness of the results for developing more expressive recurrent models.  
I read the paper and I agree that the contribution is solid providing a nice supporting theory for studying recurrent models.  

I propose then accept for this paper.   
Nevertheless, I urge the authors to take into account the requests made by the reviewers to improve the presentation of the paper, notably those made by reviewers sV21, MndJ and ycc4. The authors final remarks make me confident on the fact that the authors will update their paper accordingly.
Decision: Accept (poster)