# The grammar of the Ising model: A new complexity hierarchy

Tobias Reinhart<EMAIL_ADDRESS>Gemma De las Cuevas  Institute for
Theoretical Physics, University of Innsbruck, Technikerstr. 21a, A-6020
Innsbruck, Austria

###### Abstract

How complex is an Ising model? Usually, this is measured by the computational
complexity of its ground state energy problem. Yet, this complexity measure
only distinguishes between planar and non-planar interaction graphs, and thus
fails to capture properties such as the average node degree, the number of
long range interactions, or the dimensionality of the lattice. Herein, we
introduce a new complexity measure for Ising models and thoroughly classify
Ising models with respect to it. Specifically, given an Ising model we
consider the decision problem corresponding to the function graph of its
Hamiltonian, and classify this problem in the Chomsky hierarchy. We prove that
the language of this decision problem is (i) regular if and only if the Ising
model is finite, (ii) constructive context free if and only if the Ising model
is linear and its edge language is regular, (iii) constructive context
sensitive if and only if the edge language of the Ising model is context
sensitive, and (iv) decidable if and only if the edge language of the Ising
model is decidable. We apply this theorem to show that the 1d Ising model, the
Ising model on generalised ladder graphs, and the Ising model on layerwise
complete graphs are constructive context free, while the 2d Ising model, the
all-to-all Ising model, and the Ising model on perfect binary trees are
constructive context sensitive. We also provide a grammar for the 1d and 2d
Ising model. This work is a first step in the characterisation of physical
interactions in terms of grammars.

##  I Introduction

Figure 1: (Left and Middle) We fully classify the properties of an Ising model
$\mathcal{M}$ that determines the complexity of its language ${\sf
L}_{\mathcal{M}}$ in the refined Chomsky hierarchy (Theorem 1). (Right) We
apply this classification to show that the language of the 1d Ising model is
constructive context free; the language of the Ising model on perfect binary
trees, 2d lattices, and all-to-all interaction graphs is constructive context
sensitive (Section IV).

Spin models are a powerful tool to model complex systems. While the
paradigmatic spin model, the Ising model [1, 2, 3], was originally proposed as
a stripped-off model of magnetism, it has since been used in a remarkable
variety of settings, including as a toy model of matter in certain quantum
gravity models [4], to model gases (via so-called lattice gas models) [5], in
knot theory (via the connection of the Jones polynomial with the partition
function of the Potts model in a certain parameter regime) [6], for artificial
neural networks (stemming from Hopfield’s proposal) [7, 8], in ecology (e.g.
to model the size of canopy trees) [9], to model flocks of birds [10], viruses
as quasi-species [11, 12], genetic interactions [13], for protein folding [14,
15, 16, 17] (together with its generalisation, the Potts model [18]), for
economic opinions, urban segregation and language change [19], for random
language models [20], social dynamics [21], earthquakes [22] and the US
Supreme Court [23], to name some. The relevant questions differ for each of
these applications—e.g. for artificial neural networks, one is interested in a
“driven” Ising model, where the parameters are updated (corresponding to
learning) and one may study convergence rates, whereas in complex systems [9],
one may be interested in the behaviour of the Ising model at criticality.
Whatever the focus may be, the fact is that this very simplified model
provides insights into very different problems.

Depending on the application, the Ising model is considered on different
families of interaction graphs, such as lattices of a certain dimensionality
for magnetism, or (layerwise) complete graphs for artificial neural networks.
How does one characterise these different Ising models? In particular, how can
we measure the complexity of Ising models on different families of graphs?
Traditionally, this is measured by the computational complexity of the ground
state energy problem (GSE), which asks:

> Given an interaction graph for $n$ spins and an integer $k$, does there
> exist a spin configuration with energy below $k$?

For the Ising model without fields, if the family of interaction graphs is
planar, this problem is in P, and if it is non-planar, it is NP-complete [24,
25] 111P (NP) is the class of decision problems solvable in polynomial time by
a (non)-deterministic Turing machine.. These results have given rise to strong
and fruitful ties between spin models (and, more generally, statistical
mechanics) and computational complexity [27, 28]. For example, one can
formulate many NP problems in terms of the GSE[29].

Yet, this measure is very coarse: It only classifies Ising models depending on
whether they are defined on planar or non-planar graphs (resulting in a two-
level hierarchy of P and NP-complete, respectively). It is insensitive to the
dimensionality of the interaction graph (when considering lattices), the
number of long range interactions, or the average node degree. This might be
due to the facts that GSE only ‘cares’ about the low energy sector of the
model, and that computational complexity tends to gloss over polynomial
factors. Clearly, a 1d Ising model has a different local structure than a 2d
Ising model, yet this distinction is invisible in the traditional measure. Can
one devise a measure that captures the complexity of the local structure of an
Ising model?

In this work, we introduce a new complexity measure for Ising models and
thoroughly classify them in it. We do so in three steps. First, given an Ising
model $\mathcal{M}$ we define its language ${\sf L}_{\mathcal{M}}$ which
encodes the function graph of its Hamiltonian $H_{\mathcal{M}}$, that is, the
set of all pairs of spin configurations and their energy,

${\sf L}_{\mathcal{M}}=\\{(x,H_{\mathcal{M}}(x))\mid x\textrm{ is a spin
configuration of }\mathcal{M}\\}$ (1)

Second, we consider the problem of deciding ${\sf L}_{\mathcal{M}}$, that is:

> Given $(x,E)$, is $x$ is a valid spin configuration of $\mathcal{M}$ and is
> $E=H_{\mathcal{M}}(x)$?

Third, we measure the hardness of this problem by classifying ${\sf
L}_{\mathcal{M}}$ in a (refined) Chomsky hierarchy. This answers the question:

> What is the simplest type of grammar (automaton) that generates (accepts)
> ${\sf L}_{\mathcal{M}}$?

Note that in computational complexity one characterises the resources (in
time, space or non-determinism) that a Turing machine needs to recognise the
language. Since the language of most Ising models can be decided in polynomial
time by a deterministic Turing machine, computational complexity is
insufficient to distinguish among their local structures, whereas the Chomsky
hierarchy can achieve that. The refinement of the Chomsky hierarchy stems from
posing restrictions on the automata that accept context free and context
sensitive languages, resulting in two levels called constructive context free
and constructive context sensitive (Fig. 1), which we conjecture to coincide
with context free and context sensitive, respectively.

We prove that (Theorem 1):

  1. (i)

${\sf L}_{\mathcal{M}}$ is regular if and only if $\mathcal{M}$ is finite;

  2. (ii)

${\sf L}_{\mathcal{M}}$ is constructive context free if and only if
$\mathcal{M}$ is linear and ${\sf E}_{\mathcal{M}}$ is regular;

  3. (iii)

${\sf L}_{\mathcal{M}}$ is constructive context sensitive if and only if ${\sf
E}_{\mathcal{M}}$ is context sensitive; and

  4. (iv)

${\sf L}_{\mathcal{M}}$ is decidable if and only if ${\sf E}_{\mathcal{M}}$ is
decidable.

This classification fully characterises the complexity of ${\sf
L}_{\mathcal{M}}$ in terms of properties of the interaction graphs of
$\mathcal{M}$. Specifically, the edge language ${\sf E}_{\mathcal{M}}$ encodes
which spins interact, and its complexity captures how difficult it is to
decide whether two spins interact or not. The remaining properties of
$\mathcal{M}$ (being finite or linear) encode how the number of interactions
grows with the system size.

We then apply this classification to common families of interaction graphs,
and show that (Fig. 3):

  1. (i)

The language of the 1d Ising model with open or periodic boundary conditions,
the Ising model on ladder graphs, and the Ising model on layerwise complete
graphs is constructive context free. All of these Ising models are linear and
their edge language is regular.

  2. (ii)

The language of the Ising model on perfect binary trees and the 2d Ising model
is constructive context sensitive. All of these Ising models are linear and
their edge language is context sensitive.

  3. (iii)

The language of the all-to-all Ising model is constructive context sensitive.
This Ising model is not linear and its edge language is regular.

Note that a similar approach was recently proposed in [30], yet for a more
general definition of spin model which only achieves a partial
characterisation in the Chomsky hierarchy. The present focus on the Ising
model allows us to promote the partial characterisation to a thorough
classification. In particular, this work identifies which properties of the
interaction graphs play a role in the complexity of the model, and specifies
how they interact (metaphorically) to increase the complexity.

This paper is structured as follows. In Section II we define the new
complexity measure for Ising models. In Section III we define several
properties of Ising models and state our main result, Theorem 1, which we
prove in Appendix A. In Section IV we apply our main result to obtain the
complexity of some well-known examples of Ising models, and in Section V we
conclude and present an outlook. In Appendix B we list some basic definitions
and results from formal language and automata theory, and in Appendix C we
provide explicit grammars of the 1d and 2d Ising model.

##  II A new complexity measure for Ising models

Here we define the new complexity measure for Ising models. In Section II.1 we
define the concept of an Ising model $\mathcal{M}$ and explain how the
function graph of its Hamiltonian is encoded as a formal language ${\sf
L}_{\mathcal{M}}$. In Section II.2 we define how the complexity measure for
$\mathcal{M}$ is obtained by classifying ${\sf L}_{\mathcal{M}}$ in the
Chomsky hierarchy.

###  II.1 The Ising model and its language

What is an Ising model? That depends on the context: the system size may be
pre-determined, unspecified, or defined in the thermodynamic limit.
Additionally, the couplings may be fixed or drawn from a probability
distribution, in which case it is usually called a spin glass. In this work,
an Ising model is defined as follows.

######  Definition 1 (Ising model).

An _Ising model_ $\mathcal{M}$ is a pair
$\mathcal{M}=(N_{\mathcal{M}},E_{\mathcal{M}})$, where

$\displaystyle N_{\mathcal{M}}\subseteq\mathbb{N}$ (2) $\displaystyle
E_{\mathcal{M}}=\\{(E_{\mathcal{M}})_{n}\mid n\in N_{\mathcal{M}}\\}$ (3)

and

$(E_{\mathcal{M}})_{n}\subseteq\\{(i,j)\mid i,j\in\\{1,\ldots,n\\},i<j\\}$ (4)

defines an undirected, ordered graph with vertex set
$V_{n}\coloneqq\\{1,\ldots,n\\}$ that has no isolated vertices. An Ising model
$\mathcal{M}$ defines a _Hamiltonian_ $H_{\mathcal{M}}$:

$\displaystyle\begin{aligned} H_{\mathcal{M}}:\bigcup_{n\in
N_{\mathcal{M}}}\\{0,1\\}^{n}&\rightarrow\mathbb{Z}\\\ s_{1}\ldots
s_{n}&\mapsto\sum_{(i,j)\in(E_{\mathcal{M}})_{n}}h(s_{i},s_{j})\end{aligned}$
(5)

where $h(s_{i},s_{j})=-1$ if $s_{i}=s_{j}$ and $+1$ else.

In words, $N_{\mathcal{M}}$ specifies the system sizes for which $\mathcal{M}$
is defined, and for each $n\in N_{\mathcal{M}}$, the edge set
$(E_{\mathcal{M}})_{n}$ describes how the system of $n$ spins interacts.
Specifically, if there is an edge $(i,j)\in(E_{\mathcal{M}})_{n}$, spins $i$
and $j$ interact. We require that no vertex is isolated (i.e. that every
vertex is contained in at least one edge) because isolated vertices correspond
to non-interacting spins, which do not contribute to the Hamiltonian.

This definition could be generalised to include non-constant couplings or
higher order interactions, e.g. by using hyperedge-labeled hypergraphs (see
e.g. [31]), as done in [30]. Yet, in this work we focus on the constant
coupling case in order to classify the complexity of Ising models solely based
on their interaction structure.

Note that $\mathcal{M}$ is generally defined for an infinite set of system
sizes, and that it is not defined in the thermodynamic limit ($n\to\infty$).
Both are crucial for encoding $H_{\mathcal{M}}$ as a language, as finitely
many system sizes would result in a finite language (which is trivially
regular), and the thermodynamic limit would require infinite strings
(precluding the use of formal languages).

Finally, note that in Definition 1 the vertices of the interaction graphs have
an order, as imposing such an order is necessary when encoding graphs as
strings, and thus a family of graphs as a language. Ultimately this is due to
the fact that symbols in a string have a canonical order, while vertices in a
graph do not. Disposing of the order of the vertices would require considering
equivalence classes of encodings of graphs (where two strings are equivalent
if they encode the same graph), and measuring the complexity of an Ising model
would require a minimisation over all equivalent encodings of that Ising
model. The latter would involve, in particular, solving the graph isomorphism
problem. Alternatively, such an order could be disposed of by casting spin
models as graph languages (see the Conclusions and Outlook).

In order to define the language of an Ising model, let $u$ denote the unary
encoding of integers

$\displaystyle\begin{aligned} u:\mathbb{Z}&\rightarrow\\{+,-\\}^{*}\\\
u(z)&\coloneqq\begin{cases}\epsilon&\text{if}\ z=0\\\ +^{z}&\text{if}\ z>0\\\
-^{-z}&\text{else}\end{cases}\end{aligned}$ (6)

Note that here $+$ and $-$ are just symbols, not mathematical operations.

######  Definition 2 (Language of an Ising model).

Let $\mathcal{M}$ be an Ising model. The _language of_ $\mathcal{M}$, ${\sf
L}_{\mathcal{M}}$, is defined as

${\sf L}_{\mathcal{M}}\coloneqq\\{s_{1}\ldots s_{n}\bullet
u(H_{\mathcal{M}}(s_{1}\ldots s_{n}))\mid\\\ n\in
N_{\mathcal{M}},s_{i}\in\\{0,1\\}\\}$ (7)

In words, ${\sf L}_{\mathcal{M}}$ encodes the function graph of
$H_{\mathcal{M}}$. Explicitly, we use the symbol $\bullet$ as a separator
between spin configurations and energies. Let $\sigma\in\\{+,-\\}$. A string
$s_{1}\ldots s_{n}\bullet\sigma^{k}$ is contained in ${\sf L}_{\mathcal{M}}$
if $s_{1}\ldots s_{n}$ is a spin configuration from the domain of
$H_{\mathcal{M}}$ and $\sigma^{k}$ equals the unary encoding of
$H_{\mathcal{M}}(s_{1}\ldots s_{n})$.

Note that the energy is encoded in unary, as this leads to a more fine-grained
classification in the Chomsky hierarchy. Specifically, encoding the energy in
binary would render the addition of individual energy contributions context
sensitive and not context free, and we would lose one entire level of our
complexity hierarchy (Fig. 1). The increase in complexity caused by a binary
encoding has also been observed from a different angle in Ref. [30].

###  II.2 The complexity measure provided by the Chomsky hierarchy

We now classify ${\sf L}_{\mathcal{M}}$ in the Chomsky hierarchy. To that end,
we define two additional levels of the Chomsky hierarchy which are obtained by
posing restrictions on the automata that accept context free and context
sensitive languages, namely constructive context free and constructive context
sensitive. We will conjecture that these two new levels are identical with
context free and context sensitive, respectively.

PDAs and LBAs are defined in Definition 9 and Definition 11, respectively. Let
us now define their constructive versions.

######  Definition 3 (Constructive automaton).

Let $\mathcal{M}$ be an Ising model and ${\sf L}_{\mathcal{M}}$ be its
language.

  1. (i)

A PDA $P$ that decides ${\sf L}_{\mathcal{M}}$ is called _constructive_ if for
any $n\in N_{\mathcal{M}}$, there exists a unique partition of edges of
$(E_{\mathcal{M}})_{n}=\bigcup_{m=1}^{r_{n}}I_{m}$, such that on well-formed
inputs $s_{1}\ldots s_{n}\bullet\sigma^{k}$, $P$ operates as follows:

    1. (a)

First, $P$ accumulates $u(H_{\mathcal{M}}(s_{1}\ldots s_{n}))$ on its stack.
$P$ iterates over $m=1,\ldots,r_{n}$, and in each step of the iteration it
stores the states of the spins that interact according to $I_{m}$,

$\displaystyle\begin{aligned} V_{n}|_{I_{m}}&\coloneqq\\{i\in V_{n}\mid\exists
j\in V_{n}\\\ &s.t.\ (i,j)\in I_{m}\ \text{or}\ (j,i)\in
I_{m}\\}\end{aligned}$ (8)

in its states. $P$ then adds the unary encoding of the energy contribution of
those spins

$\displaystyle H_{\mathcal{M}}|_{I_{m}}\coloneqq\sum_{(i,j)\in
I_{m}}h(s_{i},s_{j})$ (9)

to its stack.

    2. (b)

Second, $P$ compares its stack content, $u(H_{\mathcal{M}}(s_{1}\ldots
s_{n}))$ to the input energy $\sigma^{k}$ and accepts if and only if they are
equal.

  2. (ii)

A LBA $M$ that decides ${\sf L}_{\mathcal{M}}$ is called _constructive_ if it
uses a designated energy tape $T_{e}$ to accumulate the energy
$H_{\mathcal{M}}(s_{1}\ldots s_{n})$ in binary, compares the content of
$T_{e}$ to the input energy and accepts if and only if the two values
coincide.

For the constructive PDA, note that there exists an upper bound for the size
of $I_{m}$, as by definition a constructive PDA must be able to store all spin
states contained in $V_{n}|_{I_{m}}$ in its states.

In words, a constructive automaton works the way one naively expects: it adds
up local energy contributions in a pre-determined way, and then compares the
result to the input energy. In particular, constructive automata compute
$H_{\mathcal{M}}$ as a function. Working with constructive automaton thus
ensures that we consider the function problem of computing $H_{\mathcal{M}}$,
although for technical reasons, we formulate it as a decision problem
(deciding the function graph of $H_{\mathcal{M}}$) so that we can work with
the Chomsky hierarchy. We conjecture that the constructive condition on the
automata is not necessary:

######  Conjecture 1.

For every context free ${\sf L}_{\mathcal{M}}$ there exists a constructive PDA
that decides it. For every context sensitive ${\sf L}_{\mathcal{M}}$ there
exists a constructive LBA that decides it.

In this work, we do not assume that this conjecture is true, i.e. we
explicitly state whenever we require that an automaton is constructive.

Constructive PDA and constructive LBA define two new complexity levels for
${\sf L}_{\mathcal{M}}$. If ${\sf L}_{\mathcal{M}}$ is decided by a
constructive PDA, we say that ${\sf L}_{\mathcal{M}}$ is constructive context
free; if ${\sf L}_{\mathcal{M}}$ is decided by a constructive LBA, we say that
${\sf L}_{\mathcal{M}}$ is constructive context sensitive (cf. Fig. 1).
Considering only languages of the type ${\sf L}_{\mathcal{M}}$, constructive
context free is a subset of context free, and constructive context sensitive
is a subset of context sensitive. We now show that supplementing the Chomsky
hierarchy with these two complexity levels still forms a hierarchy, i.e. that
regular is a subset of constructive context free and context free is a subset
of constructive context sensitive.

######  Proposition 1 (Refined Chomsky hierarchy).

Let $\mathcal{M}$ be an Ising model and ${\sf L}_{\mathcal{M}}$ be its
language.

  1. (i)

If ${\sf L}_{\mathcal{M}}$ is regular then it is constructive context free.

  2. (ii)

If ${\sf L}_{\mathcal{M}}$ is context free then it is constructive context
sensitive.

###### Proof.

Starting with (i), if ${\sf L}_{\mathcal{M}}$ is regular then by Theorem 1
(i), $\mathcal{M}$ is finite, i.e. there exists a maximum system size. Hence
we can build a PDA $P$ that on input $s_{1}\ldots s_{n}\bullet\sigma^{k}$
reads and stores all spin symbols. As there are finitely many, this can be
done with a finite number of states. Next $P$ adds the entire energy
$H_{\mathcal{M}}(s_{1}\ldots s_{n})$ to its stack. This can be hardwired in
the transition rules. Finally $P$ compares its stack to the input energy
$\sigma^{k}$ and accepts if and only if they are equal. Note that $P$ is
trivially constructive. For all system sizes, the partition of edges consists
of one element only, namely the entire edge set.

Next we prove (ii). As ${\sf L}_{\mathcal{M}}$ is context free, it has a
context free grammar in Greibach normal form [32, Lecture 21]. From this
grammar, one can build a PDA $P$ without $\epsilon$-transitions that decides
this language [32, Lecture 24]. Each transition rule of $P$ pushes at most $k$
symbols to the stack. As there are no $\epsilon$-transitions, $P$ uses an
amount of stack memory that is linear in the length of the input. $P$ can
hence be simulated by a LBA $M$ simply by using an additional tape to simulate
the linear bounded stack of $P$. We now show that this LBA can be assumed to
be constructive. First note that when processing any well-formed input
$s_{1}\ldots s_{n}\bullet\sigma^{k}$, once the head of $P$ reaches $\bullet$,
$P$ has stored the energy $H_{\mathcal{M}}(s_{1}\ldots s_{n})$ either on its
stack, in its states or by using a combination of both, as otherwise $P$ could
not decide if $u(H_{\mathcal{M}}(s_{1}\ldots s_{n}))=\sigma^{k}$. It follows
that, when $M$ simulates $P$, $M$ stores $H_{\mathcal{M}}(s_{1}\ldots s_{n})$
at some point during the computation and we can w.l.o.g. assume that $M$
stores this energy in binary, which makes it constructive. ∎

Finally, we can define the complexity measure for Ising models: The complexity
of an Ising model is obtained by classifying its language in the (refined)
Chomsky hierarchy. The latter induces a complexity hierarchy of Ising models
themselves.

######  Definition 4 (Complexity measure).

Let $\mathcal{M}$ be an Ising model. We say that $\mathcal{M}$ has complexity
$X$ if its language ${\sf L}_{\mathcal{M}}$ belongs to level $X$ of the
(refined) Chomsky hierarchy. Here $X$ can be any of the following
alternatives: regular, constructive context free, context free, constructive
context sensitive, context sensitive, decidable.

##  III Full Classification of Ising models

In this section we state and discuss our main result: a full classification of
the complexity of Ising models based on properties of their interaction graphs
(Theorem 1). First we define the relevant properties of interaction graphs,
more precisely of families of interaction graphs (Section III.1). Then we
state Theorem 1 (Section III.2), and provide a proof in Appendix A.

###  III.1 Properties of Ising models

Let us now introduce several properties of families of interaction graphs.
These properties can be divided into two classes. The first class captures the
complexity of the family of interaction graphs. The second class captures how
certain properties of the individual graphs contained therein scale with the
system size.

In order to quantify the complexity of the family of interaction graphs of an
Ising model $\mathcal{M}$ we define the edge language of $\mathcal{M}$, ${\sf
E}_{\mathcal{M}}$, as a formal language that encodes the entire family of
interaction graphs of $\mathcal{M}$. Consequently, classifying ${\sf
E}_{\mathcal{M}}$ in the Chomsky hierarchy measures the complexity of the
family of interaction graphs of $\mathcal{M}$.

######  Definition 5 (Edge language).

Let $\mathcal{M}$ be an Ising model. The _edge language_ of $\mathcal{M}$,
${\sf E}_{\mathcal{M}}$, is defined as

$\displaystyle{\sf E}_{\mathcal{M}}\coloneqq\\{0^{i-1}10^{j-i-1}10^{n-j}\mid
n\in N_{\mathcal{M}},\>(i,j)\in(E_{\mathcal{M}})_{n}\\}$ (10)

In words, ${\sf E}_{\mathcal{M}}$ directly encodes the interaction graphs of
$\mathcal{M}$, as $w=w_{1}\ldots w_{n}\in{\sf E}_{\mathcal{M}}$ if and only if
$n\in N_{\mathcal{M}}$ and $w$ is a row of the incidence matrix of the graph
defined by $(E_{\mathcal{M}})_{n}$. So each string $w$ in the edge language
specifies one edge of one interaction graph of $\mathcal{M}$, as well as the
system size of that interaction graph (encoded in the length of $w$).

$i$$\ldots$$\ldots$$1$Intermediate partInitial block $b$Final block $b$$n$
Figure 2: Interaction graph of a limited Ising model (Definition 6 (ii)).
Given any vertex $i$ not within the first or last $b$ vertices, all incident
edges are either connected to a vertex $j$ with $|j-i|\leq b$, i.e. to a
vertex within the same block (pale yellow block), or to one of the first or
last $b$ vertices (pale purple blocks).

The following proposition justifies the classification of the complexity of
Ising models based on their edge language, as it states that not only ${\sf
L}_{\mathcal{M}}$ but also ${\sf E}_{\mathcal{M}}$ characterise $\mathcal{M}$
uniquely.

######  Proposition 2 (Uniqueness of the edge language).

Let $\mathcal{M}$ and $\mathcal{M}^{\prime}$ be two Ising models. The
following are equivalent:

  1. (i)

$\mathcal{M}=\mathcal{M}^{\prime}$

  2. (ii)

${\sf L}_{\mathcal{M}}={\sf L}_{\mathcal{M}^{\prime}}$

  3. (iii)

${\sf E}_{\mathcal{M}}={\sf E}_{\mathcal{M}^{\prime}}$

###### Proof.

The two implications (i) $\implies$ (ii) and (iii) $\implies$ (i) are obvious.
We thus need to show (ii) $\implies$ (iii). If ${\sf L}_{\mathcal{M}}={\sf
L}_{\mathcal{M}^{\prime}}$ then clearly
$N_{\mathcal{M}}=N_{\mathcal{M}^{\prime}}$. Now take any $n\in
N_{\mathcal{M}}$. To show that
$(E_{\mathcal{M}})_{n}=(E_{\mathcal{M}^{\prime}})_{n}$ consider the function

$\displaystyle\begin{aligned}
C_{\mathcal{M}}(n,i,j)\coloneqq-\frac{1}{4}\bigl{[}&H_{\mathcal{M}}(0^{n})+H_{\mathcal{M}}(0^{i-1}10^{j-i-1}10^{n-j})\\\
&-H_{\mathcal{M}}(0^{i-1}10^{n-i})-H_{\mathcal{M}}(0^{j-1}10^{n-j})\bigr{]}\end{aligned}$
(11)

Using Eq. 5 one readily concludes that

$\displaystyle C_{\mathcal{M}}(n,i,j)=\begin{cases}1&\text{if}\
(i,j)\in(E_{\mathcal{M}})_{n}\\\ 0&\text{else}\end{cases}$ (12)

Thus

$(E_{\mathcal{M}})_{n}=\\{(i,j)\mid C_{\mathcal{M}}(n,i,j)=1\\}$ (13)

But as ${\sf L}_{\mathcal{M}}={\sf L}_{\mathcal{M}^{\prime}}$ is equivalent to
$H_{\mathcal{M}}=H_{\mathcal{M}^{\prime}}$, it is also the case that
$C_{\mathcal{M}}(n,i,j)=C_{\mathcal{M}^{\prime}}(n,i,j)$, and hence it follows
that $(E_{\mathcal{M}})_{n}=(E_{\mathcal{M}^{\prime}})_{n}$. ∎

Next we consider how certain properties of the interaction graphs of an Ising
model scale, i.e. how they change when changing the system size.

######  Definition 6 (Finite, limited and linear Ising model).

We call an Ising model $\mathcal{M}$

  1. (i)

_finite_ if $N_{\mathcal{M}}$ is finite.

  2. (ii)

_limited_ if there exists a natural number $b$ such that for all $n\in
N_{\mathcal{M}}$ and any $(i,j)\in(E_{\mathcal{M}})_{n}$, if $j-i>b$ then
either $i\leq b$ or $n-j\leq b$.

  3. (iii)

_linear_ if there exists a natural number $k$ such that for all $n\in
N_{\mathcal{M}}$, it is the case that $|(E_{\mathcal{M}})_{n}|\leq kn$.

For every Ising model the number of edges scales at most quadratically with
the system size (because the complete graph has $\binom{n}{2}$ edges). The
properties (i) finite and (iii) linear fine-grain the scaling of the number of
edges—in a truncated scaling (finite), and a linear scaling.

Property (ii) (limited) captures the scaling of the maximal interaction range.
Intuitively, an Ising model is limited if there is an upper bound on its
interaction range, i.e. a $b\in\mathbb{N}$ such that there is no edge $(i,j)$
where $i$ and $j$ are separated by at least $b$ other vertices (i.e.
$|j-i|>b$). With an exception: if $i$ is within the first $b$ vertices or $j$
is within the last $b$ vertices, then either of them can have long-range
edges, that is, they can be linked to other vertices which are further away
than $b$ (see Fig. 2).

Finally, the properties finite, limited, linear form a hierarchy. Clearly,
every finite Ising model is limited. Proving that every limited Ising model is
linear follows from a simple counting argument: If $\mathcal{M}$ is limited,
considering $n>2b$ vertices, the first and last $b$ vertices are included in
at most $2bn$ edges, and the remaining vertices are included in at most
$(n-2b)2b$ additional edges. In total we have

$|(E_{\mathcal{M}})_{n}|\leq 4bn-4b^{2}$ (14)

As per definition $b$ is independent of the system size, this shows that
$\mathcal{M}$ is linear.

Overall we have two hierarchies that capture properties of the family of
interaction graphs of an Ising model (Fig. 3). The first hierarchy classifies
Ising models based on the complexity of their family of interaction graphs;
specifically, it encodes the interaction graphs as a language ${\sf
E}_{\mathcal{M}}$ and classifies it in the Chomsky hierarchy (purple shapes of
Fig. 3). The second hierarchy classifies Ising models based on the scaling of
the number of edges, as well as the scaling of the maximal interaction range
with the system size (red shapes of Fig. 3).

Figure 3: Set diagram of the properties of Ising models. The purple shapes
correspond to properties that capture the complexity of the family of
interaction graphs, phrased in terms of the complexity of ${\sf
E}_{\mathcal{M}}$ in the Chomsky hierarchy. The red shapes correspond to
properties that capture the scaling of the connectivity and the number of
long-range interactions with the system size. The right hand side shows where
several examples are located in this diagram. Note that both the 2d Ising
model and the all-to-all Ising model are constructive context sensitive; yet,
the all-to-all model has regular ${\sf E}_{\mathcal{M}}$ and is not linear
(and thus fails to be constructive context free), whereas the 2d model has
context sensitive ${\sf E}_{\mathcal{M}}$ and is linear.

###  III.2 Main result

We are now ready to state the full classification of the complexity of Ising
models based on the properties introduced above.

######  Theorem 1 (Main result).

Let $\mathcal{M}$ be an Ising model.

  1. (i)

${\sf L}_{\mathcal{M}}$ is regular if and only if $\mathcal{M}$ is finite;

  2. (ii)

${\sf L}_{\mathcal{M}}$ is constructive context free if and only if
$\mathcal{M}$ is linear and ${\sf E}_{\mathcal{M}}$ is regular;

  3. (iii)

${\sf L}_{\mathcal{M}}$ is constructive context sensitive if and only if ${\sf
E}_{\mathcal{M}}$ is context sensitive;

  4. (iv)

${\sf L}_{\mathcal{M}}$ is decidable if and only if ${\sf E}_{\mathcal{M}}$ is
decidable.

While this theorem is proven in Appendix A, the statements can be intuitively
understood as follows.

#####  (i).

A finite Ising model only contains a finite number of system sizes, thus both
${\sf L}_{\mathcal{M}}$ and ${\sf E}_{\mathcal{M}}$ are finite languages,
which are trivially regular. Conversely, by the pumping lemma for regular
languages, it follows that infinite Ising models cannot have a regular
language.

#####  (ii).

The essence of the argument is the following. If $\mathcal{M}$ is linear and
${\sf E}_{\mathcal{M}}$ is regular, a constructive PDA for ${\sf
L}_{\mathcal{M}}$ can be built from a FSA for ${\sf E}_{\mathcal{M}}$.
Deciding ${\sf L}_{\mathcal{M}}$ amounts to deciding ${\sf E}_{\mathcal{M}}$
and adding the individual energy contributions. The PDA decides ${\sf
E}_{\mathcal{M}}$ by running the FSA in its states. As $\mathcal{M}$ is
linear, also adding the individual energy contributions is possible for a PDA.
Note that if $\mathcal{M}$ is not finite, adding the individual energy
contributions requires at least a PDA, i.e. cannot be achieved by a FSA.
Consequently, deciding the edges can at most require a FSA, since PDAs can use
FSAs but not PDAs as subroutines. Conversely, if $\mathcal{M}$ were not
linear, then already adding the individual energy contributions would require
a LBA (independently of the complexity of ${\sf E}_{\mathcal{M}}$), as it is
the case for the all-to-all Ising model (Fig. 3 and Section IV.6). Regularity
of ${\sf E}_{\mathcal{M}}$ can be proven by using the constructive PDA for
${\sf L}_{\mathcal{M}}$ to compute Eq. 11. So this PDA can be modified to
decide ${\sf E}_{\mathcal{M}}$. From the fact that the PDA is constructive it
then follows that the modified PDA only ever uses a single cell of stack
memory, so it effectively is a FSA.

#####  (iii).

In contrast to PDAs, LBAs can use LBAs as subroutines. This is the key
difference between (ii) and (iii). It follows that there is no separation in
the complexity of ${\sf E}_{\mathcal{M}}$ and ${\sf L}_{\mathcal{M}}$, i.e. in
contrast to (ii), they can be of the same complexity. The constructive LBA
that decides ${\sf L}_{\mathcal{M}}$ can be built by using a LBA for deciding
${\sf E}_{\mathcal{M}}$, to select the individual edges that contribute to the
energy, and another LBA to sum up these individual energy contributions.
Conversely, if ${\sf L}_{\mathcal{M}}$ is constructive context sensitive then
a LBA for ${\sf E}_{\mathcal{M}}$ can be built by modifying the LBA for ${\sf
L}_{\mathcal{M}}$ so that it computes Eq. 11.

#####  (iv).

Turing machines can also use Turing machines as subroutines. A Turing machine
that decides ${\sf L}_{\mathcal{M}}$ can be built in the same way as the LBA
in the previous case, and also the converse direction of (iv) works the same
way as that of (iii).

Let us highlight a corollary of the proof of Theorem 1, which will prove
useful in the examples of Section IV:

######  Corollary 1.

If $\mathcal{M}$ is not limited then ${\sf L}_{\mathcal{M}}$ is not
constructive context free.

###### Proof.

From Theorem 1 (ii) we know that if ${\sf L}_{\mathcal{M}}$ is constructive
context free then $\mathcal{M}$ is linear and ${\sf E}_{\mathcal{M}}$ is
regular. From Section A.2 (c), it follows that $\mathcal{M}$ is limited. The
corollary states the contrapositive. ∎

##  IV Examples: The complexity of Ising models

We now consider various Ising models and compute their complexity by applying
Theorem 1. Specifically, we consider the $1$d Ising model (Section IV.1) the
$1$d Ising model with periodic boundary conditions (Section IV.2), the Ising
model on ladder graphs (Section IV.3), the Ising model on layerwise complete
graphs (Section IV.4), the $2$d Ising model (Section IV.5), the all-to-all
Ising model (Section IV.6), and the Ising model on perfect binary trees
(Section IV.7). The results are summarised in Table 1.

We remark that we provide a grammar for the 1d and 2d Ising model in Appendix
C. These constitute independent proofs of their context freeness and context
sensitiveness, respectively. In fact, Appendix C provides a total of two
alternative proofs of the context freeness of the 1d Ising model.

Ising model $\mathcal{M}$ | ${\sf L}_{\mathcal{M}}$ | ${\sf E}_{\mathcal{M}}$ | Finite | Limited | Linear
---|---|---|---|---|---
$\mathcal{M}_{{\mathrm{1d}}}$ | Constructive context free | Regular | No | Yes | Yes
$\mathcal{M}_{{\mathrm{circ}}}$ | Constructive context free | Regular | No | Yes | Yes
$\mathcal{M}_{{\mathrm{ladder}}}$ | Constructive context free | Regular | No | Yes | Yes
$\mathcal{M}_{{\mathrm{layer}}}$ | Constructive context free | Regular | No | Yes | Yes
$\mathcal{M}_{{\mathrm{2d}}}$ | Constructive context sensitive | Context sensitive | No | No | Yes
$\mathcal{M}_{{\mathrm{all}}}$ | Constructive context sensitive | Regular | No | No | No
$\mathcal{M}_{{\mathrm{tree}}}$ | Constructive context sensitive | Context sensitive | No | No | Yes
Table 1: The Ising models (first column) considered in Section IV, their
complexity (second column) and the properties that determine their complexity
(remaining columns).

###  IV.1 1d Ising model

The most straightforward example of a constructive context free Ising model
uses $1$-dimensional chains as interaction graphs (Fig. 4(a)). We denote this
model as
$\mathcal{M}_{\mathrm{1d}}\coloneqq(N_{\mathrm{1d}},E_{\mathrm{1d}})$, defined
by

$\displaystyle\begin{aligned} N_{\mathrm{1d}}&\coloneqq\\{n\in\mathbb{N}\mid
n\geq 2\\}\\\ (E_{\mathrm{1d}})_{n}&\coloneqq\bigl{\\{}(i,i+1)\mid 1\leq i\leq
n-1\bigr{\\}}\end{aligned}$ (15)

We now use Theorem 1 (ii) to prove that the language of
$\mathcal{M}_{\mathrm{1d}}$ is constructive context free. To that end, let us
show that it is linear and its edge language is regular. Linearity is
immediate, as for any $n\in N_{\mathrm{1d}}$, $|(E_{\mathrm{1d}})_{n}|=n-1$.
Also regularity of ${\sf E}_{\mathrm{1d}}$ can be concluded straightforwardly,
as ${\sf E}_{\mathrm{1d}}=0^{*}110^{*}$ (where $0^{*}$ denotes the
concatenation of any number of 0s, including the empty one). Since
$\mathcal{M}_{\mathrm{1d}}$ is clearly not finite, by Theorem 1 (i) ${\sf
L}_{\mathrm{1d}}$ is not regular.

###  IV.2 1d Ising model with periodic boundary conditions

A second Ising model with constructive context free language is obtained by
taking circles as interaction graphs (Fig. 4(b)). We denote this model as
$\mathcal{M}_{\mathrm{circ}}\coloneqq(N_{\mathrm{circ}},E_{\mathrm{circ}})$,
where

$\displaystyle\begin{aligned} N_{\mathrm{circ}}&\coloneqq\\{n\in\mathbb{N}\mid
n\geq 3\\}\\\
(E_{\mathrm{circ}})_{n}&\coloneqq(E_{\mathrm{1d}})_{n}\cup\\{(1,n)\\}\end{aligned}$
(16)

Again, as $|(E_{\mathrm{circ}})_{n}|=n$, ${\mathcal{M}}_{\mathrm{circ}}$
clearly is linear. Besides,

${\sf E}_{\mathrm{circ}}={\sf E}_{\mathrm{1d}}\cup 100^{*}1$ (17)

is a union of regular languages, so it is regular. So according to Theorem 1
(ii) ${\sf L}_{\mathrm{circ}}$ is constructive context free. As
$\mathcal{M}_{\mathrm{circ}}$ is not finite, according to Theorem 1 (i) ${\sf
L}_{\mathrm{circ}}$ is not regular.

(a)

(b)

$k$$i$direction of growth (c)

$k$$i$direction of growth (d)

Figure 4: Interaction graphs of $\mathcal{M}_{\mathrm{1d}}$ (4(a)),
$\mathcal{M}_{\mathrm{circ}}$ (4(b)), $\mathcal{M}_{\mathrm{ladder}}$ (4(c)),
and $\mathcal{M}_{\mathrm{layer}}$ (4(d)). All these Ising models are
constructive context free. Intuitively, this is because their interaction
graphs all have one distinguished dimension along which an elementary building
block (that contains a constant number $k$ spins) is repeated ($i$ times) in a
periodic fashion. In (4(a)) and (4(b)) there is only one dimension, in (4(c))
and (4(d)) the distinguished dimension is indicated as“direction of growth”.
This property is made precise in Theorem 1 (ii): constructive context free
Ising models are uniquely characterised by ${\sf E}_{\mathcal{M}}$ being
regular and $\mathcal{M}$ being linear (or limited according to Section A.2
(c)).

###  IV.3 Ising model on a ladder graph

Another class of Ising models with constructive context free languages is
obtained by considering generalised ladder graphs as interaction graphs. For
each such model the interaction graphs are given by a family of d-dimensional
lattices, such that all lattices of the family have equal size along all but
one dimension, i.e. increasing the system size amounts to adding spins along
one distinguished dimension. It follows from Theorem 1 (ii) that all these
Ising models are constructive context free.

To illustrate this, we consider $2$-dimensional ladders with constant width
$k$ (Fig. 4(c)). The corresponding Ising model $\mathcal{M}_{\mathrm{ladder}}$
is defined by

$\displaystyle\begin{aligned} N_{\mathrm{ladder}}&\coloneqq\\{ik\mid i\geq
2\\}\\\
(E_{\mathrm{ladder}})_{ik}&\coloneqq(E_{\mathrm{ladder}})_{ik}^{\mathrm{ver}}\cup(E_{\mathrm{ladder}})_{ik}^{\mathrm{hor}}\\\
\end{aligned}$ (18)

where

$(E_{\mathrm{ladder}})_{ik}^{\mathrm{ver}}\coloneqq\\{(jk+l,jk+l+1)\mid\\\
0\leq j\leq i-1,\ 1\leq l\leq k-1\\}$ (19)

contains the vertical edges and

$(E_{\mathrm{ladder}})_{ik}^{\mathrm{hor}}\coloneqq\\{(jk+l,(j+1)k+l)\mid\\\
0\leq j\leq i-2,\ 1\leq l\leq k\\}$ (20)

contains the horizontal edges.

$\mathcal{M}_{\mathrm{ladder}}$ is linear, as
$|(E_{\mathrm{ladder}})_{n=ik}|=2ik-i-k<2n$. Moreover, its edge language ${\sf
E}_{\mathrm{ladder}}$ is regular, since it can be written as a finite union of
regular expressions From Theorem 1 (ii) it follows that ${\sf
L}_{\mathrm{ladder}}$ is constructive context free. In addition,
$\mathcal{M}_{\mathrm{ladder}}$ is not finite, so by Theorem 1(i) ${\sf
L}_{\mathrm{ladder}}$ is not regular.

###  IV.4 Ising model on layerwise complete graph

Also layerwise complete graphs, which are used in many neural network models,
define a class of Ising models with constructive context free language. To see
this, consider interaction graphs composed of $i$ layers of $k$ vertices, such
that there is no edge between vertices within the same layer, and any two
vertices from neighbouring layers are connected (Fig. 4(d)). The corresponding
Ising model $\mathcal{M}_{\mathrm{layer}}$ is defined as

$\displaystyle\begin{aligned} N_{\mathrm{layer}}&\coloneqq\\{ik\mid i\geq
2\\}\\\ (E_{\mathrm{layer}})_{ik}&\coloneqq\\{(jk+l,(j+1)k+r)\mid\\\
&\hphantom{\coloneqq}0\leq j\leq i-2,\ 1\leq l\leq k,\ 1\leq r\leq
k\\}\end{aligned}$ (21)

Since

$\displaystyle|(E_{\mathrm{layer}})_{n=ik}|=(i-1)k^{2}<kn$ (22)

$\mathcal{M}_{\mathrm{layer}}$ is linear. Regularity of ${\sf
E}_{\mathrm{layer}}$ can be seen from

$\displaystyle{\sf E}_{\mathrm{layer}}=\bigcup_{1\leq l\leq k,\ 1\leq r\leq
k}(0^{k})^{*}0^{l-1}10^{k-l}0^{r-1}10^{k-r}(0^{k})^{*}$ (23)

Using Theorem 1 (ii) it follows that ${\sf L}_{\mathrm{layer}}$ is
constructive context free. As $\mathcal{M}_{\mathrm{layer}}$ is not finite, by
Theorem 1 (i) we conclude that ${\sf L}_{\mathrm{layer}}$ is not regular.

###  IV.5 2d Ising model

Let us now show that the Ising model on $2$d square lattices has a
constructive context sensitive language. We denote the 2d Ising model as
$\mathcal{M}_{\mathrm{2d}}$, and define it as

$\displaystyle\begin{aligned} N_{\mathrm{2d}}&\coloneqq\\{n^{2}\mid n\geq
2\\}\\\
(E_{\mathrm{2d}})_{n^{2}}&\coloneqq(E_{\mathrm{2d}})_{n^{2}}^{\mathrm{hor}}\cup(E_{\mathrm{2d}})_{n^{2}}^{\mathrm{ver}}\end{aligned}$
(24)

The edge set of size $n^{2}$ is split in horizontal and vertical edges:

$\displaystyle\begin{aligned}
(E_{\mathrm{2d}})_{n^{2}}^{\mathrm{hor}}&\coloneqq\\{(i,i+1)\mid 1\leq i\leq
n^{2}-1,\ i\notin n\mathbb{N}\\}\\\
(E_{\mathrm{2d}})_{n^{2}}^{\mathrm{ver}}&\coloneqq\\{(i,i+n)\mid 1\leq i\leq
n^{2}-n\\}\end{aligned}$ (25)

Its family of interaction graphs can be seen in Fig. 4(c), with the difference
that for $\mathcal{M}_{\mathrm{2d}}$, when increasing the system size both
dimensions are scaled up simultaneously.

Using Theorem 1(iii) we now prove that ${\sf L}_{\mathrm{2d}}$ is constructive
context sensitive by showing that its edge language ${\sf E}_{\mathrm{2d}}$ is
context sensitive. To this end, we build a LBA that decides ${\sf
E}_{\mathrm{2d}}$. Asserting that the input $w_{1}\ldots w_{m}$ is well-
formed, i.e. of the form $0^{*}10^{*}10^{*}$, can be achieved by a FSA, which
can be simulated by the LBA. We can thus w.l.o.g. assume that the input is
well-formed. Next the LBA checks if $m=n^{2}$ for some natural number $n$.
This is done by iterating over natural numbers $n$, starting with $n=1$. In
each step of the iteration the LBA computes $n^{2}$ and checks if this matches
the length of the input $m$. If $n^{2}=m$ this subroutine terminates, if
$n^{2}<m$ the LBA moves on with the next natural number $n+1$, and if
$n^{2}>m$ the LBA rejects the input, as then $m$ is not a square number, i.e.
not in $N_{\mathrm{2d}}$. Explicitly, we use $(n+1)^{2}=n^{2}+2n+1$ to compute
the square numbers. The LBA uses an additional tape $T_{n}$ to store $n$ in
unary. Initially $n=1$ and the head of the LBA is placed over the first cell
of the input tape. The LBA enters a loop: The head moves $2n+1$ cells to the
right on the input tape. Note that this places the head over cell $(n+1)^{2}$.
The LBA now checks if the current cell is empty. If yes, then $m\notin
N_{\mathrm{2d}}$ and the LBA rejects the input. If no, the LBA checks if the
next cell is empty. If no, it increases $n$ by one in the additional tape, and
starts again. If yes, it accepts.

Now the LBA traverses the input until its head reaches the first $1$. While
doing so it uses another additional tape $T_{f}$ to count the position of that
first $1$ in the input string, $f$. Then the LBA counts the number of $0$s
between the first and the second $1$, $z$, and stores it in another additional
tape $T_{z}$. Finally, it accepts the input if either $z=n-1$, corresponding
to a vertical edge, or if $z=0$ and there exists no $k$ satisfying $f=kn$
(this can be done since $n$ is written on $T_{n}$), corresponding to a
horizontal edge.

Note that, as

$|(E_{\mathrm{2d}})_{n^{2}}|=2n(n-1)<2n^{2}$ (26)

$\mathcal{M}_{\mathrm{2d}}$ is linear. However, for any $n\in\mathbb{N}$,

$(n,2n)\in(E_{\mathrm{2d}})_{n^{2}}$ (27)

and hence $\mathcal{M}_{\mathrm{2d}}$ is not limited. So by Corollary 1 ${\sf
L}_{\mathrm{2d}}$ is not constructive context free.

We now show that ${\sf L}_{\mathrm{2d}}$ is not context free by using the
pumping lemma for context free languages [32]. Assume that ${\sf
L}_{\mathrm{2d}}$ was context free and let $p$ be the pumping length of ${\sf
L}_{\mathrm{2d}}$. Now consider

$\displaystyle l\coloneqq 0^{p^{2}}\bullet-^{2p(p-1)}$ (28)

Note that $l\in{\sf L}_{\mathrm{2d}}$, as a configuration of $p^{2}$ spins has
$2p(p-1)$ edges. When writing $l=uvwxy$, $v$ must be a non-empty string of $0$
symbols (let $|v|=:k$), while $x$ must be a non-empty string of $-$ symbols.
Otherwise pumping up $l$ would yield a mismatch between spin configuration and
energy. Since $|vwx|\leq p$ we also have that $k\leq p$, so $uv^{2}wx^{2}y$
yields a configuration with $p^{2}+k$ spins. But $p^{2}<p^{2}+k<(p+1)^{2}$, so
$p^{2}+k\notin N_{\mathrm{2d}}$ and thus $uv^{2}wx^{2}y\notin{\sf
L}_{\mathrm{2d}}$. Hence ${\sf L}_{\mathrm{2d}}$ is not context free.

###  IV.6 All-to-all Ising model

Also the all-to-all Ising model (Fig. 5(a)), i.e. the Ising model with
complete interaction graphs, has a constructive context sensitive language. We
denote this model as $\mathcal{M}_{\mathrm{all}}$, and define it by

$\displaystyle\begin{aligned} N_{\mathrm{all}}&\coloneqq\\{n\mid n\geq 2\\}\\\
(E_{\mathrm{all}})_{n}&\coloneqq\\{(i,j)\mid 1\leq i<j\leq n\\}\end{aligned}$
(29)

Its edge language ${\sf E}_{\mathrm{all}}$ is regular, since

${\sf E}_{\mathrm{all}}=0^{*}10^{*}10^{*}$ (30)

Thus ${\sf E}_{\mathrm{all}}$ is in particular context sensitive and by
Theorem 1 (iii), ${\sf L}_{\mathrm{all}}$ is constructive context sensitive.
Since

$\displaystyle|(E_{\mathrm{all}})_{n}|=\frac{1}{2}n(n-1)$ (31)

$\mathcal{M}_{\mathrm{all}}$ is not linear and, by Theorem 1 (ii), ${\sf
L}_{\mathrm{all}}$ is not constructive context free. In fact, by the pumping
lemma [32], ${\sf L}_{\mathrm{all}}$ can be proven to be not context free.
Assume ${\sf L}_{\mathrm{all}}$ was context free and denote its pumping length
by $p$. Now take

$\displaystyle l\coloneqq 0^{p}\bullet-^{\frac{p(p-1)}{2}}\in{\sf
L}_{\mathrm{all}}$ (32)

Writing $l=uvwxy$ as required by the pumping lemma, $v$ must be a non-empty
string of $0$s and $x$ must a non-empty string of $-$ symbols. Pumping up once
yields $k\coloneqq|v|$ new spin symbols and thus increases the overall energy
by

$e\coloneqq kp+\frac{1}{2}k(k-1)$ (33)

Hence it must be the case that $x=-^{e}$. Pumping up a second time
additionally adds

$k(p+k)+\frac{1}{2}k(k-1)=e+k^{2}$ (34)

more pair interactions but only $e$ more $-$ symbols. Thus there is a mismatch
between spin configuration and energy, and hence $uv^{3}wx^{3}y\notin{\sf
L}_{\mathrm{all}}$. Therefore ${\sf L}_{\mathrm{all}}$ is not context free.

(a)

$n$ (b)

Figure 5: Interaction graphs of $\mathcal{M}_{\mathrm{all}}$ (5(a)) and
$\mathcal{M}_{\mathrm{tree}}$ (5(b)). (5(b)) shows a perfect binary tree that
contains $2^{n}-1$ vertices, and thus consists of $n$ individual levels.
Increasing the system size in $\mathcal{M}_{\mathrm{tree}}$ adds entire levels
to the tree. These Ising models, as well as $\mathcal{M}_{\mathrm{2d}}$, have
constructive context sensitive language. $\mathcal{M}_{\mathrm{all}}$ has
regular edge language, but fails to be constructive context free as it is not
linear. In contrast, $\mathcal{M}_{\mathrm{tree}}$ and
$\mathcal{M}_{\mathrm{2d}}$ have context sensitive edge languages and are
linear. Theorem 1 (iii) states that the crucial property for ${\sf
L}_{\mathcal{M}}$ to be constructive context sensitive is that ${\sf
E}_{\mathcal{M}}$ be context sensitive.

###  IV.7 Ising model on perfect binary trees

Next we consider the Ising model $\mathcal{M}_{\mathrm{tree}}$ that uses
perfect binary trees as interaction graphs (Fig. 5(b)). This model is defined
by

$\displaystyle\begin{aligned} N_{\mathrm{tree}}&\coloneqq\\{2^{n}-1\mid n\geq
2\\}\\\
(E_{\mathrm{tree}})_{2^{n}-1}&\coloneqq(E_{\mathrm{tree}})_{2^{n}-1}^{\mathrm{left}}\cup(E_{\mathrm{tree}})_{2^{n}-1}^{\mathrm{right}}\end{aligned}$
(35)

where the edge set of size $2^{n}-1$ is split into those that connect the
parent vertex to its left child vertex and those that connect the parent
vertex to its right child vertex:

$\displaystyle\begin{aligned}
(E_{\mathrm{tree}})_{2^{n}-1}^{\mathrm{left}}&\coloneqq\\{(i,2i)\mid 1\leq
i\leq 2^{n-1}-1\\}\\\
(E_{\mathrm{tree}})_{2^{n}-1}^{\mathrm{right}}&\coloneqq\\{(i,2i+1)\mid 1\leq
i\leq 2^{n-1}-1\\}\end{aligned}$ (36)

In order to apply Theorem 1 (iii) we need to prove that ${\sf
E}_{\mathrm{tree}}$ is context sensitive. To this end, consider the language
that only encodes the system sizes $N_{\mathrm{tree}}$,

$\displaystyle{\sf N}_{\mathrm{tree}}\coloneqq\\{w_{1}\ldots w_{2^{n}-1}\mid
w_{i}\in\\{0,1\\},\ n\geq 2\\}$ (37)

We now show that this language is context sensitive by constructing a LBA that
decides it. Given an input string

$w_{1}\ldots w_{m}\in\\{0,1\\}^{*}$ (38)

the LBA checks if $m=2^{n}-1$ for some natural number $n$. It does so by using
an additional tape $T_{2^{n}}$ to store $2^{n}$ in unary. It starts with $n=1$
(so that $2^{n}=2$), and the head placed on the first cell of the input tape.
Then it enters the following loop. It moves the head on the input tape $2^{n}$
cells to the right (this is possible because $2^{n}$ is stored on the
additional tape). If the current cell is the last non-empty cell, it accepts.
If the cell is empty, it rejects. Else, it doubles the number of symbols on
the additional tape (so that it now contains $2^{n+1}$), moves its head back
to the beginning of the input tape, and continues with the first step of the
loop. This shows that ${\sf N}_{\mathrm{tree}}$ is context sensitive.

Next, note that the edge language is given by

$\displaystyle{\sf E}_{\mathrm{tree}}=\bigl{(}{\sf
E}_{\mathrm{tree}}^{\mathrm{left}}\cup{\sf
E}_{\mathrm{tree}}^{\mathrm{right}}\bigr{)}\cap{\sf N}_{\mathrm{tree}}$ (39)

where Both ${\sf E}_{\mathrm{tree}}^{\mathrm{left}}$ and ${\sf
E}_{\mathrm{tree}}^{\mathrm{right}}$ are context free, as can be seen by
constructing two PDAs $P_{\mathrm{left}}$ and $P_{\mathrm{right}}$ that accept
these two languages, respectively. (This can also directly be seen from the
fact that both languages are essentially of the form $\\{a^{n}b^{n}\mid n\geq
1\\}$.) $P_{\mathrm{left}}$ uses its stack to count the number of zeros in
front of the first $1$, and then it compares this number against the number of
zeros in front of the second $1$. If the two numbers coincide and the string
contains no further 1, it accepts, else it rejects. $P_{\mathrm{right}}$ does
the same, except for ignoring the first symbol after the first $1$ if it is
$0$ and rejecting if it is $1$.

Finally, from (39) and the closure properties of context sensitive languages
[32], it follows that ${\sf E}_{\mathrm{tree}}$ is context sensitive. Hence by
Theorem 1 (iii), ${\sf L}_{\mathrm{tree}}$ is constructive context sensitive.

$\mathcal{M}_{\mathrm{tree}}$ is not limited, as for any $n\geq 2$, the edge

$(2^{n-1}-1,2^{n}-2)\in(E_{\mathrm{tree}})_{2^{n}-1}^{\mathrm{left}}$ (40)

is long-range. Hence, by Corollary 1, ${\sf L}_{\mathrm{tree}}$ is not
constructive context free.

Moreover, ${\sf L}_{\mathrm{tree}}$ is not context free. This can be proven
with the pumping lemma of context free languages [32]. Assume ${\sf
L}_{\mathrm{tree}}$ was context free and let $p$ be its pumping length. Take
$n$ to be the smallest natural number that satisfies $2^{n}-1\geq p$. Consider

$\displaystyle l=0^{2^{n}-1}\bullet-^{2^{n}-2}\in{\sf L}_{\mathrm{tree}}$ (41)

Writing $l=uvwxy$, $v$ must be a non-empty string of $0$s and $x$ a non-empty
string of $-$ symbols. Then pumping up once yields a string that corresponds
to configuration of $2^{n}-1+k$ spins, where $k\coloneqq|v|$. As $k\leq p\leq
2^{n}-1$ it follows that $2^{n}-1+k<2^{n+1}-1$. Additionally using that $k>0$
shows that $2^{n}-1+k\notin N_{\mathrm{tree}}$ and hence
$uv^{2}wx^{2}y\notin{\sf L}_{\mathrm{tree}}$. Thus ${\sf L}_{\mathrm{tree}}$
is not context free.

##  V Conclusions and Outlook

In this work we have introduced a new complexity measure for Ising models and
fully classified Ising models according to it (Theorem 1). The complexity
measure consists of classifying the decision problem corresponding to the
function graph of the Hamiltonian of an Ising model in the Chomsky hierarchy.
In order to establish this classification, we have identified certain
properties of interaction graphs of Ising models. These properties can be
divided into two classes: those that capture the complexity of interaction
graphs (viz. the complexity of the edge language, Definition 5), versus those
that capture the scaling of interaction graphs (viz. finite, limited and
linear, Definition 6). In our main result we have unveiled which properties of
interaction graphs correspond to which complexity level of an Ising model in a
one-to-one manner. We have then used the classification of Theorem 1 to
compute the complexity of the 1d Ising model, the Ising model on ladder
graphs, on layerwise complete graphs, the 2d Ising model, the all-to-all Ising
model, and the Ising model on perfect binary trees (Table 1). We find a
different easy-to-hard threshold than for the computational complexity of the
ground state energy problem.

Among other things, this work raises the question of whether constructive
context free and constructive context sensitive differ from context free and
context sensitive. We conjecture this is not the case (Conjecture 1).
Constructive automata first compute the energy of the input spin configuration
and then compare it to the input energy. For this reason, working with
constructive automata ensures that we characterise the function problem of
computing the Hamiltonian (although for technical reasons we phrase it as the
decision problem of deciding its function graph). Therefore, Conjecture 1
ultimately concerns the question of how function problems differ from their
corresponding decision problems when considering PDAs or LBAs.

Furthermore, it would be interesting to compare our complexity measure to the
complexity of GSE rigorously, namely to investigate how the non-planarity
required for the NP-completeness of GSE relates to the properties of
Definition 6 and the complexity of the edge language (Definition 5).
Specifically, in our measure we observe that both the Ising model on ladder
graphs (irrespective of the dimension of the ladder) and the Ising model on
layerwise complete graphs are “easy”; yet, both of these families contain an
infinite number of non-planar graphs (The ladder graphs only if the dimension
is at least 3). On the other hand, both the 2d Ising models and the Ising
model on perfect binary trees are “hard” in our measure, while they both
contain only planar graphs. It is clear that the two measures capture
different properties; it is however not clear to us how the number of
crossings needs to scale with the system size for the GSE to be NP-complete
and thus how the two measures exactly differ.

A different way of comparing the two measures consists of investigating the
computational complexity of deciding ${\sf L}_{\mathcal{M}}$, that is, the
time resources a Turing machine needs to decide ${\sf L}_{\mathcal{M}}$—this
is done in [30] for general spin models. Conversely, one could classify the
language of GSE in the Chomsky hierarchy, and thereby unveil the grammar (i.e.
local structure) of the set of yes instances of the ground state energy
problem.

Encoding the Hamiltonian of an Ising model as a formal languages enforces a
total order of the spins, as mentioned in Section II. This could be avoided by
using graph languages and graph grammars instead of string languages and
string grammars. A graph language is a set of graphs, and graph grammars
generalise the production rule of string grammars to operate directly on
graphs [33]. While encoding Ising models as graph languages is more natural,
graph grammars lack the well-studied complexity hierarchy of string grammars.

From a broader perspective, this work —together with [30]— establishes a new
connection between spin models and theoretical computer science. Among other
reasons this connection is motivated by the recent discovery that certain spin
models such as the 2d Ising model with fields or the 3d Ising model are
universal [34]. This notion of universality has several similarities to that
of a universal Turing machine [35]. In [34] it is proven that a spin model is
universal if and only it is closed and its GSE is NP-complete. The complexity
measure for Ising models introduced here could help obtain another
characterisation of universal Ising models—for instance by translating closure
into properties of the interaction graphs. This would lead to a better
understanding of spin model universality and thereby also its relation to
Turing machine universality. We are currently working on a categorical
framework for universality which allows to compare notions of universality
[36].

This work is a first step in the characterisation of physical interactions in
terms of grammars, and an invitation to characterising interactions beyond the
Ising model, as well as other systems with a local structure, in the light of
grammars.

## Acknoweldgements

We thank Sebastian Stengele for many discussions, as well as everyone in the
group—Tomáš Gonda, Andreas Klingler and Mirte van der Eyden. We also thank
David Bänsch for joint work on graph grammars and graph languages. We thank
Thomas Müller, Hadil Karawani and Sahra Styger from the University of Konstanz
for many discussions about counterfactuals. We acknowledge funding from
Austrian Science Fund (FWF) via the FWF START Prize Y1261-N.

##  Appendix A Proof of Theorem 1

Here we prove Theorem 1 with one subsection for each statement.

###  A.1 Proof of Theorem 1(i)

If $N_{\mathcal{M}}$ is finite then so is ${\sf L}_{\mathcal{M}}$. Thus ${\sf
L}_{\mathcal{M}}$ is trivially regular [32].

In order to prove the “only if” direction using the pumping lemma for regular
languages [32], we prove that an Ising model with infinite $N_{\mathcal{M}}$
cannot be regular. To this end, assume such a ${\sf L}_{\mathcal{M}}$ was
regular and let $p$ be its pumping length. As $\mathcal{M}$ is infinite, there
exists a configuration of length $q>p$. Hence, the string

$0^{q}\bullet-^{e}\in{\sf L}_{\mathcal{M}}$ (42)

with $e\coloneqq|(E_{\mathcal{M}})_{q}|$ is contained in ${\sf
L}_{\mathcal{M}}$. Note that $e\leq\frac{1}{2}q(q-1)$, and hence, for any
$n>\frac{1}{2}q(q-1)+1$ we have $|E_{n}|>e$. Pumping up $k$ times yields a
string of the form $0^{q+kp}\bullet-^{e}$. Now chosing $k$ large enough such
that

$\displaystyle q+kp>\frac{1}{2}q(q-1)+1$ (43)

this string is not contained in ${\sf L}_{\mathcal{M}}$, since $|E_{q+kp}|>e$,
so $H_{\mathcal{M}}(0^{q+kp})\neq-e$. Thus an infinite Ising model cannot have
a regular language.

###  A.2 Proof of Theorem 1(ii)

In order to prove that

> ${\sf L}_{\mathcal{M}}$ is constructive context free $\iff\mathcal{M}$ is
> linear and ${\sf E}_{\mathcal{M}}$ is regular

we prove the following four statements:

  1. (a)

${\sf L}_{\mathcal{M}}$ is context free $\implies\mathcal{M}$ is linear

  2. (b)

${\sf L}_{\mathcal{M}}$ is constructive context free $\implies{\sf
E}_{\mathcal{M}}$ is regular

  3. (c)

$\mathcal{M}$ is linear and ${\sf E}_{\mathcal{M}}$ is regular
$\implies\mathcal{M}$ is limited

  4. (d)

$\mathcal{M}$ is limited and ${\sf E}_{\mathcal{M}}$ is regular $\implies{\sf
L}_{\mathcal{M}}$ is constructive context free

Combining (a) and (b) (and the fact that constructive context free is included
in context free) yields the forward direction of the statement, and combining
(c) and (d) yields the other direction.

Let us now prove each of the statements.

####  (a) If ${\sf L}_{\mathcal{M}}$ is context free, then $\mathcal{M}$ is
linear

As by assumption ${\sf L}_{\mathcal{M}}$ is context free, we claim that so is
the language containing the configuration of minimal energy for each system
size,

$({\sf L}_{\mathcal{M}})_{\mathrm{min}}\coloneqq\\{0^{n}-^{e_{n}}\mid n\in
N_{\mathcal{M}}\\}$ (44)

where $e_{n}\coloneqq|(E_{\mathcal{M}})_{n}|$. This holds since $({\sf
L}_{\mathcal{M}})_{\mathrm{min}}$ can be obtained from ${\sf L}_{\mathcal{M}}$
by first intersecting with the regular language $0^{*}\bullet-^{*}$ and then
applying the homomorphism that maps $\bullet$ to the empty string and acts as
identity on $\\{0,1,+,-\\}$. Since the class of context free languages is
closed both with respect to intersections with regular languages and
homomorphisms [32], this proves the claim that $({\sf
L}_{\mathcal{M}})_{\mathrm{min}}$ is context free.

As $({\sf L}_{\mathcal{M}})_{\mathrm{min}}$ is context free, its image under
the Parikh map

$P(0^{n}-^{e_{n}})=(n,e_{n})$ (45)

is a semilinear subset of $\mathbb{N}^{2}$, i.e. a union of finitely many
linear subsets $U_{1},\ldots,U_{r}\subset\mathbb{N}^{2}$ [32]. We now
construct a natural number $k$ such that for all $n\in N_{\mathcal{M}}$,
$e_{n}\leq kn$. Take any $(n,e_{n})$ from the image of $P$. Then there is an
$i\leq r$ such that $(n,e_{n})\in U_{i}$. As $U_{i}$ is linear, there exist
$u_{0}\in\mathbb{N}^{2},u_{1},\ldots,u_{d}\in\mathbb{N}^{2}\setminus\\{(0,0)\\}$,
such that any element in $U_{i}$ can be written as

$u_{0}+\lambda_{1}u_{1}+\ldots+\lambda_{d}u_{d}$ (46)

with $\lambda_{j}$ natural numbers. Thus, denoting $u_{j}=(v_{j},w_{j})$ we in
particular have

$\displaystyle\frac{e_{n}}{n}=\frac{w_{0}+\lambda_{1}w_{1}+\ldots+\lambda_{d}w_{d}}{v_{0}+\lambda_{1}v_{1}+\ldots+\lambda_{d}v_{d}}$
(47)

Now note that for any $u_{j}$ it holds that $v_{j}$ is strictly positive. For
assume that $v_{j}=0$. Then, by the linearity of $U_{i}$,

$0^{n+\lambda 0}\bullet-^{e_{n}+\lambda w_{j}}\in{\sf L}_{\mathcal{M}}$ (48)

so a single spin configuration, $0^{n}$, would have energies $-^{e_{n}}$ and
$-^{e_{n}+\lambda w_{j}}$. In other words, the relation between spin
configuration and energy would no longer be functional. Moreover, $v_{0}$
cannot be zero either, by Definition 2.

To finish the proof, take

$\displaystyle k_{i}\coloneqq\max\Bigl{\\{}\frac{w_{l}}{v_{j}}\mid l,j\leq
d\Bigr{\\}}$ (49)

Then it is easy to see that

$\displaystyle\frac{e_{n}}{n}\leq k_{i}$ (50)

Defining $k$ to be the maximum taken over $\\{k_{i}\mid i\leq r\\}$ shows that
for any $n\in N_{\mathcal{M}}$, $|(E_{\mathcal{M}})_{n}|\leq kn$ and hence
proves the claim.

####  (b) If ${\sf L}_{\mathcal{M}}$ is constructive context free, then ${\sf
E}_{\mathcal{M}}$ is regular

As ${\sf L}_{\mathcal{M}}$ is constructive context free there exists an
constructive PDA $P$ that accepts ${\sf L}_{\mathcal{M}}$. We prove the claim
by first using $P$ to construct a second PDA $P_{C}$ that decides ${\sf
E}_{\mathcal{M}}$, and showing that there exists a finite bound on the stack
memory of $P_{C}$. Since a finite stack can be simulated by a FSA (by
increasing the number of states), $P_{C}$ can be transformed into a FSA, which
proves the claim.

So let us consider a potential edge

$\langle i,j-1-1,n-j\rangle\coloneqq 0^{i-1}10^{j-i-1}10^{n-j}$ (51)

In order to decide if it is in ${\sf E}_{\mathcal{M}}$, $P_{C}$ computes
$C_{\mathcal{M}}(n,i,j)$ defined in Eq. 11, by simulating $P$’s computation on
the four input spin configurations

$0^{i-1}10^{j-i-1}10^{n-j},\quad 0^{i-1}10^{n-i},\quad 0^{j-1}10^{n-j},\quad
0^{n}$ (52)

and summing the four energies appropriately.

We now prove that, since $P$ is constructive, $P_{C}$ can be taken to be a
FSA. Let $(I_{m})_{m=1,\ldots,r_{n}}$ be the unique partition of
$(E_{\mathcal{M}})_{n}$ that witnesses that $P$ is constructive. At step $m$
of the main iteration of $P$ (cf. Definition 3 (i)(a)), $P$ computes the
energy contribution from interactions contained in $I_{m}$ and adds it to its
stack. Consequently, $P_{C}$ computes

$\displaystyle\begin{aligned}
C_{\mathcal{M}}(n,i,j)_{I_{m}}\coloneqq&-\frac{1}{4}\bigl{[}H_{\mathcal{M}}|_{I_{m}}(0^{n})\\\
&+H_{\mathcal{M}}|_{I_{m}}(0^{i-1}10^{j-i-1}10^{n-j})\\\
&-H_{\mathcal{M}}|_{I_{m}}(0^{i-1}10^{n-i})\\\
&-H_{\mathcal{M}}|_{I_{m}}(0^{j-1}10^{n-j})\bigr{]}\end{aligned}$ (53)

and adds the result to its stack. By Definition 3 the energy that each $I_{m}$
contributes is upper bounded by the number of states of $P$, and so in
particular it is finite. Thus, summing up the four terms of Eq. 53 can be done
in the states of $P_{C}$, and we can assume that $P_{C}$ only uses its stack
to accumulate

$\sum_{m=1}^{r_{n}}C_{\mathcal{M}}(n,i,j)_{I_{m}}$ (54)

By construction $C_{\mathcal{M}}(n,i,j)_{I_{m}}$ is $+1$ if $(i,j)\in I_{m}$
and $0$ else. Thus, a finite stack suffices to compute (54), and hence this
can be done in the states of $P_{C}$. This makes $P_{C}$ a FSA.

Finally, if $n\notin N_{\mathcal{M}}$, $P_{C}$ rejects by construction, as so
does $P$. If $n\in N_{\mathcal{M}}$, $P_{C}$ accepts the input if and only if
$C_{\mathcal{M}}(n,i,j)=1$. So $P_{C}$ correctly decides ${\sf
E}_{\mathcal{M}}$, which proves that ${\sf E}_{\mathcal{M}}$ is regular.

####  (c) If $\mathcal{M}$ is linear and ${\sf E}_{\mathcal{M}}$ is regular,
then $\mathcal{M}$ is limited

We prove that if ${\sf E}_{\mathcal{M}}$ is regular and $\mathcal{M}$ is not
limited, then $\mathcal{M}$ cannot be linear. To this end, for any natural
number $k$, assuming ${\sf E}_{\mathcal{M}}$ is regular, we construct a
natural number $l$ such that $\mathcal{M}$ contains more than $kl$ edges of
length $l$, i.e. it is not linear.

By assumption ${\sf E}_{\mathcal{M}}$ is regular. Let $F$ be a FSA that
accepts it and denote the number of states of $F$ by $b$. Consider an edge
$\langle p,q,r\rangle\in{\sf E}_{\mathcal{M}}$ with $p>b$. When accepting
$\langle p,q,r\rangle$ there has to be at least one state that $F$ enters
twice before reaching the first $1$ with its head. Thus, $F$ contains a loop
in its transition rules. Denote the number of transitions that are contained
in this loop by $w_{p}$. Then, for any natural number $n_{p}$,

$\langle p+n_{p}w_{p},q,r\rangle\in{\sf E}_{\mathcal{M}}$ (55)

By a similar reasoning, for an edge $\langle p,q,r\rangle$ with $q>b$, $F$
must enter a loop after reading the first $1$ and before reading the second
$1$. Denote the length of the corresponding loop by $w_{q}$. Then for any
natural number $n_{q}$,

$\langle p,q+n_{q}w_{q},r\rangle\in{\sf E}_{\mathcal{M}}$ (56)

Similarly, for an edge $\langle p,q,r\rangle$ with $r>b$, $F$ enters a loop
after reading the second $1$. Denote the number of transitions in this loop as
$w_{r}$. Then for any natural number $n_{r}$,

$\langle p,q,r+n_{r}w_{r}\rangle\in{\sf E}_{\mathcal{M}}$ (57)

Now, since $\mathcal{M}$ is not limited, there exists an edge $\langle
p,q,r\rangle\in{\sf E}_{\mathcal{M}}$ with $p,q,r>b$. By the above reasoning,
there exist natural numbers $w_{p},w_{q},w_{r}$ such that for any
$n_{p},n_{q},n_{r}$

$\displaystyle\langle p+n_{p}w_{p},q+n_{q}w_{q},r+n_{r}w_{r}\rangle\in{\sf
E}_{\mathcal{M}}$ (58)

Take any natural number $m$ and define

$\displaystyle l_{m}\coloneqq p+q+r+2+mw_{p}w_{q}w_{r}$ (59)

We will now show that for any $k$, choosing $m$ appropriately, there are more
than $kl_{m}$ words of length $l_{m}$ and hence $\mathcal{M}$ is not linear.
To this end, take any $m_{p},m_{q},m_{r}$ that satisfy $m_{p}+m_{q}+m_{r}=m$.
Then, the edge

$\displaystyle\langle
p+m_{p}w_{p}w_{q}w_{r},q+m_{q}w_{p}w_{q}w_{r},r+m_{r}w_{p}w_{q}w_{r}\rangle$
(60)

is contained in ${\sf E}_{\mathcal{M}}$ and has length $l_{m}$. Thus the
number of edges of length $l_{m}$ is at least as big as the number of triples
$(m_{p},m_{q},m_{r})$ that sum to $m$,

$\displaystyle\begin{aligned} &\bigl{|}\\{(m_{p},m_{q},m_{r})\mid
m_{p}+m_{q}+m_{r}=m\\}\bigr{|}\\\
&=\sum_{m_{p}=0}^{m}\sum_{m_{q}=0}^{m-m_{p}}1=\frac{1}{2}m^{2}+\frac{3}{2}m+1\end{aligned}$
(61)

So, while $l_{m}$ grows linearly with $m$, the number of words of length
$l_{m}$ grows at least quadratically with $m$. Thus, for any $k\in\mathbb{N}$,
choosing $m$ appropriately yields more than $kl_{m}$ words of length $l_{m}$.
Hence $\mathcal{M}$ is not linear.

####  (d) If $\mathcal{M}$ is limited and ${\sf E}_{\mathcal{M}}$ is regular,
then ${\sf L}_{\mathcal{M}}$ is constructive context free

We prove the claim by building a constructive PDA that accepts ${\sf
L}_{\mathcal{M}}$. Let $F$ be a FSA that accepts ${\sf E}_{\mathcal{M}}$ and
let $b$ denote the number of states of $F$. As a first step, we use $F$ to
decompose ${\sf E}_{\mathcal{M}}$ into $8$ disjoint subsets, represented by
eight finite sets (68). In the second step, for each of these sets, we build a
PDA that computes the energy contribution corresponding to the edges in that
set. Putting together these contributions shows that ${\sf L}_{\mathcal{M}}$
can be recognised by a constructive PDA.

##### Decomposing ${\sf E}_{\mathcal{M}}$.

Take any edge $\langle p,q,r\rangle\in{\sf E}_{\mathcal{M}}$. If $F$ enters a
loop when processing $0^{p}$, we can w.l.o.g. assume that this loop is
irreducible in the sense that it contains each state at most once; otherwise
we decompose it until it is irreducible. Denote the number of states of this
loop by $w_{p}$. Then we can write $p=v_{p}+n_{p}w_{p}$ for some natural
number $n_{p}$. Note that

$\langle v_{p}+nw_{p},q,r\rangle\in{\sf E}_{\mathcal{M}}$ (62)

for any natural number $n$. We call $(w_{p},v_{p})$ the $1$-loop-parameters of
$\langle p,q,r\rangle$ ($1$\- to indicate that the loop occurs in $p$ and not
in $q$ or $r$) and say that $\langle p,q,r\rangle$ is $1$-periodic if there
exist $1$-loop-parameters $(w_{p},v_{p})$ and a natural number $n_{p}$ such
that $p=v_{p}+n_{p}w_{p}$. Next, we define the set of $1$-loop-parameters that
correspond to valid edges in ${\sf E}_{\mathcal{M}}$, requiring that all such
$1$-loop-parameters describe irreducible loops,

$P_{\mathrm{l}}\coloneqq\\{(w_{p},v_{p})\mid(w_{p},v_{p})\text{
{\hbox{1}}-loop-parameters of {\hbox{{\sf E}_{\mathcal{M}}}}}\\}$ (63)

Note that $v_{p},w_{p}\leq b$ as otherwise the loop would not be irreducible.
Thus, $P_{\mathrm{l}}$ is a finite set.

If $\langle p,q,r\rangle$ is not $1$-periodic, we say it is $1$-finite. We
define

$P_{\mathrm{f}}\coloneqq\\{p\mid\exists q,r\ \textrm{s.t.}\\\ \ \langle
p,q,r\rangle\in{\sf E}_{\mathcal{M}}\text{ and }\ \nexists v_{p}:\
(p,v_{p})\in P_{\mathrm{l}}\\}$ (66)

Note that any $p\in P_{\mathrm{f}}$ must satisfy $p\leq b$, so
$P_{\mathrm{f}}$ is also a finite set. Note also that, by construction, any
edge $\langle p,q,r\rangle\in{\sf E}_{\mathcal{M}}$ is either $1$-finite or
$1$-periodic, i.e. either $p\in P_{\mathrm{f}}$ or $p=w_{p}n+v_{p}$ for a
unique $\langle w_{p},v_{p}\rangle\in P_{\mathrm{l}}$ and $n\in\mathbb{N}$.

In exactly the same way we define $2$-periodicity, $2$-finiteness,
$3$-periodicity and $3$-finiteness of an edge $\langle p,q,r\rangle$, where
periodicity or finiteness refers to $q$ and $r$, respectively, as well as
$2$-loop-parameters and $3$-loop-parameters and the corresponding sets

$\displaystyle\begin{aligned}
Q_{\mathrm{l}}\coloneqq&\\{(w_{q},v_{q})\mid(w_{q},v_{q})\text{ $2$-loop-
paramaters of ${\sf E}_{\mathcal{M}}$}\\}\\\
Q_{\mathrm{f}}\coloneqq&\\{q\mid\exists p,r\ \textrm{s.t.}\\\ &\langle
p,q,r\rangle\in E_{\mathcal{M}}\ \text{and}\ \nexists v_{q}:\ (q,v_{q})\in
Q_{\mathrm{l}}\\}\\\
R_{\mathrm{l}}\coloneqq&\\{(w_{r},v_{r})\mid(w_{r},v_{r})\text{ $3$-loop-
paramaters of ${\sf E}_{\mathcal{M}}$}\\}\\\
R_{\mathrm{f}}\coloneqq&\\{r\mid\exists p,q\ \textrm{s.t.}\\\ &\langle
p,q,r\rangle\in E_{\mathcal{M}}\ \text{and}\ \nexists v_{r}:\ (r,v_{r})\in
R_{\mathrm{l}}\\}\end{aligned}$ (67)

In addition, we define sets of combinations of $p,q,r$ that lead to valid
edges in ${\sf E}_{\mathcal{M}}$,

$\displaystyle\begin{aligned} E_{\mathrm{fff}}\coloneqq&\\{(p,q,r)\in
P_{\mathrm{f}}\times Q_{\mathrm{f}}\times R_{\mathrm{f}}\mid\langle
p,q,r\rangle\in{\sf E}_{\mathcal{M}}\\}\\\
E_{\mathrm{lff}}\coloneqq&\\{((w_{p},v_{p}),q,r)\in P_{\mathrm{l}}\times
Q_{\mathrm{f}}\times R_{\mathrm{f}}\mid\langle v_{p},q,r\rangle\in{\sf
E}_{\mathcal{M}}\\}\\\ E_{\mathrm{flf}}\coloneqq&\\{(p,(w_{q},v_{q}),r)\in
P_{\mathrm{f}}\times Q_{\mathrm{l}}\times R_{\mathrm{f}}\mid\langle
p,v_{q},r\rangle\in{\sf E}_{\mathcal{M}}\\}\\\
E_{\mathrm{ffl}}\coloneqq&\\{(p,q,(w_{r},v_{r}))\in P_{\mathrm{f}}\times
Q_{\mathrm{f}}\times R_{\mathrm{l}}\mid\langle p,q,v_{r}\rangle\in{\sf
E}_{\mathcal{M}}\\}\\\
E_{\mathrm{llf}}\coloneqq&\\{((w_{p},v_{p}),(w_{q},v_{q}),r)\in
P_{\mathrm{l}}\times Q_{\mathrm{l}}\times R_{\mathrm{f}}\mid\\\ &\langle
v_{p},v_{q},r\rangle\in{\sf E}_{\mathcal{M}}\\}\\\
E_{\mathrm{lfl}}\coloneqq&\\{((w_{p},v_{p}),q,(w_{r},v_{r}))\in
P_{\mathrm{l}}\times Q_{\mathrm{f}}\times R_{\mathrm{l}}\mid\\\ &\langle
v_{p},q,v_{r}\rangle\in{\sf E}_{\mathcal{M}}\\}\\\
E_{\mathrm{fll}}\coloneqq&\\{(p,(w_{q},v_{q}),(w_{r},v_{r}))\in
P_{\mathrm{f}}\times Q_{\mathrm{l}}\times R_{\mathrm{l}}\mid\\\ &\langle
p,v_{q},v_{r}\rangle\in{\sf E}_{\mathcal{M}}\\}\\\
E_{\mathrm{lll}}\coloneqq&\\{((w_{p},v_{p}),(w_{q},v_{q}),(w_{r},v_{r}))\in
P_{\mathrm{l}}\times Q_{\mathrm{l}}\times R_{\mathrm{l}}\mid\\\ &\langle
v_{p},v_{q},v_{r}\rangle\in{\sf E}_{\mathcal{M}}\\}\end{aligned}$ (68)

Note that each of these sets is finite, and that they are all disjoint. Note
also that if $\mathcal{M}$ is limited then $E_{\mathrm{lll}}$ is empty. So
this decomposes ${\sf E}_{\mathcal{M}}$ into $7$ disjoint nonempty subsets.
Explicitly, define their union

$\displaystyle\mathcal{E}\coloneqq E_{\mathrm{fff}}\cup E_{\mathrm{lff}}\cup
E_{\mathrm{flf}}\cup E_{\mathrm{ffl}}\cup E_{\mathrm{llf}}\cup
E_{\mathrm{lfl}}\cup E_{\mathrm{fll}}$ (69)

For each such set, any of its elements describes a subset $I_{e}\subseteq{\sf
E}_{\mathcal{M}}$ of edges of $\mathcal{M}$. For $(p,q,r)\in E_{\mathrm{fff}}$
this is a singleton $I_{(p,q,r)}=\\{\langle p,q,r\rangle\\}$, but for elements
of any set other than $E_{\mathrm{fff}}$, $I_{e}$ is infinite. For example,
for $((w_{p},v_{p}),(w_{q},v_{q}),r)\in E_{\mathrm{llf}}$ we have

$I_{((w_{p},v_{p}),(w_{q},v_{q}),r)}=\\{\langle
v_{p}+nw_{p},v_{q}+mw_{q},r\rangle\mid n,m\in\mathbb{N}\\}$ (70)

In other words, an edge $\langle p^{\prime},q^{\prime},r^{\prime}\rangle$ is
contained in $I_{((w_{p},v_{p}),(w_{q},v_{q}),r)}$ if and only of

$\displaystyle\begin{aligned} p^{\prime}&=v_{p}\mod w_{p}\\\
q^{\prime}&=v_{q}\mod w_{q}\\\ r^{\prime}&=r\end{aligned}$ (71)

By construction, any edge $\langle
p^{\prime},q^{\prime},r^{\prime}\rangle\in{\sf E}_{\mathcal{M}}$ is described
by a unique $e\in\mathcal{E}$. Thus we obtain a partition of ${\sf
E}_{\mathcal{M}}$ into a finite number of disjoint subsets:

$\displaystyle{\sf E}_{\mathcal{M}}=\bigcup_{e\in\mathcal{E}}I_{e}$ (72)

##### Building the PDAs.

In order to build a constructive PDA $P$ that accepts ${\sf L}_{\mathcal{M}}$,
we build a constructive PDA $P_{e}$ for every $e\in\mathcal{E}$. The idea is
the following. First, since ${\sf E}_{\mathcal{M}}$ is regular, well-
formedness of the input can easily be checked by a FSA, and thus also be
simulated in the states of $P_{e}$. So henceforth we shall assume that all
inputs are well-formed, i.e. of the form

$s_{1}\ldots s_{n}\bullet\sigma^{k}$ (73)

Given a well-formed input, $P_{e}$ accumulates the energy contributions that
correspond to edges in $I_{e}$ on its stack, that is, $P_{e}$ computes
$H_{\mathcal{M}}|_{I_{e}}(s_{1}\ldots s_{n})$. The required constructive PDA
$P$ for ${\sf L}_{\mathcal{M}}$ is obtained by running all $P_{e}$s in
parallel while providing access to the same stack, so that $P$ accumulates

$\sum_{e\in\mathcal{E}}H_{\mathcal{M}}|_{I_{e}}(s_{1}\ldots s_{n})$ (74)

on its stack. Since $\mathcal{E}$ is finite, there is a finite number of PDAs
$P_{e}$, and hence their parallel simulation can be performed by a PDA, $P$.
Moreover, since $\bigcup_{e\in\mathcal{E}}I_{e}$ is a partition of ${\sf
E}_{\mathcal{M}}$ into disjoint subsets, equation (74) equals
$H_{\mathcal{M}}(s_{1}\ldots s_{n})$. Finally $P$ compares its stack content
to the input energy $\sigma^{k}$ and accepts if and only if the two values are
equal. All PDAs $P_{e}$ are built such that $P$ is constructive.

Let us construct the PDAs $P_{e}$ for any $e\in\mathcal{E}$. We will start by
considering $e\in E_{\mathrm{fff}}$, and then continue with the following
cases of (68).

###### 1\. The PDA for $E_{\mathrm{fff}}$.

We consider $(p,q,r)\in E_{\mathrm{fff}}$ and construct the PDA $P_{(p,q,r)}$.
We have that $I_{(p,q,r)}=\\{\langle p,q,r\rangle\\}$ contains an interaction
between $s_{i}$ and $s_{j}$ if and only if

$\displaystyle\begin{aligned} i&=p+1\\\ j&=p+q+2\\\ n&=p+q+r+2\end{aligned}$
(75)

The PDA starts by reading the first $p+q+r+2$ symbols of its input and storing
them in its state. Then it checks if the next input symbol is $\bullet$. If
yes, then $n=p+q+r+2$ and it adds $h(s_{i},s_{j})$ to its stack. The relevant
spin values are stored in its states and the value $h(s_{i},s_{j})$ can be
hard-wired into the transition rules. If it reads $\bullet$ during any other
step of the computation, it rejects.

###### 2\. The PDA for $E_{\mathrm{lff}}$.

We now consider $((w_{p},v_{p}),q,r)\in E_{\mathrm{lff}}$ and construct the
PDA $P_{((w_{p},v_{p}),q,r)}$. $s_{i}$ and $s_{j}$ interact if and only if

$\displaystyle\begin{aligned} i&=v_{p}+1\mod w_{p}\\\ j&=i+q+1\\\
n&=j+r\end{aligned}$ (76)

If, for a given $n$, Eq. 76 has a solution, this solution is unique. Hence the
PDA needs to compute at most one interaction, and works as follows. The PDA
reads the first $r+q+2$ spin symbols $s_{1}\ldots s_{r+q+2}$ and stores them
in its states. Then it iteratively reads the next input symbol, stores it in
its states and removes the left-most of the currently stored input symbols—we
call this the main iteration. Note that at any given time, the stored spins
are $s_{i}\ldots s_{i+r+q+1}$. To test if $i=v_{p}+1\mod w_{p}$, it uses a
counter $c_{w_{p}}$ initialised at 1, which is updated as

$c_{w_{p}}\mapsto c_{w_{p}}+1\mod w_{p}$ (77)

at each step of the main iteration. Thus, if $i$ solves the first equation of
Eq. 76, $c_{w_{p}}=v_{p}+1$. If this is the case, the PDA has stored
$s_{i}\ldots s_{n}$, as by Eq. 76 $n=i+r+q+1$. It then checks if the next
input symbol is $\bullet$. If yes, it adds $h(s_{i},s_{j})$ to its stack
where, according to Eq. 76, $j=n-r$. This is possible since at this step of
the computation both $s_{i}$ and $s_{j}$ are stored in the states of the PDA.
If no, it continues with the main iteration. If it reaches $\bullet$ at any
other step of the computation, it rejects.

###### 3\. The PDA for $E_{\mathrm{flf}}$.

We now consider $(p,(w_{q},v_{q}),r))\in E_{\mathrm{flf}}$ and construct the
PDA $P_{(p,(w_{q},v_{q}),r))}$. $s_{i}$ and $s_{j}$ interact if and only if

$\displaystyle\begin{aligned} i&=p+1\\\ j&=i+v_{q}+1\mod w_{q}\\\
n&=j+r\end{aligned}$ (78)

The PDA starts by moving its head $p$ symbols to the right. Next it stores
$s_{p+1}$ in its states, since according to Eq. 78, $i=p+1$. It now enters the
main iteration: It stores the next $r$ spin symbols in its states. Its head is
now placed over $s_{p+r+2}$ and it currently stores $s_{i}\ldots s_{i+r}$. At
each step of the main iteration, it reads the next spin symbol, stores it in
its states and deletes the left-most spin symbol from its states. In addition
to that, it uses a counter $c_{w_{q}}$ that is initialised at $c_{w_{q}}=i\mod
w_{q}$. At each step of the main iteration the counter is updated as

$c_{w_{q}}\mapsto c_{w_{q}}+1\mod w_{q}$ (79)

If during this main iteration the leftmost stored spin symbol is $s_{j}$ then
the counter is $c_{w_{q}}=j\mod w_{q}$. Once it reaches $\bullet$ the leftmost
stored spin symbol $s_{j}$ satisfies $j=n-r$, i.e. solves the last equation in
Eq. 78. If additionally $c_{w_{q}}=i+v_{q}+1$, it also solves the second
equation in Eq. 78. The PDA then adds $h(s_{i},s_{n-r})$ to the stack. This is
possible since both $s_{i}$ and $s_{n-r}$ are then stored in the states. If
$c_{w_{q}}\neq j\mod w_{q}$, the input is rejected. If during any other step
of the computation the PDA reaches $\bullet$, the input is rejected.

###### 4\. The PDA for $E_{\mathrm{ffl}}$.

For $(p,q,(w_{r},v_{r}))\in E_{\mathrm{ffl}}$ we construct the PDA
$P_{(p,q,(w_{r},v_{r}))}$. $s_{i}$ and $s_{j}$ interact if and only if

$\displaystyle\begin{aligned} i&=p+1\\\ j&=i+q+1\\\ n&=j+v_{r}\mod
w_{r}\end{aligned}$ (80)

Now both spin states $s_{i},s_{j}$ can be read from the beginning of the spin
configuration. The PDA starts by storing the first $p+q+2$ spins from its
input in its states. Next it counts if $n=p+q+2+v_{r}\mod w_{r}$, again using
$w_{r}$ of its states as a counter modulo $w_{r}$. If yes, it adds
$h(s_{i},s_{j})$ to its stack; if no, it rejects.

###### 5\. The PDA for $E_{\mathrm{llf}}$.

We now consider $((w_{p},v_{p}),(w_{q},v_{q}),r)\in E_{\mathrm{llf}}$ and
construct the PDA $P_{((w_{p},v_{p}),(w_{q},v_{q}),r)}$. $s_{i}$ and $s_{j}$
interact if and only if

$\displaystyle\begin{aligned} i&=v_{p}+1\mod w_{p}\\\ j&=i+v_{q}+1\mod
w_{q}\\\ n&=j+r\end{aligned}$ (81)

Let $l\coloneqq\mathrm{lcm}(w_{p},w_{q})$,
$g\coloneqq\mathrm{gcd}(w_{p},w_{q})$. By the Chinese remainder theorem, if

$v_{p}+1=j-v_{q}-1\mod g$ (82)

Eq. 81 has a unique solution modulo $l$, else it has no solution. In
particular, if there exists a solution, then there is a unique one with $i\leq
l$. All further solutions $i^{\prime}$ are given as $i^{\prime}=i+ml$ where
$m$ satisfies

$i+ml\leq n-r-v_{q}-1$ (83)

The PDA first non-deterministically guesses both $s_{n-r}$ and the unique
$i\leq l$ solving Eq. 81. Then it iterates over the input and adds all
$h(s_{i^{\prime}},s_{j})$ for $i^{\prime}=i+ml$ satisfying (83) to its stack.

More precisely, it starts by non-deterministically guessing the state of spin
$s_{n-r}$. Next it reads the first $r+1$ symbols of the input and stores them
in its states. Now the main iteration starts. At each step of the main
iteration, the PDA reads the next symbol from the input, stores this symbol in
its states and deletes the left-most of its stored symbols. Additionally, it
uses two counters, $c_{w_{p}}$ and $c_{l}$. Both counters are initialised as
one. After each step of the iteration, the counters are updated as

$\displaystyle\begin{aligned} c_{w_{p}}&\mapsto c_{w_{p}}+1\mod w_{p}\\\
c_{l}&\mapsto c_{l}+1\mod l\end{aligned}$ (84)

Note that both these counters correspond to the position of the left-most
stored spin symbol, i.e. when $s_{i}\ldots s_{i+r}$ are stored then
$c_{w_{p}}=i\mod w_{p}$ and $c_{l}=i\mod l$. The main iteration stops once
$c_{l}=0$.

If, during the main iteration, $c_{w_{p}}=v_{p}+1$, the PDA non-
deterministically branches into the two options of the current position $i$
either solving or not solving Eq. 81. If it guesses that $i$ does not solve
Eq. 81. it continues the main iteration with $i+1$. If it guesses that $i$
solves Eq. 81 it adds $h(s_{i},s_{n-r})$ to the stack. Next it sets $c_{l}$ to
zero, and sets an additional counter $c_{w_{q}}$ modulo $w_{q}$ to zero, too.
It continues iterating over the remaining input, still updating $c_{l}$ as
before. Additionally, it now updates $c_{w_{q}}\mapsto c_{w_{q}}+1\mod w_{q}$
instead of $c_{w_{p}}$. Note that now both counters, $c_{l}$ and $c_{w_{q}}$
correspond to the position of the left-most stored spin symbol relative to
$s_{i}$, i.e. when $s_{i^{\prime}}\ldots s_{i^{\prime}+r}$ is stored, the
counters correspond to $c_{l}=i^{\prime}-i\mod l$, and similarly for
$c_{w_{q}}$. If, at any time $c_{l}=0$, it adds the corresponding energy
$h(s_{i^{\prime}},s_{n-r})$ to the stack, as in that case $i^{\prime}=i+ml$
and as $i$ solves Eq. 81 so does $i^{\prime}$. Given that the non-
deterministic guess of $i$ solving Eq. 81 was right, the PDA hence accumulates
the energy contributions of all solutions of Eq. 81 on its stack.

Finally, once the head reaches $\bullet$, it has $s_{n-r}\ldots s_{n}$ stored
in its states and the second counter yields $c_{w_{q}}=j-i\mod w_{q}$. This
allows the PDA to verify its two non-deterministic guesses. If
$c_{w_{q}}=v_{q}+1$ and the initial guess of $s_{n-r}$ was correct, it
accepts; else it rejects.

###### 6\. The PDA for $E_{\mathrm{lfl}}$.

We now consider $((w_{p},v_{p}),q,((w_{r},v_{r}))\in E_{\mathrm{lfl}}$ and
construct the PDA $P_{((w_{p},v_{p}),q,((w_{r},v_{r}))}$. $s_{i}$ and $s_{j}$
interact if and only if

$\displaystyle\begin{aligned} i&=v_{p}+1\mod w_{p}\\\ j&=i+q+1\\\
n&=j+v_{r}\mod w_{r}\end{aligned}$ (85)

Using again the Chinese remainder Theorem with
$l\coloneqq\mathrm{lcm}(w_{p},w_{r})$, Eq. 85 either has a unique solution
modulo $l$, or there exists no solution. The PDA can now be built similarly to
the previous case, the only difference is that, as $j=i+q+1$, there is no need
to apply non-determinism to obtain $s_{j}$.

More precisely, the PDA first traverses the input string, while keeping track
of the current head position, using two modulo counters, $c_{w_{p}}$ and
$c_{l}$, that are both initialised as $c_{w_{p}}=c_{l}=1$. This process stops
when $c_{l}=0$. Whenever $c_{w_{p}}=v_{p}+1$ it non-deterministically guesses
if the current position $i$ solves Eq. 85. If no, it continues traversing the
input; if yes, it sets $c_{l}$ to zero, reads and stores the next $q+1$ spin
symbol $s_{i}\ldots s_{i+q+1}$. Then it adds $h(s_{i},s_{i+q+1})$ to its stack
and further initialises an additional modulo $w_{r}$ counter $c_{w_{r}}$ at
zero. Now it iterates over the remaining input. At each step it deletes the
leftmost stored spin and stores the next symbol from the input. Additionally,
the two counters are updated.

Note that when the stored spins are $s_{i^{\prime}}\ldots s_{i^{\prime}+q+r}$,
the values of the two counters are $c_{l}=i^{\prime}-i\mod l$,
$c_{w_{r}}=i^{\prime}-i\mod w_{r}$. While $c_{l}$ is used to obtain all
further solutions $i^{\prime}=i+ml$ to Eq. 85, $c_{w_{r}}$ allows the PDA to
validate the non-deterministic guess of $i$ being a valid solution. If at any
time $c_{l}=0$ the PDA adds $h(s_{i^{\prime}},s_{i^{\prime}+q+1})$ to the
stack. Finally, when it reaches $\bullet$, $c_{w_{r}}=n-i-q-1\mod w_{r}$.
Hence, $i$ solves Eq. 85 if and only if $c_{w_{r}}=v_{r}$. If this holds, the
PDA accepts; else the initial guess was wrong and it rejects.

###### 7\. The PDA for $E_{\mathrm{fll}}$.

We now consider $(p,(w_{q},v_{q}),(w_{r},v_{q}))\in E_{\mathrm{fll}}$ and
build the PDA $P_{(p,(w_{q},v_{q}),(w_{r},v_{q}))}$. $s_{i}$ and $s_{j}$
interact if and only if

$\displaystyle\begin{aligned} i&=p+1\\\ j&=i+v_{q}+1\mod w_{q}\\\
n&=j+v_{r}\mod w_{r}\end{aligned}$ (86)

As before, let $l\coloneqq\mathrm{lcm}(w_{q},w_{r})$. The PDA starts by
traversing the input until it reaches $s_{p+1}$. It then stores $s_{p+1}$ in
its states. Next it initialises two modulo counters $c_{w_{q}}$ and $c_{l}$ at
$c_{w_{q}}=c_{l}=1$ and traverses the input until $c_{l}=0$. Whenever
$c_{w_{q}}=v_{q}+1$, it non-deterministically guesses if the current position
$j$ solves Eq. 86. If no, it continues traversing the input as before; if yes
it sets $c_{l}=0$, intitializes a second modulo counter $c_{w_{r}}$ at zero
and adds $h(s_{p+1},s_{j})$ to its stack. The PDA then traverses the remaining
input.

Whenever for the current head position $j^{\prime}$, $c_{l}=0$ it adds
$h(s_{p+1},s_{j}^{\prime})$ to its stack. Finally, when its head reaches
$\bullet$, it accepts if $c_{w_{q}}=v_{r}$, and rejects otherwise. If at any
other occasion its head reaches $\bullet$, it also rejects.

###  A.3 Proof of Theorem 1 (iii)

First we prove that if ${\sf L}_{\mathcal{M}}$ is constructive context
sensitive, then ${\sf E}_{\mathcal{M}}$ is context sensitive. So let
$\mathcal{M}$ be an Ising model with constructive context sensitive ${\sf
L}_{\mathcal{M}}$, i.e. there exists a constructive multitape LBA $M$ that
accepts ${\sf L}_{\mathcal{M}}$. Similarly to (b), given $M$ we will build
another LBA $M_{C}$ that on input $0^{i-1}10^{j-1}10^{n-j}$ computes
$C_{\mathcal{M}}(n,i,j)$.

$M_{C}$ uses $4$ extra input tapes
$T_{\mathrm{in},1},\ldots,T_{\mathrm{in},4}$ and $4$ energy tapes
$T_{E,1},\ldots,T_{E,4}$. Using its input, $M_{C}$ writes the $4$ spin
configurations

$0^{i-1}10^{j-1}10^{n-j},\quad 0^{i-1}10^{n-i},\quad 0^{j-1}10^{n-j},\quad
0^{n}$ (87)

to the $4$ extra input tapes. This can be done by copying the input and
replacing one or both $1$s with $0$s. Now $M_{C}$ simulates $M$ on these $4$
input spin configurations, and the corresponding energies obtained from $M$
are written to the $4$ energy tapes $T_{E,1},\ldots,T_{E,4}$. As $M$ is
constructive, it necessarily computes these $4$ energies before even
considering any possible input energy $e$. Note that, as these $4$ energies
are computed in binary, they can be stored within the LBA bounds, since for a
spin configuration of length $n$, the maximal absolute value of the energy is
$\binom{n}{2}$. Finally, $M_{C}$ adds the $4$ stored energies; note that
addition of binary numbers is possible for a LBA. This way, $M_{C}$ computes
$C_{\mathcal{M}}(n,i,j)$, and it accepts the input if and only if
$C_{\mathcal{M}}(n,i,j)=1$.

Conversely, if ${\sf E}_{\mathcal{M}}$ is context sensitive, there exists a
LBA $M_{E}$ that accepts ${\sf E}_{\mathcal{M}}$. According to the
Immerman–Szelepcsényi theorem there exists another LBA $M_{\bar{E}}$ that
accepts the complement of ${\sf E}_{\mathcal{M}}$. We now build a constructive
LBA $M$ that accepts ${\sf L}_{\mathcal{M}}$ as follows.

$M$ uses a specific tape $T_{S_{E}}$ to simulate $M_{E}$ and a second tape
$T_{S_{\bar{E}}}$ to simulate $M_{\bar{E}}$. In addition, $M$ has the usual
input tape $T_{\mathrm{in}}$ and energy tape $T_{E}$. On input $s_{1}\ldots
s_{n}\bullet e$, $M$ iterates over all possible pairs $(i,j)$ that satisfy
$i<j\leq n$. This can be achieved by marking the input on $T_{\mathrm{in}}$
appropriately; explicitly, by marking it as

$s_{1}^{\prime}s_{2}^{\prime\prime}s_{3}\ldots s_{n}\bullet e$ (88)

in the beginning, then moving the $s_{j}^{\prime\prime}$ mark one step to the
right after each iteration. Once $\bullet$ is reached the
$s_{j}^{\prime\prime}$ mark is removed, $M$ moves the $s_{i}^{\prime}$ mark
one position to the right and marks the spin symbol to the right of it as
$s_{i+1}^{\prime\prime}\bullet e$.

At every step of the iteration, with $s_{i}$ and $s_{j}$ marked, $M$ copies
the entire input spin configuration

$s_{1}\ldots s_{i}^{\prime}\ldots s_{j}^{\prime\prime}\ldots s_{n}$ (89)

both to $T_{S_{E}}$ and $T_{S_{\bar{E}}}$, and replaces each unmarked spin
with a $0$ and each marked spin with a $1$. Thereby the edge between $i$ and
$j$ is written to these two tapes.

Now $M$ simulates $M_{E}$ with $T_{S_{E}}$ as input and $M_{\bar{E}}$ with
$T_{S_{\bar{E}}}$ as input. If $M_{E}$ accepts, $\mathcal{M}$ contains an
interaction of $s_{i}$ and $s_{j}$, so $M$ adds $h(s_{i},s_{j})$ in binary to
its energy tape. If $M_{\bar{E}}$ accepts, $\mathcal{M}$ contains no
interaction of $s_{i}$ and $s_{j}$, so $M$ moves to the next pair of spins
without adding $h(s_{i},s_{j})$ to $T_{E}$. After that, $M$ clears both
$T_{S_{E}}$ and $T_{S_{\bar{E}}}$, before it continues with the next step of
the iteration.

When the iteration terminates, $M$ has stored $H_{\mathcal{M}}(s_{1}\ldots
s_{n})$ in binary on $T_{E}$ and compares this to the input energy $e$. If the
computed and the input energy coincide, it accepts; otherwise, it rejects.

If $n\notin N_{\mathcal{M}}$, the iteration terminates without $M_{E}$
accepting a single edge, in which case $M$ rejects the input. This case can be
checked by, prior to the iteration over possible edges, writing a
distinguished symbol to the energy tape that is removed once the first energy
is added.

###  A.4 Proof of Theorem 1 (iv)

The proof follows a similar line of reasoning as that of (iii). If ${\sf
L}_{\mathcal{M}}$ is decidable there exists a Turing machine $M$ that decides
it. From this we can build a second Turing machine $M_{H}$ that computes
$H_{\mathcal{M}}$ as a function, i.e. that on input $s_{1}\ldots s_{n}$ with
$n\in N_{\mathcal{M}}$, after a finite number of steps, halts with
$H_{\mathcal{M}}(s_{1}\ldots s_{n})$ written to its output tape
$T_{\mathrm{out}}$. This can be achieved as follows: On input $s_{1}\ldots
s_{n}$, $M_{H}$ iterates over

$e\in u\left(\left\\{-\binom{n}{2},\ldots,\binom{n}{2}\right\\}\right)$ (90)

i.e. over all possible energies that the input may have. For each, $M_{H}$
writes $s_{1}\ldots s_{n}\bullet e$ to an additional tape $T_{S}$ and
simulates $T$ with $T_{S}$ as input. As $M$ decides ${\sf L}_{\mathcal{M}}$,
this simulation halts after a finite number of steps. If $M$ accepts
$s_{1}\ldots s_{n}\bullet e$, then $e$ is the correct energy, i.e.

$e=H_{\mathcal{M}}(s_{1}\ldots s_{n})$ (91)

and $M_{H}$ writes $e$ to $T_{\mathrm{out}}$ and halts. If $M$ rejects,
$M_{H}$ continues with the next step of the iteration. If the iteration
terminates without $M_{H}$ halting, then $n\notin N_{\mathcal{M}}$ and $M_{H}$
halts and rejects.

Using $M_{H}$, we can proceed analogously to the proof of (iii), in order to
build a Turing machine $M_{C}$ that on input $0^{i-1}10^{j-1}10^{n-j}$
computes $C_{\mathcal{M}}(n,i,j)$. So $M_{C}$ decides ${\sf E}_{\mathcal{M}}$.

Conversely, if ${\sf E}_{\mathcal{M}}$ is decidable, as in the proof of (iii)
we can build a Turing machine $M$ that on input $s_{1}\ldots s_{n}\bullet e$
iterates over all possible edges $(i,j)$ with $i<j\leq n$ and uses the decider
for ${\sf E}_{\mathcal{M}}$, $M_{E}$, to decide if
$(i,j)\in(E_{\mathcal{M}})_{n}$. If yes, $M$ adds $h(s_{i},s_{j})$ to its
energy tape $T_{E}$ and continues the iteration. If no, $M$ continues the
iteration without adding the energy. Once the iteration over edges terminates,
$M$ has $H_{\mathcal{M}}(s_{1}\ldots s_{n})$ stored on its energy tape. Hence
${\sf L}_{\mathcal{M}}$ can be decided by letting $M$ accept the input if and
only if there was at least one edge accepted by $M_{E}$, to ensure that $n\in
N_{\mathcal{M}}$, and additionally input energy and computed energy are equal.

##  Appendix B Formal language theory toolbox

Let $\Sigma$ be a finite set, called the alphabet. Let $\Sigma^{*}$ denote the
free monoid over $\Sigma$, with unit being the empty string $\epsilon$. In the
context of formal language theory $\Sigma^{*}$ is often called the Kleene star
of $\Sigma$. $\Sigma^{*}$ contains all finite strings that can be formed with
symbols from $\Sigma$, including the empty string. A formal language ${\sf L}$
over $\Sigma$ is a subset of $\Sigma^{*}$.

While most languages can only be characterised in an extensive way, namely by
specifying the (infinite) set ${\sf L}\subseteq\Sigma^{*}$ itself, some admit
a finite description. There are two ways of providing this finite description:
by providing a grammar $G$ that generates ${\sf L}$, or by constructing an
automaton that accepts ${\sf L}$.

######  Definition 7 (Grammar).

A _grammar_ is a $4$-tuple $G=(S,T,NT,P)$, where

  * •

$S\in NT$ is a distinguished symbol, called the start symbol of $G$;

  * •

$T$, $NT$ are disjoint, finite sets, whose elements are called terminal and
non-terminal symbols respectively;

  * •

$P\subseteq(T\cup NT)^{*}\times(T\cup NT)^{*}$ is a finite set of production
rules. For $(\alpha,\beta)\in P$ we write $\alpha\rightarrow\beta$ and for
$\\{(\alpha,\beta),(\alpha,\beta^{\prime}),(\alpha,\beta^{\prime\prime})\\}\subset
P$ we write
$\alpha\rightarrow\beta\mid\beta^{\prime}\mid\beta^{\prime\prime}$.

Given a string $w\in(T\cup NT)^{*}$, a production rule
$\alpha\rightarrow\beta\in P$ is applied to it by replacing an occurrence of
$\alpha$ as a substring of $w$ with $\beta$. If a string $w$ can be obtained
from another string $w^{\prime}$ by repeated application of production rules
of $G$ we say that $w$ can be derived from $w^{\prime}$ by means of $G$, and
write $w^{\prime}\Rightarrow^{*}_{G}w$. The language ${\sf L}(G)$ that a
grammar $G$ generates is the set of all terminal strings that can be derived
from the start symbol $S$,

$\displaystyle{\sf L}(G)\coloneqq\\{w\in T^{*}\mid S\Rightarrow_{G}^{*}w\\}$
(92)

Grammars can be classified according to the form of the production rules they
contain. The most famous such classification is the Chomsky hierarchy,

$\displaystyle\text{regular}\subset\text{context free}\subset\text{context
sensitive}\subset\text{unrestricted}$ (93)

where all inclusions are strict [37, 38]. A grammar $G$ belongs to either of
these classes if for all production rules $\alpha\to\beta\in P$, the following
holds:

regular

if $\alpha\in NT$ and $\beta=\epsilon$ or $\beta\in T$ or $\beta=bB$ with
$b\in T$ and $B\in NT$;

context free

if $\alpha\in NT$;

context sensitive

if $aBc\rightarrow adc$, where $a,c\in(T\cup NT)^{*}$, $B\in NT$, and
$\epsilon\neq d\in(T\cup NT)^{*}$;

unrestricted

in any case.

This hierarchy of grammars can be lifted to a hierarchy of languages, by
calling a formal language ${\sf L}$ regular if there exists a regular grammar
with ${\sf L}={\sf L}(G)$, and similar for context free and context sensitive.
The class of languages corresponding to unrestricted grammars is called
recursively enumerable. If both a language and its complement are recursively
enumerable, then it is called decidable.

For every level in the Chomsky hierarchy, there exists a type of automaton
(i.e. a model of computation) that accepts the languages from that level:
regular languages are accepted by finite state automata (FSA), context free
languages are accepted by pushdown automata (PDA), context sensitive languages
are accepted by linear bounded automata (LBA), and recursively enumerable
language are accepted by Turing machines (TM). Proving that a language is
accepted by a certain type automaton is equivalent to proving that it is in
the corresponding level. We now review these automata (see e.g. [32, 39]).

A FSA can be imagined as a machine with one tape, and a head that scans one
cell of the input tape at a time. The FSA has a finite number of states in its
head as memory. The computation starts with the input written on the tape and
the head placed over the first input symbol. At each computation step, it
reads the symbol that its head is currently placed over, and, depending on the
symbol on the tape and the current state, transitions to a new state. The head
then moves to the next input symbol. A FSA can neither change the direction of
its head movement nor overwrite the tape.

######  Definition 8.

(Finite state automaton) A _finite state automaton_ is a $5$-tuple
$F=(Q,\Sigma,\delta,q_{0},A)$, where

  * •

$Q$ and $\Sigma$ are finite sets called the states and the input alphabet;

  * •

$\delta:Q\times\Sigma\rightarrow Q$ is called the transition function;

  * •

$q_{0}\in Q$ is the start state;

  * •

$A\subseteq Q$ are the accept states.

The transition function encodes one computation step of the FSA $F$: When in
state $q$ upon reading $s$, $F$ transitions to state $q^{\prime}=\delta(q,s)$.
On input $w_{1}\ldots w_{n}\in\Sigma^{*}$, $F$ starts in state $q_{0}$. It
then processes the entire input: for each input symbol it uses $\delta$ and
the current state to compute the new state; then it moves on with the next
input symbol. After processing the entire input, if $F$ is in a state $f\in
A$, the input is accepted by $F$; else, $F$ rejects.

A PDA can be imagined as a FSA which additionally has access to a stack.
Specifically, at each step of the computation, the head of the PDA reads the
current symbol on the tape, pops a symbol from the top of the stack, and
pushes a finite number of symbols onto the stack. Then the head moves to the
next symbol.

######  Definition 9 (Pushdown automaton).

A _pushdown automaton_ is a $7$-tuple $P=(Q,\Sigma_{\rm in},\Sigma_{\rm
stack},\delta,q_{0},Z,A)$, where

  * •

$Q,\Sigma_{\rm in}$ and $\Sigma_{\rm stack}$ are finite sets called the
states, input alphabet and stack alphabet;

  * •

$\delta\subseteq(Q\times(\Sigma_{\rm in}\cup\\{\epsilon\\})\times\Sigma_{\rm
stack})\times(Q\times\Sigma_{\rm stack}^{*})$ is a finite set called the
transition relation;

  * •

$q_{0}\in Q$ is the initial state;

  * •

$Z\in\Sigma_{\rm stack}$ is the initial stack symbol;

  * •

$A\subseteq Q$ are the accept states.

The transition relation models one step of the computation: When in state $q$,
upon reading $x$ and popping $s$, $P$ transitions to state $q^{\prime}$ and
pushes $s^{\prime}$ to the stack, where $q^{\prime}$ and $s^{\prime}$ are such
that

$(q,x,s,q^{\prime},s^{\prime})\in\delta$ (94)

Then $P$ moves its head to the next input symbol. If there are multiple such
$q^{\prime}$, $s^{\prime}$, $P$ branches its computation to pursue all such
options simultaneously.

$P$ is called deterministic if for any $q\in Q$, $x\in\Sigma_{\rm in}$ and
$s\in\Sigma_{\rm stack}$, there exist a unique $q^{\prime}\in Q$,
$s^{\prime}\in\Sigma_{\rm stack}^{*}$, such that either

$(q,x,s,q^{\prime},s^{\prime})\in\delta\quad\text{or}\quad(q,\epsilon,s,q^{\prime},s^{\prime})\in\delta$
(95)

Otherwise $P$ is called non-deterministic.

An input string $w_{1}\ldots w_{n}\in\Sigma_{\rm in}^{*}$ is accepted by $P$
if with its head placed over the first symbol $w_{1}$, in state $q_{0}$ and
with its stack containing only one symbol $Z$, after processing the entire
input as dictated by $\delta$, there is at least one computation path that
leads to a state $f\in A$. Otherwise the input is rejected by $P$.

The most powerful notion of machine that we will encounter in this work is
that of a Turing machine (TM). A TM can be imagined as a machine with a finite
number of states and an input tape. In contrast to a PDA, a TM can overwrite
the input tape, and move left or right.

######  Definition 10 (Turing machine).

A _Turing machine_ (TM) is a $7$-tuple $M=(Q,\Sigma_{\rm in},\Sigma_{\rm
tape},\delta,q_{0},A,B)$, where

  * •

$Q,\Sigma_{\rm tape}$ are finite sets called the states and the tape alphabet;

  * •

$\Sigma_{\rm in}\subseteq\Sigma_{\rm tape}$ is the input alphabet;

  * •

$\delta\subseteq(Q\times\Sigma_{\rm tape})\times(Q\times\Sigma_{\rm
tape}\times\\{L,R\\})$ is the transition relation;

  * •

$q_{0}\in Q$ is the start state;

  * •

$A\subseteq Q$ are the final states;

  * •

$B\in\Sigma_{\rm tape}$ is the blank symbol that represents an empty input
cell.

When in state $q$ upon reading $s$, $M$ transitions to state $q^{\prime}$,
overwrites $s$ with $s^{\prime}$ and moves its head one step in the direction
specified by $m\in\\{L,R\\}$, where $(q^{\prime},s^{\prime},m)$ are specified
by $\delta$,

$(q,s,q^{\prime},s^{\prime},m)\in\delta$ (96)

If there are multiple such options $M$ branches its computation path to carry
them out simultaneously.

$M$ is called deterministic if for each $(q,s)\in Q\times\Sigma_{\rm tape}$
there exists at most one $(q^{\prime},s^{\prime},m)\in Q\times\Sigma_{\rm
tape}\times\\{L,R\\}$ such that (96) holds. Otherwise $M$ is called non-
deterministic.

If for a given state and input symbol $(q,s)$ there is no
$(q^{\prime},s^{\prime},m)$ satisfying (96), $M$ is said to halt in state $q$.
An input string $w_{1}\ldots w_{n}\in\Sigma_{\rm in}$ is accepted by $M$ if
$M$ when started in state $q_{0}$ with $w_{1}\ldots w_{n}$ written on its
input tape and its head placed over the first cell, after repeatedly
performing the transitions as specified by $\delta$, after a finite number of
steps there is at least one computation path that leads to $M$ halting in a
final state.

Whereas a TM may use an unbounded amount of tape to carry out the computation,
for the weaker notion of a linear bounded automaton (LBA) the accessible tape
is limited to the cells which are initially used by the input string.

######  Definition 11 (Linear bounded automaton).

A _linear bounded automaton_ is a $9$-tuple $L=(Q,\Sigma_{\rm in},\Sigma_{\rm
tape},\delta,q_{0},A,B,\bot_{L},\bot_{R})$, where

  * •

$(Q,\Sigma_{\rm in},\Sigma_{\rm tape},\delta,q_{0},A,B)$ is a Turing machine

  * •

$\bot_{L},\bot_{R}\in\Sigma_{\rm tape}$ are two special symbols that satisfy

$\displaystyle\begin{aligned}
(q,\bot_{L},q^{\prime},s^{\prime},m)\in\delta&\Rightarrow s^{\prime}=\bot_{L}\
\text{and}\ m=R\\\ (q,\bot_{R},q^{\prime},s^{\prime},m)\in\delta&\Rightarrow
s^{\prime}=\bot_{R}\ \text{and}\ m=L\end{aligned}$ (97)

The special symbols $\bot_{L},\bot_{R}$ serve as left and right endmarkers of
the tape. Throughout the computation, $L$ neither overwrites these endmarkers
nor moves its head past them. Other than that, the computation works exactly
like that of a TM.

Relaxing the definition of the LBA such that the accessible tape space is a
linear function of the input length, or allowing the LBA to perform its
computation on multiple tapes does not change the class of problems it can
solve [40, Theorem 12]. Hence, the class of context sensitive languages is
identical with the complexity class NLINSPACE of problems that can be solved
in linear space on a non-deterministic Turing machine [41, Theorem 3.33].

Finally, we stress that most languages do not have a grammar (or,
equivalently, are not recognised by a Turing machine), as there are
uncountably many languages but countably many grammars (or Turing machines).
Explicitly, the number of languages over a finite alphabet $\Sigma$ is
$|\wp(\Sigma^{*})|=2^{|\mathbb{N}|}$, whereas the number of grammars (or
Turing machines) is $|\mathbb{N}|$.

##  Appendix C The grammar of the 1d and 2d Ising model

Here we provide grammars of the 1d and 2d Ising model (Section C.2 and Section
C.3, respectively). Before presenting the grammar of the 1d Ising model, we
present a connection to lattice paths which provides an intuitive and
transparent picture of the grammar (Section C.1).

While we have already proven that ${\sf L}_{\mathrm{1d}}$ is context free and
${\sf L}_{\mathrm{2d}}$ is context sensitive by means of our main theorem, the
following provides independent proofs of the same statements, and an
alternative perspective on the same facts—if the automaton recognising a
language is a ‘passive’ description of this language, the grammar generating
it can be seen an ‘active’ description thereof. As a matter of fact, the
connection to lattice paths of Section C.1 provides yet another proof of the
context freeness of ${\sf L}_{\mathrm{1d}}$. So, in total, we provide three
proofs of the context freeness of the language of the 1d Ising model: by
applying our main theorem to the 1d Ising model (Section IV.1), via the
connection to lattice paths (Section C.1), and by providing a context free
grammar (Section C.2).

We remark that proving the complexity of an Ising model by providing a grammar
only works for certain examples. This underlines the generality and usefulness
of Theorem 1.

###  C.1 The 1d Ising model and lattice paths

Here we provide another proof (besides Section IV.1 and Section C.2) that the
language of the 1d Ising model, ${\sf L}_{\mathrm{1d}}$, is context free. We
do so by establishing a connection between ${\sf L}_{\mathrm{1d}}$ and lattice
paths. We construct a corresponding context free language of lattice paths,
${\sf L}_{\mathrm{p}}$, that is related to ${\sf L}_{\mathrm{1d}}$ by a
mapping (called a generalised string homormorphism) which guarantees that the
two languages, ${\sf L}_{\mathrm{1d}}$ and ${\sf L}_{\mathrm{p}}$, have the
same complexity in the Chomsky hierarchy. Thus context freeness of ${\sf
L}_{\mathrm{1d}}$ is implied by context freeness of ${\sf L}_{\mathrm{p}}$.

We conjecture that the connection between ${\sf L}_{\mathrm{1d}}$ and lattice
paths is a consequence of the Chomsky–Schützenberger representation theorem,
which states that every context free language can be constructed from a
language of matched brackets of different types in a natural way [32, Supp.
Lec. G]. The lattice paths used in this section can be seen as a variant of
such languages of matched brackets.

######  Definition 12 (Lattice path).

A _lattice path_ with steps $\uparrow$ and $\downarrow$ is a string
$l\in\\{\uparrow,\downarrow\\}^{*}$.

We draw a lattice path by taking the lattice $\mathbb{Z}^{2}$, starting at
$(0,0)$ and then traversing $l$, consecutively moving one step in $(+1,+1)$
direction for each $\uparrow$ and one step in $(+1,-1)$ direction for each
$\downarrow$ that we encounter (see Fig. 6).

Figure 6: Representation of the lattice path
$\downarrow\uparrow\downarrow\uparrow\uparrow\downarrow$.

We assign an energy to such a lattice path $l$ by taking the difference
between the number of up-steps $\\#^{\uparrow}(l)$ and the number of down-
steps $\\#^{\downarrow}(l)$,

$\displaystyle\begin{aligned}
H_{\mathrm{p}}:\\{\uparrow,\downarrow\\}^{*}&\rightarrow\mathbb{Z}\\\
l&\mapsto\\#^{\uparrow}(l)-\\#^{\downarrow}(l)\end{aligned}$ (98)

With this, we define a formal language that encodes $H_{\mathrm{p}}$ as

$\displaystyle{\sf L}_{\mathrm{p}}\coloneqq\\{l\bullet u(H_{\mathrm{p}}(l))\
|\ l\in\\{\uparrow,\downarrow\\}^{*}\\}$ (99)

This language is related to ${\sf L}_{\mathrm{1d}}$ by two generalised string
homomorphisms (GSH) (see [42] and [40, Chapter 11.2]). A generalised string
homomorphism can be realised as a machine that computes an output string from
a given input string. For our purpose it suffices to consider a deterministic
GSH.

######  Definition 13 (Generalised string homomorphism).

A _generalised string homomorphism_ (GSH) is a $5$-tuple
$M=(Q,\Sigma_{\mathrm{in}},\Sigma_{\mathrm{out}},\delta,q_{0})$, where

  * •

$Q,\Sigma_{\mathrm{in}}$ and $\Sigma_{\mathrm{out}}$ are finite sets called
the states, input alphabet and output alphabet;

  * •

$q_{0}\in Q$ is the start state;

  * •

$\delta:Q\times\Sigma_{\mathrm{in}}\rightarrow
Q\times\Sigma_{\mathrm{out}}^{*}$ is the transition function.

When in state $q\in Q$, upon reading $x\in\Sigma_{\mathrm{in}}$, $M$ outputs
$s\in\Sigma_{\mathrm{out}}^{*}$ and transitions to state $q^{\prime}$ before
moving on with the next symbol, where $(q^{\prime},s)\coloneqq\delta(q,x)$.
Given an input string $w\in\Sigma_{\mathrm{in}}^{*}$, by starting in state
$q_{0}$ and processing $w$ in this fashion, $M$ produces an output string.
Thereby it defines a map which by abuse of notion will also be denoted as $M$

$\displaystyle M:\Sigma_{\mathrm{in}}^{*}\rightarrow\Sigma_{\mathrm{out}}^{*}$
(100)

Note that a GSH with only one state equals a conventional string homomorphism.
A multistate GSH can additionally use its states to alter how symbols from
$\Sigma_{\mathrm{in}}$ are mapped to strings in $\Sigma_{\mathrm{out}}$.

A GSH is called $\epsilon$-free if for every $w\in\Sigma_{\mathrm{in}}$ it
outputs at least one symbol.

######  Lemma 1 (Theorem 11.1 in [40]).

Let ${\sf L}\subseteq\Sigma_{1}^{*}$ be a context free language and
$M=(Q,\Sigma_{1},\Sigma_{2},\delta,q_{0})$ an $\epsilon$-free GSH, then also
the image of $L$ under $M$ is context free.

GSH can be specified by a graph where every node corresponds to a state, and a
directed edge from $q_{1}$ to $q_{2}$ with label $w\mid x$ denotes that
$\delta(q_{1},w)=(q_{2},x)$ (see Fig. 7 and [40, Figure 11.1]).

$S_{0}$$I^{1}_{0}$$I^{0}_{0}$$E_{0}$$\uparrow\,\mid 01$$\downarrow\,\mid
00$$\downarrow\,\mid 1$$\downarrow\,\mid 0$$\uparrow\,\mid 0$$\uparrow\,\mid
1$$\bullet\mid\bullet$$\bullet\mid\bullet$$+\mid+$$-\mid-$ Figure 7: The
transition function of GSH $M_{0}$. All transition rules that are not drawn
lead to the only missing state, $R_{0}$ and output $\bullet$, irrespective of
the input.

The correspondence between ${\sf L}_{\mathrm{p}}$ and ${\sf L}_{\mathrm{1d}}$
is provided by two GSH $M_{0}$ and $M_{1}$, where $M_{0}$ ($M_{1}$) maps
lattice paths to spin configurations that start with $s_{1}=0$ ($s_{1}=1$).
They are defined by

$\displaystyle
M_{s}\coloneqq(Q_{s},\\{\uparrow,\downarrow,\bullet,+,-\\},\\{0,1,\bullet,+,-\\},\delta_{s},S_{s})$
(101)

where $s\in\\{0,1\\}$. $M_{s}$ uses states

$\displaystyle Q_{s}\coloneqq\\{S_{s},I^{0}_{s},I^{1}_{s},E_{s},R_{s}\\}$
(102)

The transition function $\delta_{0}$ is shown in Fig. 7, and $\delta_{1}$ only
differs in the treatment of the first input symbols

$\displaystyle\begin{aligned}
\delta_{1}(S_{1},\uparrow)\coloneqq(I^{0}_{1},10)\\\
\delta_{1}(S_{1},\downarrow)\coloneqq(I^{1}_{1},11)\end{aligned}$ (103)

Note that these mappings are not possible by conventional string
homomorphisms, as deciding if a symbol $l_{i}=\uparrow$ should be mapped to a
spin state $s_{i+1}=0$ or $s_{i+1}=1$ requires knowledge of the previous spin
state $s_{i}$.

######  Example 1.

Consider the lattice path
$\downarrow\uparrow\downarrow\uparrow\uparrow\downarrow$, shown in Fig. 6.
Clearly $H_{\mathrm{p}}(l)=0$. Applying $M_{0}$ and $M_{1}$ to the
corresponding string in ${\sf L}_{\mathrm{p}}$ yields

$\displaystyle\begin{aligned}
M_{0}(\downarrow\uparrow\downarrow\uparrow\uparrow\downarrow\bullet)&=0011011\bullet\\\
M_{1}(\downarrow\uparrow\downarrow\uparrow\uparrow\downarrow\bullet)&=1100100\bullet\end{aligned}$
(104)

Both $M_{0}$ and $M_{1}$ are injective when restricted to ${\sf
L}_{\mathrm{p}}$. Moreover,

$\displaystyle{\sf L}_{\mathrm{1d}}=M_{0}({\sf L}_{\mathrm{p}})\cup M_{1}({\sf
L}_{\mathrm{p}})$ (105)

We thus have a $2$-to-$1$ correspondence between ${\sf L}_{\mathrm{1d}}$ and
${\sf L}_{\mathrm{p}}$. The lattice path that corresponds to a spin
configuration can be interpreted as uncovering the information about how the
global energy of the spin configuration is composed locally. The fact that
this correspondence is $2$-to-$1$ follows from the bit-flip symmetry of the
Ising Hamiltonian $H_{\mathcal{M}}$: for any spin configuration $s_{1}\ldots
s_{n}\in S_{\mathcal{M}}$,

$\displaystyle
H_{\mathcal{M}}(\bar{s}_{1}\ldots\bar{s}_{n})=H_{\mathcal{M}}(s_{1}\ldots
s_{n})$ (106)

where $\bar{s}$ denotes application of the bit-flip operation, i.e.
$\bar{0}=1$ and $\bar{1}=0$. Also the two maps $M_{s}$ are precisely related
by this flip operation. Moving from spin configurations to lattice paths can
thus be seen as modding out this bit flip symmetry.

######  Proposition 3.

${\sf L}_{\mathrm{1d}}$ is context free.

###### Proof.

We first prove that ${\sf L}_{\mathrm{p}}$ is context free. The claim then
follows from Lemma 1 and the fact that the union of context free languages is
itself context free [40, Theorem 6.1].

We start by considering the subset of lattice paths with energy $0$

$\displaystyle{\sf L}_{\mathrm{p}}^{0}\coloneqq H_{\mathrm{p}}^{-1}(\\{0\\})$
(107)

Note that for any $l=l_{1}\ldots l_{n}\in{\sf L}_{\mathrm{p}}^{0}$ one of the
following three cases holds true

  1. 1.

$n=2$ and either $l=\uparrow\downarrow$ or $l=\downarrow\uparrow$

  2. 2.

$l_{1}\neq l_{n}$ and thus $l_{2}\ldots l_{n-1}\in{\sf L}_{\mathrm{p}}^{0}$

  3. 3.

there exists $w,w^{\prime}\in{\sf L}_{\mathrm{p}}^{0}$ with $l=ww^{\prime}$

${\sf L}_{\mathrm{p}}^{0}$ is generated by the grammar

$\displaystyle
G_{\mathrm{p}}^{0}\coloneqq(S_{\mathrm{p}}^{0},\\{\uparrow,\downarrow\\},\\{S_{\mathrm{p}}^{0}\\},P_{\mathrm{p}}^{0})$
(108)

where the production rules $P_{\mathrm{p}}^{0}$ are given as

$\displaystyle\begin{aligned} S_{\mathrm{p}}^{0}\rightarrow\
\uparrow\downarrow\ |\ \downarrow\uparrow\ |\ \uparrow
S_{\mathrm{p}}^{0}\downarrow\ |\ \downarrow S_{\mathrm{p}}^{0}\uparrow\ |\
S_{\mathrm{p}}^{0}S_{\mathrm{p}}^{0}\end{aligned}$ (109)

Clearly all production rules produce an equal number of $\uparrow$ and
$\downarrow$ symbols, so by induction over the derivation length of any word
$w$ in the language (i.e. the number of production rules applied to derive $w$
from $S_{\mathrm{p}}^{0}$), it follows that ${\sf
L}(G_{\mathrm{p}}^{0})\subseteq{\sf L}_{\mathrm{p}}^{0}$.

As all strings in ${\sf L}_{\mathrm{p}}^{0}$ admit one of the three forms
above, and all these forms are captured by the production rules, by induction
over the length of strings in ${\sf L}_{\mathrm{p}}^{0}$ it follows that all
such strings can be derived by $P_{\mathrm{p}}^{0}$, so ${\sf
L}_{\mathrm{p}}^{0}\subseteq{\sf L}(G_{\mathrm{p}}^{0})$. Thus

${\sf L}_{\mathrm{p}}^{0}={\sf L}(G_{\mathrm{p}}^{0})$ (110)

We now construct a grammar for ${\sf L}_{\mathrm{p}}$,

$\displaystyle
G_{\mathrm{p}}\coloneqq(S_{\mathrm{p}},T_{\mathrm{p}},NT_{\mathrm{p}},P_{\mathrm{p}})$
(111)

with terminal symbols

$\displaystyle T_{\mathrm{p}}\coloneqq\\{\uparrow,\downarrow,\bullet,+,-\\}$
(112)

non-terminal symbols

$\displaystyle
NT_{\mathrm{p}}\coloneqq\\{S_{\mathrm{p}},S_{\mathrm{p}}^{+},S_{\mathrm{p}}^{-},S_{\mathrm{p}}^{0},I_{\mathrm{p}}^{+},I_{\mathrm{p}}^{-}\\}$
(113)

and production rules $P_{\mathrm{p}}$

$\displaystyle S_{\mathrm{p}}$ $\displaystyle\rightarrow$ $\displaystyle
S_{\mathrm{p}}^{0}\bullet\ |\ S_{\mathrm{p}}^{+}\ |\ S_{\mathrm{p}}^{-}$
(114a) $\displaystyle S_{\mathrm{p}}^{+}$ $\displaystyle\rightarrow$
$\displaystyle\uparrow I_{\mathrm{p}}^{+}+\ |\ S_{\mathrm{p}}^{0}\uparrow
I_{\mathrm{p}}^{+}+\ |$ (114b) $\displaystyle\uparrow
S_{\mathrm{p}}^{0}I_{\mathrm{p}}^{+}+\ |\ S_{\mathrm{p}}^{0}\uparrow
S_{\mathrm{p}}^{0}I_{\mathrm{p}}^{+}+$ $\displaystyle S_{\mathrm{p}}^{-}$
$\displaystyle\rightarrow$ $\displaystyle\downarrow I_{\mathrm{p}}^{-}-\ |\
S_{\mathrm{p}}^{0}\downarrow I_{\mathrm{p}}^{-}-\ |$ (114c)
$\displaystyle\downarrow S_{\mathrm{p}}^{0}I_{\mathrm{p}}^{-}-\ |\
S_{\mathrm{p}}^{0}\downarrow S_{\mathrm{p}}^{0}I_{\mathrm{p}}^{-}-$
$\displaystyle I_{\mathrm{p}}^{+}$ $\displaystyle\rightarrow$
$\displaystyle\bullet\ |\ \uparrow I_{\mathrm{p}}^{+}+\ |\ \uparrow
S_{\mathrm{p}}^{0}I_{\mathrm{p}}^{+}+$ (114d) $\displaystyle
I_{\mathrm{p}}^{-}$ $\displaystyle\rightarrow$ $\displaystyle\bullet\ |\
\downarrow I_{\mathrm{p}}^{-}-\ |\ \downarrow
S_{\mathrm{p}}^{0}I_{\mathrm{p}}^{-}-$ (114e)

Additionally, $P_{\mathrm{p}}$ contains all productions in
$P_{\mathrm{p}}^{0}$.

First, observe that all terminal expressions that can be derived with the
production rules $P_{\mathrm{p}}$ are well-formed, i.e. they contain exactly
one $\bullet$ symbol, only $\uparrow$, $\downarrow$ symbols left of it and a
potentially empty string that consists of either only $+$ or only $-$ symbols
to the right of it. Besides, all rules in $P_{\mathrm{p}}$ produce an equal
number of $\uparrow$ and $+$, or $\downarrow$ and $-$. Thus, again by
induction over the derivation length it follows that ${\sf
L}(G_{\mathrm{p}})\subseteq{\sf L}_{\mathrm{p}}$.

To prove that ${\sf L}_{\mathrm{p}}\subseteq{\sf L}(G_{\mathrm{p}})$, note
that the production rules Eq. 114a separate the strictly positive, strictly
negative and zero energy case, so these three cases can be treated
independently. The lattice paths with zero energy can of course be obtained by
the rules in $P_{\mathrm{p}}^{0}$. For a lattice path of strictly positive
energy,

$\displaystyle l_{1}\ldots l_{n}\bullet+^{k}\in{\sf L}_{\mathrm{p}}$ (115)

one can always separate a maximal prefix with energy $1$, i.e. there always
exists an $i\in\\{2,\ldots,n\\}$ such that $l^{(1)}\coloneqq l_{1}\ldots
l_{i}$ has energy $+1$. If $k=1$ then $i=n$; else, $l_{i+1}=\uparrow$ as
otherwise $i$ would not be maximal. Iteratively separating maximal prefixes
with energy $+1$ from $l_{1}\ldots l_{n}$ yields

$\displaystyle l_{1}\ldots l_{n}=l^{(1)}\ldots l^{(k)}$ (116)

such that also for all $i=2,\ldots,k-1$, $l^{(i)}$ is a maximal energy $+1$
prefix of $l^{(i+1)}\ldots l^{(k)}$. An example is shown in Fig. 8. The first
such maximal prefix $l^{(1)}\coloneqq l_{1}\ldots l_{i}$ of energy $+1$ admits
one of the following forms

  * •

$l^{(1)}=\uparrow$

  * •

$l^{(1)}=w\uparrow$ with $w\in{\sf L}_{\mathrm{p}}^{0}$

  * •

$l^{(1)}=\uparrow w$ with $w\in{\sf L}_{\mathrm{p}}^{0}$

  * •

$l^{(1)}=w\uparrow w^{\prime}$ with $w,w^{\prime}\in{\sf L}_{\mathrm{p}}^{0}$

These $4$ possibilities are precisely covered by the four production rules in
Eq. 114b. As after that, all further maximal prefixes $l^{(i)}$, with
$i=2,\ldots,k$ necessarily start with $\uparrow$, there are only two
possibilities for these

  * •

$l^{(i)}=\uparrow$

  * •

$l^{(i)}=\uparrow w$ with $w\in{\sf L}_{\mathrm{p}}^{0}$

These two options can be generated by the two production rules in Eq. 114d.

This works in the same way for lattice paths with negative energy. Proceeding
by induction over the energy, treating positive and negative energies
separately, we see that the production rules in $P_{\mathrm{p}}$ derive any
string in ${\sf L}_{\mathrm{p}}$ and hence ${\sf L}_{\mathrm{p}}\subseteq{\sf
L}(G_{\mathrm{p}})$. Thus,

${\sf L}_{\mathrm{p}}={\sf L}(G_{\mathrm{p}})$ (117)

As $G_{\mathrm{p}}$ is context free, so is ${\sf L}_{\mathrm{p}}$. ∎

Figure 8: Lattice path
$l=\uparrow\uparrow\downarrow\uparrow\uparrow\uparrow\uparrow\downarrow\uparrow$,
with $H_{\mathrm{p}}(l)=5$ and split in maximal prefixes of energy $+1$,
$l^{(1)}=l_{1}l_{2}l_{3}$, $l^{(2)}=l_{4}$, $l^{(3)}=l_{5}$,
$l^{(4)}=l_{6}l_{7}l_{8}$, $l^{(5)}=l_{9}$.

The central idea of these grammars is the following. At the first step of each
derivation, they distinguish between zero, positive or negative energies. In
the zero energy case, only strings that keep the overall energy zero can be
appended. In the strictly positive (negative) case, only strings that increase
(decrease) the overall energy can be appended. This property is somewhat
counterintuitive but necessary, as within context free grammars it is not
possible to define production rules that cancel positive against negative
energies:

$\displaystyle+-\rightarrow\epsilon$ (118)

###  C.2 A context free grammar for the 1d Ising model

Here we provide a context free grammar for the language of the 1d Ising model,
${\sf L}_{\mathrm{1d}}$. We start by providing a context free grammar for the
zero energy spin configurations (Proposition 4), which will act as the
backbone of the grammar for ${\sf L}_{\mathrm{1d}}$ (Proposition 5). The ideas
behind the grammar for ${\sf L}_{\mathrm{1d}}$ are very similar to those
behind the grammar for lattice paths ${\sf L}_{\mathrm{p}}$.

######  Proposition 4 (Grammar for ${\sf L}_{\mathrm{1d}}^{0}$).

Let ${\sf L}_{\mathrm{1d}}^{0}$ be the set of zero energy spin configurations
of the Ising model $\mathcal{M}_{\mathrm{1d}}$

$\displaystyle{\sf L}_{\mathrm{1d}}^{0}\coloneqq
H_{\mathrm{1d}}^{-1}(\\{0\\})$ (119)

Let $i,j\in\\{0,1\\}$ with $i\neq j$, whenever they appear in the same
production rule. The context free grammar

$\displaystyle
G_{\mathrm{1d}}^{0}\coloneqq(S_{\mathrm{1d}}^{0},T_{\mathrm{1d}}^{0},NT_{\mathrm{1d}}^{0},P_{\mathrm{1d}}^{0})$
(120)

with start symbol $S_{\mathrm{1d}}^{0}$, terminal symbols

$\displaystyle T_{\mathrm{1d}}^{0}\coloneqq\\{0,1\\}$ (121)

non-terminal symbols

$\displaystyle
NT_{\mathrm{1d}}^{0}\coloneqq\\{S_{\mathrm{1d}}^{0},S_{ii},S_{ij},\bar{S}_{ii},\bar{S}_{ij}\\}$
(122)

and production rules $P_{\mathrm{1d}}^{0}$

$\displaystyle S_{\mathrm{1d}}^{0}$ $\displaystyle\rightarrow S_{ii}\ |\
S_{ij}$ (123a) $\displaystyle S_{ii}$ $\displaystyle\rightarrow iS_{ji}i\ |\
iS_{ij}i\ |\ S_{ii}\bar{S}_{ii}\ |\ S_{ij}\bar{S}_{ji}$ (123b) $\displaystyle
S_{ij}$ $\displaystyle\rightarrow ijj\ |\ iij\ |\ iS_{jj}j\ |\ iS_{ii}j\ |\
S_{ij}\bar{S}_{jj}\ |\ S_{ii}\bar{S}_{ij}$ (123c) $\displaystyle\bar{S}_{ii}$
$\displaystyle\rightarrow S_{ji}i\ |\ S_{ij}i\ |\ \bar{S}_{ii}\bar{S}_{ii}\ |\
\bar{S}_{ij}\bar{S}_{ji}$ (123d) $\displaystyle\bar{S}_{ij}$
$\displaystyle\rightarrow jj\ |\ ij\ |\ S_{jj}j\ |\ S_{ii}j\ |\
\bar{S}_{ij}\bar{S}_{jj}\ |\ \bar{S}_{ii}\bar{S}_{ij}$ (123e)

generates ${\sf L}_{\mathrm{1d}}^{0}$.

In words, (123b) generates the zero energy spin configurations that start and
end in the same state (called $i$). (123c) generates the zero energy spin
configurations that start and end in a different state ($i$ and $j$). So
$S_{ii}$ stands for any zero energy spin configuration that starts and ends in
$i$, and $S_{ij}$ stands for any zero energy spin configuration that starts in
$i$ and ends in $j$. $\bar{S}_{ii}$ stands for any zero energy spin
configuration that starts and ends in $i$ but is ‘missing an $i$ on the left’,
and similarly for $\bar{S}_{ij}$.

###### Proof.

We start by proving that ${\sf L}(G_{\mathrm{1d}}^{0})\subseteq{\sf
L}_{\mathrm{1d}}^{0}$ by induction over the derivation length. First, note
that any spin configuration that can be derived from $S_{ij}$ starts with $i$
and ends with $j$. The only derivations of length $2$ are

$\displaystyle\begin{aligned} S_{\mathrm{1d}}^{0}\rightarrow S_{01}\rightarrow
001\ |\ 011\\\ S_{\mathrm{1d}}^{0}\rightarrow S_{10}\rightarrow 100\ |\
110\end{aligned}$ (124)

All these configurations have energy $0$. Now consider an arbitrary
configuration of length $n$. We only show explicitly the case where the
derivation starts with $S_{\mathrm{1d}}^{0}\rightarrow S_{ii}$, as the other
case works in exactly the same way. There are two cases of how the derivation
can continue. In the first case the derivation is of the form

$\displaystyle S_{\mathrm{1d}}^{0}\rightarrow S_{ii}\rightarrow iS_{ji}i\ |\
iS_{ij}i$ (125)

Then the induction hypothesis applies to the remaining productions that
transform $S_{ji}$ or $S_{ij}$ into terminal symbols. Thus, $S_{ji}$ will be
transformed into a spin configuration of energy $0$ that starts with $j$ and
ends with $i$, while $S_{ij}$ will be transformed into a spin configuration of
energy $0$ that starts with $i$ and ends with $j$. Since $i\neq j$, in either
case, the first and last contributions to the energy of $iS_{ji}i\ |\
iS_{ij}i$ cancel. Hence, also the derivation of length $n+1$ yields a final
configuration with energy $0$. In the second case the derivation is of the
form

$\displaystyle S_{\mathrm{1d}}^{0}\rightarrow S_{ii}\rightarrow
S_{ii}\bar{S}_{ii}\ |\ S_{ij}\bar{S}_{ji}$ (126)

Note that a configuration $s_{1}\ldots s_{k}$ can be derived from
$\bar{S}_{ij}$ if and only if $is_{1}\ldots s_{k}$ can be derived from
$S_{ij}$, as can readily be seen from comparing the production rules (123e)
and (123c). Thus the induction hypothesis applies not only to the productions
that follow for $S_{ii}\ |\ S_{ij}$ but also to those that follow for
$\bar{S}_{ii}\ |\ \bar{S}_{ji}$ once the missing $i\ |\ j$ is appended. This
case corresponds to two zero energy configurations that are glued together,
overlapping in a single spin symbol. Therefore also this case yields a
configuration with zero energy.

In order to prove ${\sf L}_{\mathrm{1d}}^{0}\subseteq{\sf
L}(G_{\mathrm{1d}}^{0})$ we proceed by induction over the word length, i.e.
the length of the spin configuration. ${\sf L}_{\mathrm{1d}}^{0}$ contains
exactly four configurations of length three, namely $001,011,100,110$, which
can all be derived from $S_{\mathrm{1d}}^{0}$. Consider now an arbitrary
configuration of $n$ spins, $s=s_{1}\ldots s_{n}\in{\sf L}_{\mathrm{1d}}^{0}$.
There are now only two cases. The first one is

$\displaystyle h(s_{1},s_{2})+h(s_{n-1},s_{n})=0$ (127)