# Jumping Automata Must Pay

Shaull Almagor Technion, IsraelThis research was supported by the ISRAEL
SCIENCE FOUNDATION (grant No. 989/22). We also thank Michaël Cadilhac for
fruitful discussions about this submission<EMAIL_ADDRESS>Technion,
Israel Ishai Salgado Technion, Israel<EMAIL_ADDRESS>
###### Abstract

Jumping automata are finite automata that read their input in a non-sequential
manner, by allowing a reading head to “jump” between positions on the input,
consuming a permutation of the input word. We argue that allowing the head to
jump should incur some cost. To this end, we propose three quantitative
semantics for jumping automata, whereby the jumps of the head in an accepting
run define the cost of the run. The three semantics correspond to different
interpretations of jumps: the _absolute distance_ semantics counts the
distance the head jumps, the _reversal_ semantics counts the number of times
the head changes direction, and the _Hamming distance_ measures the number of
letter-swaps the run makes.

We study these measures, with the main focus being the _boundedness problem_ :
given a jumping automaton, decide whether its (quantitative) languages is
bounded by some given number $k$. We establish the decidability and complexity
for this problem under several variants.

##  1 Introduction

Traditional automata read their input sequentially. Indeed, this is the case
for most state-based computational models. In some settings, however, we wish
to abstract away the order of the input letters. For example, when the input
represents available resources, and we only wish to reason about their
_quantity_. From a more language-theoretic perspective, this amounts to
looking at the _commutative closure_ of languages, a.k.a. their _Parikh
image_. To capture this notion in a computation model, _Jumping Automata (
JFAs)_ were introduced in [20]. A jumping automaton may read its input in a
non-sequential manner, jumping from letter to letter, as long as every letter
is read exactly once. Several works have studied the algorithmic properties
and expressive power of these automata [12, 13, 22, 11, 18, 5].

While JFAs are an attractive and simple model, they present a shortcoming when
thought of as model for systems, namely that the abstraction of the order may
be too coarse. More precisely, the movement of the head can be thought of as a
physical process of accessing the input storage of the JFA. Then, sequential
access is the most basic form of access and can be considered “cheap”, but
allowing the head to jump around is physically more difficult and therefore
should incur a cost.

To address this, we present three _quantitative semantics_ for JFAs, whereby a
JFA represents a function from words to costs, which captures how expensive it
is to accept a given word with respect to the head jumps. The different
semantics capture different aspects of the cost of jumps, as follows.

Consider a JFA $\mathcal{A}$ and a word $w$, and let $\rho$ be an accepting
run of $\mathcal{A}$ on $w$. The run $\rho$ specifies the sequence of states
and indices visited in $w$. We first define the cost of individual runs.

  * •

In the _Absolute Distance_ semantics (abs), the cost of $\rho$ is the sum of
the lengths of jumps it makes.

  * •

In the _Reversal_ semantics (rev), the cost of $\rho$ is the number of times
the reading head changes its direction (i.e., moving from right to left or
from left to right).

  * •

In the _Hamming_ semantics (ham), we consider the word $w^{\prime}$ induced by
$\rho$, i.e., the order of letters that $\rho$ reads. Then, the cost of $\rho$
is the number of letters where $w^{\prime}$ differs from $w$.

We then define the cost of the word $w$ in $\mathcal{A}$ according to each
semantics, by taking the run that minimizes the cost.

Thus, we lift JFAs from a Boolean automata model to the rich setting of
_quantitative_ models [6, 4, 9, 10]. Unlike other quantitative automata,
however, the semantics in this setting arise naturally from the model, without
an external domain. Moreover, the definitions are naturally motivated by
different types of memory access, as we now demonstrate. First, consider a
system whose memory is laid out in an array (i.e., a tape), with a reading
head that can move along the tape. Moving the head requires some energy, and
therefore the total energy spent reading the input corresponds to the abs
semantics. Next, consider a system whose memory is a spinning disk (or a
sliding tape), so that the head stays in place and the movement is of the
memory medium. Then, it is cheap to continue spinning in the same
direction111We assume that the head does not return back to the start by
continuing the spin, but rather reaches some end., and the main cost is in
reversing the direction, which requires stopping and reversing a motor. Then,
the rev semantics best captures the cost. Finally, consider a system that
reads its input sequentially, but is allowed to edit its input by replacing
one letter with another, such that at the end the obtained word is a
permutation of the original word. This is akin to _edit-distance automata_
[21, 14] under a restriction of maintaining the amount of resources. Then, the
minimal edits required correspond to the ham semantics.

######  Example 1.

Consider a (standard) NFA $\mathcal{A}$ for the language given by the regular
expression $(ab)^{*}$ (the concrete automaton chosen is irrelevant, see Remark
6). As a JFA, $\mathcal{A}$ accepts a word $w$ if and only if $w$ has an equal
number of $a$’s and $b$’s. To illustrate the different semantics, consider the
words $w_{1}=ababbaab$ and $w_{2}=ababbaba$, obtained from $(ab)^{4}$ by
flipping the third $ab$ pair ($w_{1}$) and the third and fourth pairs
($w_{2}$). As we define in Section 3, we think of runs of the JFA
$\mathcal{A}$ as if the input is given between end markers at indices $0$ and
$n+1$, and the jumping run must start at $0$ and end in $n+1$.

  * •

In the abs semantics, the cost of $w_{1}$, denoted
$\mathcal{A}_{\textsc{abs}}(w_{1})$, is $2$: the indices read by the head are
$0,1,2,3,4,6,5,7,8,9$, so there are two jumps of cost $1$: from $4$ to $6$ and
from $5$ to $7$. Similarly, we have $\mathcal{A}_{\textsc{abs}}(w_{2})=4$,
e.g., by the sequence $0,1,2,3,4,6,5,8,7,9$, which has two jumps of cost $1$
($4$ to $6$ and $7$ to $9$), and one jump of cost $2$ ($5$ to $8$). (formally,
we need to prove that there is no better run, but this is not hard to see).

  * •

In the rev semantics, we have $\mathcal{A}_{\textsc{rev}}(w_{1})=2$ by the
same sequence of indices as above, as the head performs two “turns”, one at
index $6$ (from $\to$ to $\leftarrow$) and one at $5$ (from $\leftarrow$ to
$\to$). Here, however, we also have $\mathcal{A}_{\textsc{rev}}(w_{2})=2$,
using the sequence $0,1,2,3,4,6,8,7,5,9$, whose turning points are $8$ and
$5$.

  * •

In the ham semantics we have $\mathcal{A}_{\textsc{ham}}(w_{1})=2$ and
$\mathcal{A}_{\textsc{ham}}(w_{2})=4$, since we must change the letters in all
the flipped pairs for the words to be accepted.

######  Example 2.

Consider now an NFA $\mathcal{B}$ for the language given by the regular
expression $a^{*}b^{*}$. Note that as a JFA, $\mathcal{B}$ accepts
$\\{a,b\\}^{*}$, since every word can be reordered to the form $a^{*}b^{*}$.

Observe that in the rev semantics, for every word $w$ we have
$\mathcal{B}_{\textsc{rev}}(w)\leq 2$, since at the worst case $\mathcal{B}$
makes one left-to-right pass to read all the $a$’s, then a right-to-left pass
to read all the $b$’s, and then jump to the right end marker, and thus it has
two turning points. In particular, $\mathcal{B}_{\textsc{rev}}$ is bounded.

However, in the abs and ham semantics, the costs can become unbounded. Indeed,
in order to accept words of the form $b^{n}a^{n}$, in the abs semantics the
head must first jump over all the $b^{n}$, incurring a high cost, and for the
ham semantics, all the letters must be changed, again incurring a high cost.

#### Related work

Jumping automata were introduced in [20]. We remark that [20] contains some
erroneous proofs (e.g., closure under intersection and complement, also
pointed out in [13]). The works in [12, 13] establish several expressiveness
results on jumping automata, as well as some complexity results. In [22] many
additional closure properties are established. An extension of jumping
automata with a two-way tape was studied in [11], and jumping automata over
infinite words were studied by the first author in [5].

When viewed as the commutative image of a language, jumping automata are
closely related to Parikh Automata [17, 8, 7, 15], which read their input and
accept if a certain Parikh image relating to the run belongs to a given
semilinear set (indeed, we utilize the latter in our proofs). Another related
model is that of symmetric transducers – automata equipped with outputs, such
that permutations in the input correspond to permutations in the output. These
were studied in [3] in a jumping-flavour, and in [2] in a quantitative
$k$-window flavour.

More broadly, quantitative semantics have received much attention in the past
two decades, with many motivations and different flavors of technicalities. We
refer the reader to [6, 10] and the references therein.

#### Contribution and paper organization

Our contribution consists of the introduction of the three jumping semantics,
and the study of decision problems pertaining to them (defined in Section 3).
Our main focus is the boundedness problem: given a JFA $\mathcal{A}$, decide
whether the function described by it under each of the semantics bounded by
some constant $k$. We establish the decidability of this problem for all the
semantics, and consider the complexity of some fragments.

Our paper is organized as follows: the preliminaries and definitions are given
in Sections 2 and 3. Then, each of Sections 4, 5 and 6 studies one of the
semantics, and follows the same structure: we initially establish that the
membership problem for the semantics is NP-complete. Then we characterize the
set of words whose cost is at most $k$ using a construction of an NFA. These
constructions differ according to the semantics, and involve some nice tricks
with automata, but are technically not hard to understand. We note that these
constructions are preceded by crucial observations regarding the semantics,
which allow us to establish their correctness. Next, in Section 7 we give a
complete picture of the interplay between the different semantics (using some
of the results established beforehand). Finally, in Section 8 we discuss some
exciting open problems. Due to lack of space, some proofs appear in the
appendix.

##  2 Preliminaries and Definitions

For a finite alphabet $\Sigma$ we denote by $\Sigma^{*}$ the set of finite
words over $\Sigma$. For $w\in\Sigma^{*}$ we denote its letters by
$w=w_{1}\cdots w_{n}$, and its length by $|w|=n$. In the following, when
discussing sets of numbers, we define $\min\emptyset=\infty$

#### Automata

A _nondeterministic finite automaton ( NFA)_ is a 5-tuple
$\mathcal{A}=\langle\Sigma,Q,\delta,Q_{0},\alpha\rangle$ where $\Sigma$ is a
finite alphabet, $Q$ is a finite set of states, $\delta:Q\times\Sigma\to
2^{Q}$ is a nondeterministic transition function, $Q_{0}\subseteq Q$ is a set
of initial states, and $\alpha\subseteq Q$ is a set of accepting states. A
_run_ of $\mathcal{A}$ on a word $w=w_{1}w_{2}\ldots w_{n}$ is a sequence
$\rho=q_{0},q_{1},\ldots,q_{n}$ such that $q_{0}\in Q_{0}$ and for every
$0\leq i<n$ it holds that $q_{i+1}\in\delta(q_{i},w_{i+1})$. The run $\rho$ is
_accepting_ if $q_{n}\in\alpha$. A word $w$ is _accepted_ by $\mathcal{A}$ if
there exists an accepting run of $\mathcal{A}$ on $w$. The _language_ of
$\mathcal{A}$, denoted $\mathfrak{L}(\mathcal{A})$, is the set of words
accepted by $\mathcal{A}$.

#### Permutations

Let $n\in\mathbb{N}$. The _permutation group_ $S_{n}$ is the set of bijections
(i.e. _permutations_) from $\\{1,...,n\\}$ to itself. $S_{n}$ forms a group
with the function-composition operation and the identity permutation as a
neutral element. Given a word $w=w_{1}\cdots w_{n}$ and a permutation $\pi\in
S_{n}$, we define $\pi(w)=w_{\pi(1)}\cdots w_{\pi(n)}$. For example, if
$w=abcd$ and $\pi=\begin{pmatrix}1&2&3&4\\\ 3&4&2&1\end{pmatrix}$ then
$\pi(w)=cdba$. We usually denote permutations in _one-line form_ , e.g., $\pi$
is represented as $(3,4,2,1)$. We say that a word $y$ is a _permutation_ of
$x$, and we write $x\sim y$ if there exists a permutation $\pi\in S_{|x|}$
such that $\pi(x)=y$.

#### Jumping Automata

A jumping automaton is syntactically identical to an NFA, with the semantic
difference that it has a reading head that can “jump” between indices of the
input word. An equivalent view is that a jumping automaton reads a
(nondeterministically chosen) permutation of the input word.

Formally, consider an NFA $\mathcal{A}$. We view $\mathcal{A}$ as a _jumping
finite automaton_ (JFA) by defining its _jumping language_
$\mathfrak{J}(\mathcal{A})=\\{w\in\Sigma^{*}\mid\exists u\in\Sigma^{*}.\ w\sim
u\wedge u\in\mathfrak{L}(\mathcal{A})\\}$.

Since our aim is to reason about the manner with which the head of a JFA
jumps, we introduce a notion to track the head along a run. Consider a word
$w$ of length $n$ and a JFA $\mathcal{A}$. A _jump sequence_ is a vector
$\mathbf{a}=(a_{0},a_{1},a_{2},\ldots,a_{n},a_{n+1})$ where $a_{0}=0$,
$a_{n+1}=n+1$ and $(a_{1},a_{2},\ldots,a_{n})\in S_{n}$. We denote by $J_{n}$
the set of all jump sequences of size $n+2$.

Intuitively, a jump sequence $\mathbf{a}$ represents the order in which a JFA
visits a given word of length $n$. First it visits the letter at index
$a_{1}$, then the letter at index $a_{2}$ and so on. To capture this, we
define $w_{\mathbf{a}}=w_{a_{1}}w_{a_{2}}\cdots w_{a_{n}}$. Observe that jump
sequences enforce that the head starts at position 0 and ends at position
$n+1$, which can be thought of as left and right markers, as is common in
e.g., two-way automata.

An alternative view of jumping automata is via _Parikh Automata (PA)_ [17, 7].
The standard definition of PA is an automaton whose acceptance condition
includes a semilinear set over the transitions. To simplify things, and to
avoid defining unnecessary concepts (e.g., semilinear sets), for our purposes,
a PA is a pair $(\mathcal{A},\mathcal{C})$ where $\mathcal{A}$ is an NFA over
alphabet $\Sigma$, and $\mathcal{C}$ is a JFA over $\Sigma$. Then, the PA
$(\mathcal{A},\mathcal{C})$ accepts a word $w$ if
$w\in\mathfrak{L}(\mathcal{A})\cap\mathfrak{J}(\mathcal{C})$. Note that when
$\mathfrak{L}(\mathcal{A})=\Sigma^{*}$, then the PA coincides with
$\mathfrak{J}(\mathcal{C})$. Our usage of PA is to obtain the decidability of
certain problems. Specifically, from [17] we have that emptiness of PA is
decidable.

##  3 Quantitative Semantics for JFAs

In this section we present and demonstrate the three quantitative semantics
for JFAs. We then define the relevant decision problems, and lay down some
general outlines to solving them, which are used in later sections. For the
remainder of the section fix a JFA
$\mathcal{A}=\langle\Sigma,Q,\delta,Q_{0},\alpha\rangle$.

###  3.1 The Semantics

#### The Absolute-Distance Semantics

In the absolute-distance semantics, the cost of a run (given as a jump
sequence) is the sum of the sizes of the jumps made by the head. Since we want
to think of a sequential run as a run with 0 jumps, we measure a jump over $k$
letters as distance $k-1$ (either to the left or to the right). This is
captured as follows.

For $k\in\mathbb{Z}$, define $\llbracket k\rrbracket=|k|-1$. Consider a word
$w\in\Sigma^{*}$ with $|w|=n$, and let
$\mathbf{a}=(a_{0},a_{1},a_{2},\ldots,a_{n},a_{n+1})$ be a jump sequence, then
we lift the notation above and write
$\llbracket\mathbf{a}\rrbracket=\sum_{i=1}^{n+1}\llbracket
a_{i}-a_{i-1}\rrbracket$.

######  Definition 3 (Absolute-Distance Semantics).

For a word $w\in\Sigma^{*}$ with $|w|=n$ we define

$\mathcal{A}_{\textsc{abs}}(w)=\min\\{\llbracket\mathbf{a}\rrbracket\mid\mathbf{a}\text{
is a jump sequence, and }w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{A})\\}$

(recall that $\min\emptyset=\infty$ by definition).

#### The Reversal Semantics

In the reversal semantics, the cost of a run is the number of times the head
changes direction in the corresponding jump sequence. Consider a word
$w\in\Sigma^{*}$ with $|w|=n$, and let
$\mathbf{a}=(a_{0},a_{1},a_{2},\ldots,a_{n},a_{n+1})$ be a jump sequence, we
define

$\\#_{\textsc{rev}}(\mathbf{a})=|\\{i\in\\{1,\ldots,n\\}\mid(a_{i}>a_{i-1}\wedge
a_{i}>a_{i+1})\vee(a_{i}<a_{i-1}\wedge a_{i}<a_{i+1})\\}|$

######  Definition 4 (Reversal Semantics).

For a word $w\in\Sigma^{*}$ with $|w|=n$ we define

$\mathcal{A}_{\textsc{rev}}(w)=\min\\{\\#_{\textsc{rev}}(\mathbf{a})\mid\mathbf{a}\text{
is a jump sequence, and }w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{A})\\}$

#### The Hamming Semantics

In the Hamming measure, the cost of a word is the minimal number of
coordinates of $w$ that need to be changed in order for the obtained word to
be accepted by $\mathcal{A}$ (sequentially, as an NFA), so that the changed
word is a permutation of $w$.

Consider two words $x,y\in\Sigma^{*}$ with $|x|=|y|=n$ such that $x\sim y$, we
define the _Hamming Distance_ between $x$ and $y$ as $d_{H}(x,y)=|\\{i\mid
x_{i}\neq y_{i}\\}|$.

######  Definition 5 (Hamming Semantics).

For a word $w\in\Sigma^{*}$ we define

$\mathcal{A}_{\textsc{ham}}(w)=\min\\{d_{H}(w^{\prime},w)\mid w^{\prime}\in
L(\mathcal{A}),w^{\prime}\sim w\\}$

######  Remark 6.

Note that the definitions of the three semantics are independent of the NFA,
and only refer to its language. We can therefore refer to the cost of a word
in a language according to each semantics, rather than the cost of a word in a
concrete automaton.

###  3.2 Quantitative Decision Problems

In the remainder of the paper we focus on quantitative variants of the
standard Boolean decision problems pertaining to the jumping semantics.
Specifically, we consider the following problems for each semantics
$\textsc{sem}\in\\{\textsc{abs},\textsc{ham},\textsc{rev}\\}$.

  * •

Membership: Given a JFA $\mathcal{A}$, $k\in\mathbb{N}$ and a word $w$, decide
whether $\mathcal{A}_{\textsc{sem}}(w)\leq k$.

  * •

$k$-Boundedness (for a fixed $k$): Given a JFA $\mathcal{A}$, decide whether
$\forall w\in\mathfrak{J}(\mathcal{A})\ \mathcal{A}_{\textsc{sem}}(w)\leq k$.

  * •

Param-Boundedness: Given a JFA $\mathcal{A}$ and $k\in\mathbb{N}$, decide
whether $\forall w\in\mathfrak{J}(\mathcal{A})\
\mathcal{A}_{\textsc{sem}}(w)\leq k$.

We also pay special attention to the setting where
$\mathfrak{J}(\mathcal{A})=\Sigma^{*}$, in which case we refer to these
problems as Univ-$k$-Boundedness and Univ-Param-Boundedness. For example, in
Univ-Param-Boundedness we are given a JFA $\mathcal{A}$ and $k\in\mathbb{N}$
and the problem is to decide whether $\mathcal{A}_{\textsc{sem}}(w)\leq k$ for
all words $w\in\Sigma^{*}$.

The boundedness problems can be thought of as quantitative variants of Boolean
universality (i.e., is the language equal to $\Sigma^{*}$). Observe that the
problems above are not fully specified, as the encoding of $k$ (binary or
unary) when it is part of the input may effect the complexity. We remark on
this when it is relevant. Note that the emptiness problem is absent from the
list above. Indeed, a natural quantitative variant would be: is there a word
$w$ such that $\mathcal{A}_{\textsc{sem}}(w)\leq k$. This, however, is
identical to Boolean emptiness, since $\mathfrak{L}(\mathcal{A})\neq\emptyset$
if and only if there exists $w$ such that $\mathcal{A}_{\textsc{sem}}(w)=0$.
We therefore do not consider this problem. Another problem to consider is
boundedness when $k$ is existentially quantified. We elaborate on this problem
in Section 8.

##  4 The Absolute-Distance Semantics

The first semantics we investigate is abs, and we start by showing that (the
decision version of) computing its value for a given word is NP-complete. This
is based on bounding the distance with which a word can be accepted.

######  Lemma 7.

Consider a JFA $\mathcal{A}$ and $w\in\mathfrak{J}(\mathcal{A})$ with $|w|=n$,
then $\mathcal{A}_{\textsc{abs}}(w)<n^{2}$.

###### Proof.

Since $w\in\mathfrak{J}(\mathcal{A})$, there exists a jump sequence
$\mathbf{a}=(a_{0},a_{1},a_{2},\ldots,a_{n},a_{n+1})$ such that
$w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{A})$. Therefore,
$\mathcal{A}_{\textsc{abs}}(w)\leq\llbracket\mathbf{a}\rrbracket$. Observe
that $|a_{i}-a_{i-1}|\leq{n}$ for all $i\in\\{1,\ldots,n+1\\}$, since there is
no jump from $0$ to $n+1$ (since $a_{0}=0$ and $a_{n}=n+1$). The following
concludes the proof:

$\llbracket\mathbf{a}\rrbracket=\sum_{i=1}^{n+1}\llbracket
a_{i}-a_{i-1}\rrbracket=\sum_{i=1}^{n+1}|a_{i}-a_{i-1}|-1\leq\sum_{i=1}^{n+1}n-1=(n+1)(n-1)<n^{2}$

∎

We can now prove the complexity bound for computing the absolute distance, as
follows.

######  Theorem 8 (Absolute-Distance Membership is NP-complete).

The problem of deciding, given $\mathcal{A},w$ and $k\in\mathbb{N}$, whether
$\mathcal{A}_{\textsc{abs}}(w)\leq k$, is NP-complete.

###### Proof.

In order to establish membership in NP, note that by Lemma 7, we can assume
$k\leq n^{2}$, as otherwise we can set $k=n^{2}$. Then, it is sufficient to
nondeterministically guess a jump sequence $\mathbf{a}$ and to check that
$w_{a_{1}}\cdots w_{a_{n}}\in\mathfrak{L}(\mathcal{A})$ and that
$\llbracket\mathbf{a}\rrbracket\leq k$. Both conditions are easily checked in
polynomial time, since $k$ is polynomially bounded.

Hardness in NP follows by reduction from (Boolean) membership in JFA: it is
shown in [13] that deciding whether $w\in\mathfrak{J}(\mathcal{A})$ is NP-
hard. We reduce this problem by outputting, given $\mathcal{A}$ and $w$, the
same $\mathcal{A}$ and $w$ with the bound $k=n^{2}$. The reduction is correct
by Lemma 7 and the fact that if $w\notin\mathfrak{J}(\mathcal{A})$ then
$\mathcal{A}_{\textsc{abs}}(w)=\infty$. ∎

###  4.1 Decidability of Boundedness Problems for abs

We now turn our attention to the boundedness problems. Consider a JFA
$\mathcal{A}$ and $k\in\mathbb{N}$. Intuitively, our approach is to construct
an NFA $\mathcal{B}$ that simulates, while reading a word $w\in\Sigma^{*}$,
every jump sequence of $\mathcal{A}$ on $w$ whose absolute distance is at most
$k$. The crux of the proof is to show that we can indeed bound the size of
$\mathcal{B}$ as a function of $k$. At a glance, the main idea here is to
claim that since the absolute distance is bounded by $k$, then $\mathcal{A}$
cannot make large jumps, nor many small jumps. Then, if we track a sequential
head going from left to right, then the jumping head must always be within a
bounded distance from it. We now turn to the formal arguments. Fix a JFA
$\mathcal{A}=\langle\Sigma,Q,\delta,Q_{0},\alpha\rangle$.

To understand the next lemma, imagine $\mathcal{A}$’s jumping head while
taking the $j^{th}$ step in a run on $w$ according to a jump sequence
$\mathbf{a}=(a_{0},a_{1},a_{2},\ldots,a_{n},a_{n+1})$. Thus, the jumping head
points to the letter at index $a_{j}$. Concurrently, imagine a “sequential”
head (reading from left to right), which points to the $j^{th}$ letter in $w$.
Note that these two heads start and finish reading the word at the same
indices $a_{0}=0$ and $a_{n+1}=n+1$. It stands to reason that if at any step
while reading $w$ the distance between these two heads is large, the cost of
reading $w$ according to $\mathbf{a}$ would also be large, as there would need
to be jumps that bridge the gaps between the heads. The following lemma
formalizes this idea.

######  Lemma 9.

Consider a jump sequence
$\mathbf{a}=(a_{0},a_{1},a_{2},\ldots,a_{n},a_{n+1})$. For every $1\leq j\leq
n$ it holds that $\llbracket\mathbf{a}\rrbracket\geq|a_{j}-j|$.

###### Proof.

Let $1\leq j\leq n+1$. First, assume that $a_{j}\geq j$ and consider the sum
$\sum_{i=1}^{j}\llbracket
a_{i}-a_{i-1}\rrbracket\leq\llbracket\mathbf{a}\rrbracket$. From the
definition of $\llbracket\cdot\rrbracket$ we have $\sum_{i=1}^{j}\llbracket
a_{i}-a_{i-1}\rrbracket=\left(\sum_{i=1}^{j}|a_{i}-a_{i-1}|\right)-j$, and we
conclude that in this case $\llbracket\mathbf{a}\rrbracket\geq|a_{j}-j|$ by
the following:

$\left(\sum_{i=1}^{j}|a_{i}-a_{i-1}|\right)-j\underset{\mathclap{\begin{subarray}{c}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\big{\downarrow}\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{triangle
inequality}}\end{subarray}}}{\geq}\left|\sum_{i=1}^{j}a_{i}-a_{i-1}\right|-j\underset{\mathclap{\begin{subarray}{c}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\big{\downarrow}\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{telescopic
sum}}\end{subarray}}}{=}|a_{j}-a_{0}|-j\underset{\mathclap{\begin{subarray}{c}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\big{\downarrow}\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a_{0}=0}\end{subarray}}}{=}a_{j}-j\underset{\mathclap{\begin{subarray}{c}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\big{\downarrow}\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a_{j}\geq
j}\end{subarray}}}{=}|a_{j}-j|$

The direction $a_{j}<j$ is proved by looking at the sum of the _last_ $j$
elements (see in Section A.1). ∎

From Lemma 9 we get that in order for a word $w$ to attain a small cost, it
must be accepted with a jumping sequence that stays close to the sequential
head. More precisely:

######  Corollary 10.

Let $k\in\mathbb{N}$ and consider a word $w$ such that
$\mathcal{A}_{\textsc{abs}}(w)\leq k$, then there exists a jumping sequence
$\mathbf{a}=(a_{0},a_{1},a_{2},\ldots,a_{n},a_{n+1})$ such that
$w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{A})$ and for all $1\leq j\leq n$ we
have $|a_{j}-j|\leq k$.

We now turn to the construction of an NFA that recognizes the words whose cost
is at most $k$.

######  Lemma 11.

Let $k\in\mathbb{N}$. We can effectively construct an NFA $\mathcal{B}$ such
that
$\mathfrak{L}(\mathcal{B})\\!=\\!\\{w\in\Sigma^{*}|\mathcal{A}_{\textsc{abs}}(w)\leq
k\\}$.

###### Proof.

Let $k\in\mathbb{N}$. Intuitively, $\mathcal{B}$ works as follows: it
remembers in its states a window of size $2k+1$ centered around the current
letter (recall that as an NFA, it reads its input sequentially). The window is
constructed by nondeterministically guessing (and then verifying) the next $k$
letters, and remembering the last $k$ letters.

$\mathcal{B}$ then nondeterministically simulates a jumping sequence of
$\mathcal{A}$ on the given word, with the property that the jumping head stays
within distance $k$ from the sequential head. This is done by marking for each
letter in the window whether it has already been read in the jumping sequence,
and nondeterministically guessing the next letter to read, while keeping track
of the current jumping head location, as well as the total cost incurred so
far. After reading a letter, the window is shifted by one to the right. If at
any point the window is shifted so that a letter that has not been read by the
jumping head shifts out of the $2k+1$ scope, the run rejects. Similarly, if
the word ends but the guessed run tried to read a letter beyond the length of
the word, the run rejects. The correctness of the construction follows from
Corollary 10. We now turn to the formal details. Recall that
$\mathcal{A}=\langle\Sigma,Q,\delta,Q_{0},\alpha\rangle$. We define
$\mathcal{B}=\langle\Sigma,Q^{\prime},\delta^{\prime},Q_{0}^{\prime},\beta\rangle$
as follows.

The state space of $\mathcal{B}$ is
$Q^{\prime}=Q\times(\Sigma\times\\{?,\checkmark\\})^{-k,\ldots,k}\times\\{-k,\ldots,k\\}\times\\{0,\ldots,k\\}$.
We denote a state of $\mathcal{B}$ as $(q,f,j,c)$ where $q\in Q$ is a state of
$\mathcal{A}$, $f:\\{-k,\ldots,k\\}\to\Sigma\times\\{?,\checkmark\\}$
represents a window of size $2k+1$ around the sequential head, where
$\checkmark$ marks letters that have already been read by $\mathcal{A}$ (and
$?$ marks the others), $j$ represents the index of the head of $\mathcal{A}$
relative to the sequential head, and $c$ represents the cost incurred thus far
in the run. We refer to the components of $f$ as $f(j)=(f(j)_{1},f(j)_{2})$
with $f(j)_{1}\in\Sigma$ and $f(j)_{2}\in\\{?,\checkmark\\}$.

The initial states of $\mathcal{B}$ are
$Q^{\prime}_{0}=\left\\{(q,f,j,j-1)\mid q\in Q_{0}\wedge
j>0\wedge(f(i)_{2}=\checkmark\iff i\leq 0)\right\\}$. That is, all states
where the state of $\mathcal{A}$ is initial, the location of the jumping head
is some $j>0$ incurring a cost of $j-1$ (i.e., the initial jump $\mathcal{A}$
makes), and the window is guessed so that everything left of the first letter
is marked as already-read (to simulate the fact that $\mathcal{A}$ cannot jump
to the left of the first letter).

The transitions of $\mathcal{B}$ are defined as follows. Consider a state
$(q,f,j,c)$ and a letter $\sigma\in\Sigma$, then
$(q^{\prime},f^{\prime},j^{\prime},c^{\prime})\in\delta^{\prime}((q,f,j,c),\sigma)$
if and only if the following hold (see Fig. 1 for an illustration):

  * •

$f(1)_{1}=\sigma$. That is, we verify that the next letter in the guessed
window is indeed correct.

  * •

$f(-k)_{2}=\checkmark$. That is, the leftmost letter has been read. Otherwise
by Corollary 10 the cost of continuing the run must be greater than $k$.

  * •

$f(j)_{2}\neq\checkmark$ and $f^{\prime}(j-1)=\checkmark$ (if $j>-k$). That
is, the current letter has not been previously read, and will be read from now
on (note that index $j$ before the transition corresponds to index $j-1$
after).

  * •

$q^{\prime}=\delta(q,f(j)_{1})$, i.e. the state of $\mathcal{A}$ is updated
according to the current letter.

  * •

$c^{\prime}=c+|j^{\prime}+1-j|-1$, since $j^{\prime}$ represents the index in
the shifted window, so in the “pre-shifted” tape this is actually index $j+1$.
We demonstrate this in Fig. 1. Also, $c^{\prime}\leq k$ by the definition of
$Q$.

  * •

$f^{\prime}(i)=f(i+1)$ for $i<k$. That is, the window is shifted and the index
$f^{\prime}(k)$ is nondeterministically guessed222The guess could potentially
be $\checkmark$, but this is clearly useless..

$\alpha\checkmark$$\beta?$$\gamma\checkmark$$\epsilon?$$\mu\checkmark$$\eta?$$\xi?$$\zeta\checkmark$$\theta?$$-4$$-3$$-2$$-1$$0$$1$$2$$3$$4$$\implies$

$\beta\checkmark$$\gamma\checkmark$$\epsilon?$$\mu\checkmark$$\eta?$$\xi?$$\zeta\checkmark$$\theta?$$\psi?$$-4$$-3$$-2$$-1$$0$$1$$2$$3$$4$

Figure 1: A single transition in the construction of Lemma 11. The dashed
arrow signifies the sequential head, the full arrow is the “imaginary” jumping
head. Here, the head jumps from $-3$ to $2$, incurring a cost of $4$, but in
the indexing after the transition $\xi$ is at index $1$, thus the expression
given for $c^{\prime}$ in the construction. Note that the letter being read
must be $\mu$, and that $\alpha$ must be checked, otherwise the run has
failed.

Finally, the accepting states of $\mathcal{B}$ are $\beta=\\{(q,f,1,c)\mid
q\in\alpha\wedge f(j)_{2}=?\text{ for all }j>0\\}$. That is, the state of
$\mathcal{A}$ is accepting, the overall cost is at most $k$, the location of
the jumping head matches the sequential head (intuitively, location $n+1$),
and no letter beyond the end of the tape has been used.

It is easy to verify that $\mathcal{B}$ indeed guesses a jump sequence and a
corresponding run of $\mathcal{A}$ on the given word, provided that the
jumping head stays within distance $k$ of the sequential head. By Corollary
10, this restriction is complete, in the sense that if
$\mathcal{A}_{\textsc{abs}}(w)\leq k$ then there is a suitable jump sequence
under this restriction with which $w$ is accepted. ∎

We can now readily conclude the decidability of the boundedness problems for
the abs semantics. The proof (in Section A.2) makes use of the decidability of
emptiness for Parikh Automata [17].

######  Theorem 12.

The following problems are decidable for the abs semantics: $k$-Boundedness,
Param-Boundedness, Univ-$k$-Boundedness and Univ-Param-Boundedness.

With further scrutiny, we see that the size of $\mathcal{B}$ constructed as
per Lemma 11 is polynomial in the size of $\mathcal{A}$ and single-exponential
in $k$. Thus, Univ-$k$-Boundedness is in fact decidable in PSPACE, whereas
Univ-Param-Boundedness is in EXPSPACE and 2-EXPSPACE for $k$ given in unary
and binary, respectively. For the non-universal problems we do not supply
upper complexity bounds, as these depend on the decidability for PA
containment, for which we only derive decidability from [17].

###  4.2 PSPACE-Hardness of Boundedness for abs

In the following, we complement the decidability result of Theorem 12 by
showing that already Univ-$k$-Boundedness is PSPACE-hard, for every
$k\in\mathbb{N}$.

We first observe that the absolute distance of every word is even. In fact,
this is true for every jumping sequence.

######  Lemma 13.

Consider a jumping sequence $\mathbf{a}=(a_{0},a_{1},\ldots,a_{n},a_{n+1})$,
then $\llbracket\mathbf{a}\rrbracket$ is even.

###### Proof.

Observe that the parity of $|a_{i}-a_{i-1}|$ is the same as that of
$a_{i}-a_{i-1}$. It follows that the parity of
$\llbracket\mathbf{a}\rrbracket=\sum_{i=1}^{n+1}\llbracket
a_{i}-a_{i-1}\rrbracket=\sum_{i=1}^{n+1}|a_{i}-a_{i-1}|-1$ is the same as that
of

$\sum_{i=1}^{n+1}(a_{i}-a_{i-1}-1)=\left(\sum_{i=1}^{n+1}a_{i}-a_{i-1}\right)-(n+1)=n+1-(n+1)=0$

and is therefore even (the penultimate equality is due to the telescopic sum).
∎

We say that $\mathcal{A}_{\textsc{abs}}$ is _$k$ -bounded_ if
$\mathcal{A}_{\textsc{abs}}(w)\leq k$ for all $w\in\Sigma^{*}$. We are now
ready to prove the hardness of Univ-$k$-Boundedness. Observe that for a word
$w\in\Sigma^{*}$ we have that $\mathcal{A}_{\textsc{abs}}(w)=0$ if and only if
$w\in\mathfrak{L}(\mathcal{A})$ (indeed, a cost of $0$ implies that an
accepting jump sequence is the sequential run $0,1,\ldots,|w|+1$). In
particular, we have that $\mathcal{A}_{\textsc{abs}}$ is $0$-bounded if and
only if $\mathfrak{L}(\mathcal{A})=\Sigma^{*}$. Since the universality problem
for NFAs is PSPACE-complete, this readily proves that Univ-$0$-Boundedness is
PSPACE-hard. Note, however, that this does _not_ imply that
Univ-$k$-Boundedness is also PSPACE-hard for other values of $k$, and that the
same argument fails for $k>0$. We therefore need a slightly more elaborate
reduction.

######  Lemma 14.

For abs the Univ-$k$-Boundedness and $k$-Boundedness problems are PSPACE-hard
for every $k\in\mathbb{N}$.

###### Proof.

We sketch the proof for Univ-$k$-Boundedness. The case of $k$-Boundedness
requires slightly more effort and is delegated to Section A.3. By Lemma 13, we
can assume without loss of generality that $k$ is even. Indeed, if there
exists $m\in\mathbb{N}$ such that $\mathcal{A}_{\textsc{abs}}(w)\leq 2m+1$ for
every $w\in\Sigma^{*}$, then by Lemma 13 we also have
$\mathcal{A}_{\textsc{abs}}(w)\leq 2m$. Therefore, we assume $k=2m$ for some
$m\in\mathbb{N}$.

We reduce the universality problem for NFAs to the Univ-$2m$-Boundedness
problem. Consider an NFA $\mathcal{A}=\langle
Q,\Sigma,\delta,Q_{0},\alpha\rangle$, and let $\heartsuit\notin\Sigma$ be a
fresh symbol. Intuitively, we obtain from $\mathcal{A}$ an NFA $\mathcal{B}$
over the alphabet $\Sigma\cup\\{\heartsuit\\}$ such that
$w\in\mathfrak{L}(\mathcal{B})$ if and only if the following hold:

  1. 1.

Either $w$ does not contain exactly $m$ occurrences of $\heartsuit$, or

  2. 2.

$w$ contains exactly $m$ occurrences of $\heartsuit$, but does not start with
$\heartsuit$, and $w|_{\Sigma}\in\mathfrak{L}(\mathcal{A})$ (where
$w|_{\Sigma}$ is obtained from $w$ by removing all occurrences of
$\heartsuit$).

We then have the following: if $\mathfrak{L}(\mathcal{A})=\Sigma^{*}$, then
for every $w\in(\Sigma\cup\\{\heartsuit\\})^{*}$ if
$w\in\mathfrak{L}(\mathcal{B})$ then $\mathcal{B}_{\textsc{abs}}(w)=0\leq 2m$,
and if $w\notin\mathfrak{L}(\mathcal{B})$ then $w$ starts with $\heartsuit$
but has exactly $m$ occurrences of $\heartsuit$. Thus, jumping to the first
occurrence of a letter in $\Sigma$ incurs a cost of at most $m$, and reading
the skipped $\heartsuit$ symbols raises the cost to at most $2m$. From there,
$w$ can be read consecutively and be accepted since
$w|_{\Sigma}\in\mathfrak{L}(\mathcal{A})$. So again
$\mathcal{B}_{\textsc{abs}}(w)\leq 2m$, and $\mathcal{B}$ is $2m$-bounded.

Conversely, if $\mathfrak{L}(\mathcal{A})\neq\Sigma^{*}$, take
$x\notin\mathfrak{L}(\mathcal{A})$ such that $x\neq\epsilon$ (see Section A.3
for details regarding this assumption), and consider the word
$w=\heartsuit^{m}x$. We then have $w\notin\mathfrak{L}(\mathcal{B})$, and
moreover – in order to accept $w$ (if at all possible), $\mathcal{B}$ first
needs to jump over the initial $\heartsuit^{m}$, guaranteeing a cost of at
least $2m$ ($m$ for the jump and another $m$ to later read the
$\heartsuit^{m}$ prefix), and needs at least one more jump to accept $x$,
since $x\notin\mathfrak{L}(\mathcal{A})$. Thus,
$\mathcal{B}_{\textsc{abs}}(w)>2m$, so $\mathcal{B}$ is not $2m$-bounded. The
precise construction and correctness are given in Section A.3. ∎

Lemma 14 shows hardness for fixed $k$, and in particular when $k$ is part of
the input. Thus, Univ-Param-Boundedness and Param-Boundedness are also PSPACE-
hard, and Univ-$k$-Boundedness is PSPACE-complete.

##  5 The Reversal Semantics

We now study the reversal semantics. Recall from Definition 4 that for a JFA
$\mathcal{A}$ and a word $w$, the cost $\mathcal{A}_{\textsc{rev}}(w)$ is the
minimal number of times the jumping head changes “direction” in a jump
sequence for which $w$ is accepted.

Consider a word $w$ with $|w|=n$ and a jump sequence
$\mathbf{a}=(a_{0},a_{1},a_{2},\ldots,a_{n},a_{n+1})$. We say that an index
$1\leq i\leq n$ is a _turning index_ if $a_{i}>a_{i-1}$ and $a_{i}>a_{i+1}$
(i.e., a right-to-left turn) or if $a_{i}<a_{i-1}$ and $a_{i}<a_{i+1}$ (i.e.,
a left-to-right turn). We denote by $\mathtt{Turn}(\mathbf{a})$ the set of
turning indices of $\mathbf{a}$.

For example, consider the jump sequence
$(\overset{a_{0}}{0},\overset{a_{1}}{2},\overset{a_{2}}{3},\overset{a_{3}}{5},\overset{a_{4}}{7},\overset{a_{5}}{4},\overset{a_{6}}{1},\overset{a_{7}}{6},\overset{a_{8}}{8})$,
then $\mathtt{Turn}(\mathbf{a})=\\{4,6\\}$. Note that the cost of $w$ is then
$\mathcal{A}_{\textsc{rev}}(w)=\min\\{|\mathtt{Turn}(\mathbf{a})|\mid
w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{A})\\}$. Viewed in this manner, we have
that $\mathcal{A}_{\textsc{rev}}(w)\leq|w|$, and computing
$\mathtt{Turn}(\mathbf{a})$ can be done in polynomial time. Thus, analogously
to Theorem 8 we have the following.

######  Theorem 15 (Reversal Membership is NP-complete).

The problem of deciding, given $\mathcal{A}$ and $k$, whether
$\mathcal{A}_{\textsc{rev}}(w)\leq k$ is NP-complete.

######  Remark 16.

For every jump sequence $\mathbf{a}$ we have that
$|\mathtt{Turn}(\mathbf{a})|$ is even, since the head starts at position $0$
and ends at $n+1$, where after an odd number of turning points the direction
is right-to-left, and hence cannot reach $n+1$.

###  5.1 Decidability of Boundedness Problems for rev

We begin by characterizing the words accepted using at most $k$ reversals as a
shuffle of subwords and reversed-subwords, as follows. Let $x,y\in\Sigma^{*}$
be words, we define their _shuffle_ to be the set of words obtained by
interleaving parts of $x$ and parts of $y$. Formally:

$x\shuffle y=\\{s_{1}\cdot t_{1}\cdot s_{2}\cdot t_{2}\cdots s_{k}\cdot
t_{k}\mid\forall i\ s_{i},t_{i}\in\Sigma^{*}\wedge x=s_{1}\cdots s_{k}\wedge
y=t_{1}\cdots t_{k}\\}$

For example, if
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}x=aab$ and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}y=cd$ then
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}x}\shuffle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}y}$
contains the words
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}aab}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}cd}$,
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}ab}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}d}$,
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}aa}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}d}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}b}$,
among others (the colors reflect which word each subword originated from).
Note that the subwords may be empty, e.g.,
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}aa}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}d}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}b}$
can be seen as starting with
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\epsilon$ as
a subword of
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}x$. It is
easy to see that $\shuffle$ is an associative operation, so it can be extended
to any finite number of words.

The following lemma states that, intuitively, if
$\mathcal{A}_{\textsc{rev}}(w)\leq k$, then $w$ can be decomposed to a shuffle
of at most $k+1$ subwords of itself, where all the even ones are reversed
(representing the left-reading subwords). See Section A.4 for the proof.

######  Lemma 17.

Let $k\in\mathbb{N}$. Consider an NFA $\mathcal{A}$ and a word
$w\in\Sigma^{*}$. Then $\mathcal{A}_{\textsc{rev}}(w)\leq k$ if and only if
there exist words $s_{1},s_{2},\ldots,s_{k+1}\in\Sigma^{*}$ such that the
following hold.

  1. 1.

$s_{1}s_{2}\ldots s_{k+1}\in\mathfrak{L}(\mathcal{A})$.

  2. 2.

$w\in s_{1}\shuffle{s_{2}}^{R}\shuffle
s_{3}\shuffle{s_{4}}^{R}\shuffle\ldots\shuffle s_{k+1}$ (where $s_{i}^{R}$ is
the reverse of $s_{i}$).

Using the characterization in Lemma 17, we can now construct a corresponding
NFA, by intuitively guessing the shuffle decomposition and running copies of
$\mathcal{A}$ and its reverse in parallel. See Section A.5 for the proof.

######  Lemma 18.

Let $k\in\mathbb{N}$ and consider a JFA $\mathcal{A}$. We can effectively
construct an NFA $\mathcal{B}$ such that
$\mathfrak{L}(\mathcal{B})=\\{w\in\Sigma^{*}\mid\mathcal{A}_{\textsc{rev}}(w)\leq
k\\}$.

The proof of Lemma 18 shows that the size of $\mathcal{B}$ is polynomial in
the size of $\mathcal{A}$ and single-exponential in $k$, giving us PSPACE
membership for Univ-$k$-Boundedness.

###  5.2 PSPACE-Hardness of Boundedness for rev

Following a similar scheme to the Absolute Distance Semantics of Section 4,
observe that for a word $w\in\Sigma^{*}$ we have that
$\mathcal{A}_{\textsc{abs}}(w)=0$ if and only if
$w\in\mathfrak{L}(\mathcal{A})$, which implies that Univ-$0$-Boundedness is
PSPACE-hard. Yet again, the challenge is to prove hardness of
Univ-$k$-Boundedness for all values of $k$.

######  Theorem 19.

For rev, Univ-$k$-Boundedness is PSPACE-complete for every $k\in\mathbb{N}$.

###### Proof.

Membership in PSPACE follows from Lemma 18 and the discussion thereafter. For
hardness, we follow the same flow as the proof of Lemma 14, but naturally the
reduction itself is different. Specifically, we construct an NFA that must
read an expression of the form $(\heartsuit\spadesuit)^{m}$ before its input.
This allows us to shuffle the input to the form
$\spadesuit^{m}\heartsuit^{m}$, which causes many reversals (see Section A.6).
∎

As in Section 4.2, it follows that Univ-Param-Boundedness, $k$-Boundedness and
Param-Boundedness are also PSPACE-hard.

##  6 The Hamming Semantics

Recall from Definition 5 that for a JFA $\mathcal{A}$ and word $w$, the cost
$\mathcal{A}_{\textsc{ham}}(w)$ is the minimal Hamming distance between $w$
and $w^{\prime}$ where $w^{\prime}\sim w$ and
$w^{\prime}\in\mathfrak{L}(\mathcal{A})$.

######  Remark 20 (An alternative interpretation of the Hamming Semantics).

We can think of a jumping automaton as accepting a permutation $w^{\prime}$ of
the input word $w$. As such, a natural candidate for a quantitative measure is
the “distance” of the permutation used to obtain $w^{\prime}$ from the
identity (i.e. from $w$). The standard definition for such a distance is the
number of transpositions of two indices required to move from one permutation
to the other, namely the distance in the Cayley graph for the transpositions
generators of $S_{n}$. It is easy to show that in fact, the Hamming distance
coincides with this definition.

In Section A.7 we establish the complexity of computing the Hamming measure of
a given word.

######  Theorem 21 (Hamming Membership is NP-complete).

The problem of deciding, given $\mathcal{A}$ and $k\in\mathbb{N}$, whether
$\mathcal{A}_{\textsc{ham}}(w)\leq k$ is NP-complete.

Similarly to Sections 4.1 and 5.1, in order to establish the decidability of
Univ-Param-Boundedness, we start by constructing an NFA that accepts exactly
the words for which $\mathcal{A}_{\textsc{ham}}(w)\leq k$.

######  Lemma 22.

Let $k\in\mathbb{N}$. We can effectively construct an NFA $\mathcal{B}$ with
$\mathfrak{L}(\mathcal{B})=\\{w\in\Sigma^{*}\mid\mathcal{A}_{\textsc{ham}}(w)\leq
k\\}$.

###### Proof.

Let $k\in\mathbb{N}$. Intuitively, $\mathcal{B}$ works as follows: while
reading a word $w$ sequentially, it simulates the run of $\mathcal{A}$, but
allows $\mathcal{A}$ to intuitively “swap” the current letter with a
(nondeterministically chosen) different one (e.g., the current letter may be
$a$ but the run of $\mathcal{A}$ can be simulated on either $a$ or $b$). Then,
$\mathcal{B}$ keeps track of the swaps made by counting for each letter $a$
how many times it was swapped by another letter, and how many times another
letter was swapped to it. This is done by keeping a counter ranging from $-k$
to $k$, counting the difference between the number of occurrences of each
letter in the simulated word versus the actual word. We refer to this value as
the _balance_ of the letter. $\mathcal{B}$ also keeps track of the total
number of swaps. Then, a run is accepting if at the end of the simulation, the
total amount of swaps does not exceed $k$, and if all the letters end up with
$0$ balance. See Section A.8 for a detailed construction and proof. ∎

An analogous proof to Theorem 12 gives us the following.

######  Theorem 23.

The following problems are decidable for the ham semantics: $k$-Boundedness,
Param-Boundedness, Univ-$k$-Boundedness, and Univ-Param-Boundedness.

We note that the size of $\mathcal{B}$ constructed in Lemma 22 is polynomial
in $k$ and single-exponential in $|\Sigma|$, and therefore when $\Sigma$ is
fixed and $k$ is either fixed or given in unary, both Univ-Param-Boundedness
and Univ-$k$-Boundedness are in PSPACE.

For a lower bound, we remark that similarly to Section 4.2, it is not hard to
prove that Univ-$k$-Boundedness is also PSPACE-hard for every $k$, using
relatively similar tricks. However, since Univ-Param-Boundedness is already
PSPACE-complete, then Univ-$k$-Boundedness is somewhat redundant. We therefore
make do with the trivial lower bound whereby we reduce universality of NFA to
Univ-$0$-Boundedness.

######  Theorem 24.

For ham, the Univ-Param-Boundedness problem is PSPACE-complete for $k$ encoded
in unary and fixed alphabet $\Sigma$.

##  7 Interplay Between the Semantics

Having established some decidability results, we now turn our attention to the
interplay between the different semantics, in the context of boundedness. We
show that for a given JFA $\mathcal{A}$, if $\mathcal{A}_{\textsc{abs}}$ is
bounded, then so is $\mathcal{A}_{\textsc{ham}}$, and if
$\mathcal{A}_{\textsc{ham}}$ is bounded, then so is
$\mathcal{A}_{\textsc{rev}}$. We complete the picture by showing that these
are the only relationships – we give examples for the remaining cases (see
Table 1).

######  Lemma 25.

Consider a JFA $\mathcal{A}$. If $\mathcal{A}_{\textsc{ham}}$ is bounded, then
$\mathcal{A}_{\textsc{rev}}$ is bounded.

###### Proof.

Consider a word $w\in\Sigma^{*}$, we show that if
$\mathcal{A}_{\textsc{ham}}(w)\leq k$ for some $k\in\mathbb{N}$ then
$\mathcal{A}_{\textsc{rev}}(w)\leq 3k$. Assume
$\mathcal{A}_{\textsc{ham}}(w)\leq k$, then there exists a jump sequence
$\mathbf{a}=(a_{0},\ldots,a_{n+1})$ such that
$w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{A})$ and $w_{\mathbf{a}}$ differs from
$w$ in at most $k$ indices. We claim that we can assume without loss of
generality that for every index $i$ such that $w_{a_{i}}=w_{i}$ we have
$a_{i}=i$ (i.e., $i$ is a _fixed point_). Intuitively – there is no point
swapping identical letters. Indeed, assume that this is not the case, and
further assume that $\mathbf{a}$ has the minimal number of fixed-points among
such jump sequences. Thus, there exists some $j$ for which ${a_{j}}\neq j$ but
$w_{a_{j}}=w_{j}$. Let $m$ be such that $a_{m}=j$, and consider the jump
sequence $\mathbf{a^{\prime}}=(a^{\prime}_{0},\ldots,a^{\prime}_{n+1})$
obtained from $\mathbf{a}$ by composing it with the swap $(a_{j}\ a_{m})$.
Then, for every $i\notin\\{j,m\\}$ we have that $a^{\prime}_{i}=a_{i}$. In
addition, $a^{\prime}_{j}=a_{m}=j$ as well as $a^{\prime}_{m}=a_{j}$. In
particular, $\mathbf{a^{\prime}}$ has more fixed points than $a$ (exactly
those of $\mathbf{a}$ and $j$). However, we claim that
$w_{\mathbf{a}}=w_{\mathbf{a^{\prime}}}$. Indeed, the only potentially-
problematic coordinates are $a_{j}$ and $a_{m}$. For $j$ we have
$w_{a_{j}}=w_{j}=w_{a^{\prime}_{j}}$. and for $m$ we have
$w_{a^{\prime}_{m}}=w_{a_{j}}=w_{j}=w_{a_{m}}$. This is a contradiction to
$\mathbf{a}$ having a minimal number of fixed points, so we conclude that no
such coordinate $a_{j}\neq j$ exists.

Next, observe that $\mathtt{Turn}(\mathbf{a})\subseteq\\{i\mid a_{i}\neq i\vee
a_{i+1}\neq i+1\vee a_{i-1}\neq i-1\\}$. Indeed, if $a_{i-1}=i-1$, $a_{i}=i$
and $a_{i+1}=i+1$ then clearly $i$ is not a turning index. By the property
established above, we have that $w_{a_{i}}=w_{i}$, if and only if $a_{i}=i$.
It follows that $\mathtt{Turn}(\mathbf{a})\subseteq\\{i\mid w_{a_{i}}\neq
w_{i}\vee w_{a_{i+1}}\neq w_{i+1}\vee w_{a_{i-1}}\neq w_{i-1}\\}$, so
$|\mathtt{Turn}(\mathbf{a})|\leq 3k$ (since each index where
$w_{\mathbf{a}}\neq w$ is counted at most 3 times333A slightly finer analysis
shows that this is in fact at most $2k$, but we are only concerned with
boundedness. in the latter set). ∎

######  Lemma 26.

Consider a JFA $\mathcal{A}$. If $\mathcal{A}_{\textsc{abs}}$ is bounded, then
$\mathcal{A}_{\textsc{ham}}$ is bounded.

###### Proof.

Consider a word $w\in\Sigma^{*}$, we show that if
$\mathcal{A}_{\textsc{abs}}(w)\leq k$ for some $k\in\mathbb{N}$ then
$\mathcal{A}_{\textsc{ham}}(w)\leq(2k+1)(k+1)$. Assume
$\mathcal{A}_{\textsc{abs}}(w)\leq k$, then there exists a jump sequence
$\mathbf{a}=(a_{0},\ldots,a_{n+1})$ such that
$\llbracket\mathbf{a}\rrbracket\leq k$ and
$w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{A})$. In the following we show that
$a_{i}=i$ for all but $(2k+1)(k+1)$ indices, i.e., $|\\{i\mid a_{i}\neq
i\\}|\leq(2k+1)(k+1)$.

It is convenient to think of the jumping head moving according to $\mathbf{a}$
in tandem with a sequential head moving from left to right. Recall that by
Lemma 9, for every index $i$ we have that $i-k\leq a_{i}\leq i+k$, i.e. the
jumping head stays within distance $k$ from the sequential head.

Consider an index $i$ such that $a_{i}\neq i$ (if there is no such index, we
are done). we claim that within at most $2k$ steps, $\mathcal{A}$ performs a
jump of cost at least 1 according to $\mathbf{a}$. More precisely, there
exists $i+1\leq j\leq i+2k$ such that $|a_{j}-a_{j-1}|>1$. To show this we
split to two cases:

  * •

If $a_{i}>i$, then there exists some $m\leq i$ such that $m$ has not yet been
visited according to $\mathbf{a}$ (i.e., by step $i$). Index $m$ must be
visited by $a_{i}$ within at most $k$ steps (otherwise it becomes outside the
$i-k,i+k$ window around the sequential head), and since $a_{i}>i$, it must
perform a “ left jump” of size at least 2 (otherwise it always remains to the
right of the sequential reading head).

  * •

If $a_{i}<i$, then there exists some $m\geq i$ such that $m$ has already been
visited by step $i$ according to $\mathbf{a}$. Therefore, within at most $2k$
steps, the jumping head must skip at least over this position (think of $m$ as
a hurdle coming toward the jumping head, which must stay within distance $k$
of the sequential head and therefor has to skip over it). Such a jump incurs a
cost of at least 1.

Now, let $B=\\{i\mid a_{i}\neq i\\}$ and assume by way of contradiction that
$|B|>(2k+1)(k+1)$. By the above, for every $i\in B$, within $2k$ steps the run
incurs a cost of at least 1. While some of these intervals of $2k$ steps may
overlap, we can still find at least $k+1$ such disjoint segments (indeed,
every $i\in B$ can cause an overlap with at most $2k$ other indices). More
precisely, there are $i_{1}<i_{2}<\ldots<i_{k+1}$ in $B$ such that
$i_{j}>i_{j-1}+2k$ for all $j$, and therefore each of the costs incurred
within $2k$ steps of visiting $i_{j}$ is independent of the others. This,
however, implies that $\llbracket\mathbf{a}\rrbracket\geq k+1$, which is a
contradiction, so $|B|\leq(2k+1)(k+1)$.

It now follows that $\mathcal{A}_{\textsc{ham}}(w)=|\\{i\mid w_{a_{i}}\neq
w_{i}\\}|\leq|\\{i\mid a_{i}\neq i\\}|\leq(2k+1)(k+1)$ ∎

Combining Lemmas 25 and 26, we have the following.

######  Corollary 27.

If abs is bounded, then so is rev.

We proceed to show that no other implication holds with regard to boundedness,
by demonstrating languages for each possible choice of bounded/unbounded
semantics (c.f. Remark 6). The examples are summarized in Table 1, and are
proved below.

abs | ham | rev | Language
---|---|---|---
Bounded | Bounded | Bounded | $(a+b)^{*}$
Unbounded | Bounded | Bounded | $(a+b)^{*}a$
Unbounded | Unbounded | Bounded | $a^{*}b^{*}$
Unbounded | Unbounded | Unbounded | $(ab)^{*}$
Table 1: Examples for every possible combination of bounded/unbounded
semantics. The languages are given by regular expressions (e.g., $(a+b)^{*}a$
is the languages of words that end with $a$.)

######  Example 28.

The language $(a+b)^{*}$ is bounded in all semantics. This is trivial, since
every word is accepted, and in particular has cost $0$ in all semantics.

######  Example 29.

The language $(a+b)^{*}a$ is bounded in the ham and rev semantics, but
unbounded in abs. Indeed, let $\mathcal{A}$ be an NFA such that
$\mathfrak{L}(\mathcal{A})=(a+b)^{*}a$ and consider a word
$w\in\mathfrak{J}(\mathcal{A})$, then $w$ has at least one occurrence of $a$
at some index $i$. Then, for the jumping sequence
$\mathbf{a}=(0,1,2,\ldots,i-1,n,i+1,\ldots n-1,i,n+1)$ we have that
$w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{A})$. Observe that
$d_{H}(w_{\mathbf{a}},w)\leq 2$ (since $w_{\mathbf{a}}$ differs from $w$ only
in indices $i$ and $n$), and $\mathtt{Turn}(\mathbf{a})\subseteq\\{i,n\\}$, so
$\mathcal{A}_{\textsc{ham}}(w)\leq 2$ and $\mathcal{A}_{\textsc{rev}}(w)\leq
2$.

For abs, however, consider the word $ab^{n}$ for every $n\in\mathbb{N}$. Since
the letter $a$ must be read last, then in any jumping sequence accepting the
word, there is a point where the jumping head is at index $n$ and the
sequential head is at position $1$. By Lemma 9, it follows that
$\mathcal{A}_{\textsc{abs}}(w)\geq n-1$, and by increasing $n$, we have that
$\mathcal{A}_{\textsc{abs}}$ is unbounded.

######  Example 30.

The language $a^{*}b^{*}$ is bounded in the rev semantics, but unbounded in
ham and abs. Indeed, let $\mathcal{A}$ be an NFA such that
$\mathfrak{L}(\mathcal{A})=a^{*}b^{*}$ and consider a word
$w\in\mathfrak{J}(\mathcal{A})$, and denote by $i_{1}<i_{2}\ldots<i_{k}$ the
indices of $a$’s in $w$ in increasing order, and by
$j_{1}>j_{2}>\ldots>j_{n-k}$ the indices of $b$’s in decreasing order. Then,
for the jumping sequence $\mathbf{a}=(i_{1},\ldots,i_{k},j_{1},\ldots
j_{n-k},n+1)$ we have that $w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{A})$, and
$\mathcal{A}_{\textsc{rev}}(w)\leq 2$ (since the jumping head goes right
reading all the $a$’s, then left reading all the $b$’s, then jumps to $n+1$).

For ham, consider the word $w=b^{n}a^{n}$ for every $n\in\mathbb{N}$. The only
permutation of $w$ that is accepted in $\mathfrak{L}(\mathcal{A})$ is
$w^{\prime}=a^{n}b^{n}$, and $d_{H}(w,w^{\prime})=n$, so
$\mathcal{A}_{\textsc{ham}}$ is unbounded. By Lemma 26 it follows that
$\mathcal{A}_{\textsc{abs}}$ is also unbounded.

######  Example 31.

The language $(ab)^{*}$ is unbounded in all the semantics. Indeed, let
$\mathcal{A}$ be an NFA such that $\mathfrak{L}(\mathcal{A})=(ab)^{*}$, then
by Lemmas 25 and 27 it suffices to show that $\mathcal{A}_{\textsc{rev}}$ is
unbounded.

Consider the word $w=b^{n}a^{n}$ for every $n\in\mathbb{N}$, and let
$\mathbf{a}=(a_{0},a_{1},\ldots,a_{2n},a_{2n+1})$ such that
$w_{\mathbf{a}}\in(ab)^{*}$, then for every odd $i\leq 2n$ we have
$a_{i}\in\\{n+1,\ldots,2n\\}$ and for every even $i\leq 2n$ we have
$a_{i}\in\\{1,\ldots,n\\}$. In particular, every index $1\leq i\leq 2n$ is a
turning point, so $\mathcal{A}_{\textsc{rev}}(w)=2n$, and
$\mathcal{A}_{\textsc{rev}}$ is unbounded.

##  8 Discussion and Future Work

Quantitative semantics are often defined by externally adding some quantities
(e.g., weights) to a finite-state model, usually with the intention of
explicitly reasoning about some unbounded domain. It is rare and pleasing when
quantitative semantics arise naturally from a Boolean model. In this work, we
study three such semantics. Curiously, despite the semantics being intuitively
unrelated, it turns out that they give rise to interesting interplay (see
Section 7).

We argue that Boundedness is a fundamental decision problem for the semantics
we introduce, as it measures whether one can make do with a certain budget for
jumping. An open question left in this research is _existentially-quantified
boundedness_ : whether there _exists_ some bound $k$ for which
$\mathcal{A}_{\textsc{sem}}$ is $k$-bounded. This problem seems technically
challenging, as in order to establish its decidability, we would need to
upper-bound the minimal $k$ for which the automaton is $k$-bounded, if it
exists. The difficulty arises from two fronts: first, standard methods for
showing such bounds involve some pumping argument. However, the presence of
permutations makes existing techniques inapplicable. We expect that a new
toolbox is needed to give such arguments. Second, the constructions we present
for Univ-Param-Boundedness in the various semantics seem like the natural
approach to take. Therefore, a sensible direction for the existential case is
to analyze these constructions with a parametric $k$. The systems obtained
this way, however, do not fall into (generally) decidable classes. For
example, in the ham semantics, using a parametric $k$ we can construct a
labelled VASS. But the latter do not admit decidable properties for the
corresponding boundedness problem.

We remark on one fragment that can be shown to be decidable: consider a
setting where the jumps are restricted to swapping disjoint pairs of adjacent
letters, each incurring a cost of 1. Then, the JFA can be translated to a
weighted automaton, whose boundedness problem is decidable by [16, 19]. We
remark that the latter decidability is a very involved result. This suggests
(but by no means proves) that boundedness may be a difficult problem.

## References

  * [1]
  * [2] Antonio Abu Nassar & Shaull Almagor (2022): _Simulation by Rounds of Letter-To-Letter Transducers_.  In: 30th EACSL Annual Conference on Computer Science Logic.
  * [3] Shaull Almagor (2020): _Process Symmetry in Probabilistic Transducers_.  In: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science.
  * [4] Shaull Almagor & Orna Kupferman (2011): _Max and sum semantics for alternating weighted automata_.  In: International Symposium on Automated Technology for Verification and Analysis, Springer, pp. 13–27.
  * [5] Shaull Almagor & Omer Yizhaq (2023): _Jumping Automata over Infinite Words_.  In: International Conference on Developments in Language Theory, Springer, pp. 9–22.
  * [6] Udi Boker (2021): _Quantitative vs. weighted automata_.  In: Reachability Problems: 15th International Conference, RP 2021, Liverpool, UK, October 25–27, 2021, Proceedings 15, Springer, pp. 3–18.
  * [7] Michaël Cadilhac, Alain Finkel & Pierre McKenzie (2012): _Affine Parikh automata_.  RAIRO-Theoretical Informatics and Applications 46(4), pp. 511–545.
  * [8] Michaël Cadilhac, Alain Finkel & Pierre McKenzie (2012): _Bounded parikh automata_.  International Journal of Foundations of Computer Science 23(08), pp. 1691–1709.
  * [9] Krishnendu Chatterjee, Laurent Doyen & Thomas A Henzinger (2010): _Quantitative languages_.  ACM Transactions on Computational Logic (TOCL) 11(4), pp. 1–38.
  * [10] Manfred Droste, Werner Kuich & Heiko Vogler (2009): _Handbook of weighted automata_.  Springer Science & Business Media.
  * [11] Szilárd Zsolt Fazekas, Kaito Hoshi & Akihiro Yamamura (2021): _Two-way deterministic automata with jumping mode_.  Theoretical Computer Science 864, pp. 92–102.
  * [12] Henning Fernau, Meenakshi Paramasivan & Markus L Schmid (2015): _Jumping finite automata: characterizations and complexity_.  In: International Conference on Implementation and Application of Automata, Springer, pp. 89–101.
  * [13] Henning Fernau, Meenakshi Paramasivan, Markus L Schmid & Vojtěch Vorel (2017): _Characterization and complexity results on jumping finite automata_.  Theoretical Computer Science 679, pp. 31–52.
  * [14] Dana Fisman, Joshua Grogin & Gera Weiss (2023): _A Normalized Edit Distance on Infinite Words_.  In: 31st EACSL Annual Conference on Computer Science Logic (CSL 2023), Schloss-Dagstuhl-Leibniz Zentrum für Informatik.
  * [15] Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen & Martin Zimmermann (2022): _Parikh Automata over Infinite Words_.  In: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science.
  * [16] Kosaburo Hashiguchi (1982): _Limitedness theorem on finite automata with distance functions_.  Journal of computer and system sciences 24(2), pp. 233–244.
  * [17] Felix Klaedtke & Harald Rueß (2003): _Monadic second-order logics with cardinalities_.  In: Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30–July 4, 2003 Proceedings 30, Springer, pp. 681–696.
  * [18] Giovanna J Lavado, Giovanni Pighizzini & Shinnosuke Seki (2014): _Operational state complexity under Parikh equivalence_.  In: Descriptional Complexity of Formal Systems: 16th International Workshop, DCFS 2014, Turku, Finland, August 5-8, 2014. Proceedings 16, Springer, pp. 294–305.
  * [19] Hing Leung & Viktor Podolskiy (2004): _The limitedness problem on distance automata: Hashiguchi’s method revisited_.  Theoretical Computer Science 310(1-3), pp. 147–158.
  * [20] Alexander Meduna & Petr Zemek (2012): _Jumping finite automata_.  International Journal of Foundations of Computer Science 23(07), pp. 1555–1578.
  * [21] Mehryar Mohri (2002): _Edit-distance of weighted automata_.  In: International Conference on Implementation and Application of Automata, Springer, pp. 1–23.
  * [22] Vojtěch Vorel (2018): _On basic properties of jumping finite automata_.  International Journal of Foundations of Computer Science 29(01), pp. 1–15.

##  Appendix A Proofs

###  A.1 Proof of Lemma 9

Assume $a_{j}<j$. The proof in this case is similar but instead of looking at
the sum $\sum_{i=1}^{j}\llbracket a_{i}-a_{i-1}\rrbracket$, we look at the sum
$\sum_{i=j+1}^{n+1}\llbracket
a_{i}-a_{i-1}\rrbracket\leq\llbracket\mathbf{a}\rrbracket$. From the
definition of $\llbracket\cdot\rrbracket$ we have

$\sum_{i=j+1}^{n+1}\llbracket
a_{i}-a_{i-1}\rrbracket=\left(\sum_{i=j+1}^{n+1}|a_{i}-a_{i-1}|\right)-(n+1-(j+1)+1)=\left(\sum_{i=j+1}^{n+1}|a_{i}-a_{i-1}|\right)-(n+1-j)$

Similarly to the previous case, from the triangle inequality we have

$\left(\sum_{i=j+1}^{n+1}|a_{i}-a_{i-1}|\right)-(n+1-j)\geq|a_{n+1}-a_{j}|-(n+1-j)=n+1-a_{j}-(n+1-j)=j-a_{j}=|a_{j}-j|$

where we use the fact that $a_{n+1}=n+1>a_{j}$, and our assumption that
$a_{j}<j$. This again concludes that
$\llbracket\mathbf{a}\rrbracket\geq|a_{j}-j|$. ∎

###  A.2 Proof of Theorem 12

Consider a JFA $\mathcal{A}$ and $k\in\mathbb{N}$ ($k$ is either fixed or
given as input, which does not effect decidability), and let $\mathcal{B}$ be
the NFA constructed as per Lemma 11. In order to decide Univ-$k$-Boundedness
and Univ-Param-Boundedness, observe that $\mathcal{A}_{\textsc{abs}}(w)\leq k$
for every word $w\in\Sigma^{*}$ if and only if
$\mathfrak{L}(\mathcal{B})=\Sigma^{*}$. Since the latter is decidable for NFA,
we have decidability.

Similarly, in order to decide $k$-Boundedness and Univ-Param-Boundedness,
observe that $\mathcal{A}_{\textsc{abs}}(w)\leq k$ for every word
$w\in\mathfrak{J}(\mathcal{A})$ if and only if
$\mathfrak{J}(\mathcal{A})\subseteq\mathfrak{L}(\mathcal{B})$. We can decide
whether the latter holds by constructing the PA
$(\overline{\mathcal{B}},\mathcal{A})$ where $\overline{\mathcal{B}}$ is an
NFA for the complement of $\mathfrak{L}(\mathcal{B})$, and checking emptiness.
Since emptiness for PA is decidable [17], we conclude decidability. ∎

###  A.3 Proof of Lemma 14

In order for the reduction to work both for Univ-$k$-Boundedness and
$k$-Boundedness, we start with an initial transformation of the given NFA
$\mathcal{A}$ to an NFA $\mathcal{A}^{\prime}$ as follows. Given
$\mathcal{A}$, we introduce a fresh symbol $\$$ to its alphabet, and modify it
so that reading $\$$ from every state can either stay at the same state, or
transition to a new accepting state $q_{\$}$. From $q_{\$}$ no letters can be
read. $\mathcal{A}^{\prime}$ then satisfies the following property: if
$L(\mathcal{A})=\Sigma^{*}$ then
$L(\mathcal{A}^{\prime})=(\Sigma\cup\\{\$\\})^{*}$, and if
$L(\mathcal{A})\neq\Sigma^{*}$ then there exists a word $x\notin
L(\mathcal{A}^{\prime})$ such that $x\in\mathfrak{J}(\mathcal{A}^{\prime})$.
Indeed, for every (non-empty) word $x\notin L(\mathcal{A})$ we have that
$\$x\notin L(\mathcal{A}^{\prime})$ but $x\$\in L(\mathcal{A}^{\prime})$. We
henceforth identify $\mathcal{A}$ with $\mathcal{A}^{\prime}$, and use this
property in the proof.

We now turn to the details of the reduction, differing from the intuition in
the main body mainly by the pesky presence of $\epsilon$. Given $\mathcal{A}$,
we first check whether $\epsilon\in\mathfrak{L}(\mathcal{A})$ (i.e., we check
whether $Q_{0}\cap\alpha\neq\emptyset$). If
$\epsilon\notin\mathfrak{L}(\mathcal{A})$, then
$\mathfrak{L}(\mathcal{A})\neq\Sigma^{*}$ and we output some fixed unbounded
automaton $\mathcal{B}$ (e.g., as in Examples 1 and 31). Otherwise, we proceed
to construct $\mathcal{B}$ such that $w\in\mathfrak{L}(\mathcal{B})$ if and
only if either Conditions 1 or 2 above hold, or:

  1. 3.

$w=\heartsuit^{m}$ (think of this as an exception to Condition 2 where
$w|_{\Sigma}=\epsilon$).

Constructing $\mathcal{B}$ from $\mathcal{A}$ is straightforward by taking
roughly $m$ copies of $\mathcal{A}$ to track the number of $\heartsuit$ in the
word. In particular, the reduction is in polynomial time.

We claim that $\mathfrak{L}(\mathcal{A})=\Sigma^{*}$ if and only if
$\mathcal{B}$ is $2m$-bounded. For the first direction, assume
$\mathfrak{L}(\mathcal{A})=\Sigma^{*}$. As mentioned above, for every
$w\in(\Sigma\cup\\{\heartsuit\\})^{*}$ if $w\in\mathfrak{L}(\mathcal{B})$ then
$\mathcal{B}_{\textsc{abs}}(w)=0\leq 2m$. If
$w\notin\mathfrak{L}(\mathcal{B})$ then $w$ starts with $\heartsuit$ but has
exactly $m$ occurrences of $\heartsuit$, and in addition,
$w\neq\heartsuit^{m}$ so the $m+1$-th letter of $w$ is in $\Sigma$. Then, the
following jump sequence $\mathbf{a}$ causes $\mathcal{B}$ to accept
$w_{\mathbf{a}}$:

$\mathbf{a}=(0,m+1,1,2,\ldots,m,m+2,m+3,\ldots|w|,|w|+1)$

Indeed, $w_{\mathbf{a}}$ does not start with $\heartsuit$, has exactly $m$
occurrences of $\heartsuit$, and
$w|_{\Sigma}\in\mathfrak{L}(\mathcal{A})=\Sigma^{*}$, so Condition 2 holds.
Finally, note that $\llbracket\mathbf{a}\rrbracket=2m$ (since the only non-
zero jumps are $0$ to $m+1$, $m+1$ to $1$, and $m$ to $m+2$).

For the converse, assume $\mathfrak{L}(\mathcal{A})\neq\Sigma^{*}$. If
$\epsilon\notin\mathfrak{L}(\mathcal{A})$, then correctness follows by the
treatment of this case above. Otherwise, let
$x\notin\mathfrak{L}(\mathcal{A})$ with $x\neq\epsilon$. We can assume by the
modification above that $x\in\mathfrak{J}(\mathcal{A})$. and consider
$w=\heartsuit^{m}x$. We claim that $\mathcal{B}_{\textsc{abs}}(w)>2m$. Indeed,
$w\notin\mathfrak{L}(\mathcal{B})$, and therefore
$\mathcal{B}_{\textsc{abs}}(w)>0$. If $\mathcal{B}_{\textsc{abs}}(w)=\infty$
then we are done. Otherwise, let $\mathbf{a}$ be a jump sequence such that
$w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{B})$. Then $a_{1}\geq m+1$,
contributing a cost of at least $m$ to $\mathbf{a}$. It can be easily seen by
induction over $m$ that in order for $\mathbf{a}$ to cover the entries
$1,\ldots,m$ starting at position $m+1$ and ending at position $m+2$, it
requires cost of at least another $m$. Then, however, in order for
$w_{\mathbf{a}}$ to be accepted by $\mathcal{B}$, it must hold that
$w_{\mathbf{a}}|_{\Sigma}\neq x$, so $\mathbf{a}$ is not the identity starting
from $m+1$. It therefore has an additional cost of at least $1$. Thus,
$\llbracket\mathbf{a}\rrbracket>2m$. In particular,
$\mathcal{B}_{\textsc{abs}}(w)>2m$, so $\mathcal{B}$ is not $2m$-bounded. Note
that $\mathcal{B}_{\textsc{abs}}(w)<\infty$, since
$x\in\mathfrak{J}(\mathcal{A})$. Thus, we are done both in the universal and
non-universal setting. ∎

###  A.4 Proof of Lemma 17

For the first direction, assume $\mathcal{A}_{\textsc{rev}}(w)\leq k$, so
there exists a jump vector $\mathbf{a}$ such that
$|\mathtt{Turn}(\mathbf{a})|\leq k$ and
$w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{A})$. Write
$\mathtt{Turn}(\mathbf{a})=\\{i_{1},i_{2},\ldots,i_{\ell}\\}$ where
$i_{1}<i_{2}<\ldots<i_{\ell}$, and set $i_{0}=0$ and $i_{\ell+1}=n+1$. Then,
for every $1\leq j\leq\ell+1$, the _$j$ -th turning subword_ is
$s_{j}=w_{a_{i_{j-1}}}w_{a_{i_{j-1}+1}}\cdots w_{a_{i_{j}}}$ (for $j=\ell+1$
we end with $w_{a_{i_{\ell+1}-1}}$). If $\ell+1<k+1$ we define the remaining
subwords $s_{\ell+2},\ldots,s_{k+1}$ to be $\epsilon$. To avoid cumbersome
indexing, we assume $\ell+1=k+1$ in the following.

It is now easy to see that Conditions 1 and 2 hold for $s_{1},\ldots,s_{k+1}$.
Indeed, by definition we have $s_{1}\cdots
s_{k+1}\in\mathfrak{L}(\mathcal{A})$, so Condition 1 holds. For Condition 2,
observe that for every $1\leq i\leq k+1$, if $i$ is odd, then $s_{i}$ consists
of an ascending sequence of letters, and if $i$ is even then $s_{i}$ is a
descending sequence. Since the $s_{i}$ form a partition of the letters of $w$,
we can conclude that $w\in s_{1}\shuffle{s_{2}}^{R}\shuffle
s_{3}\shuffle{s_{4}}^{R}\shuffle\ldots\shuffle s_{k+1}$ (by shuffling the
letters of these words to form exactly the sequence of indices
$1,\ldots,|w|$).

For the converse, consider words $s_{1},\ldots,s_{k+1}$ such that Conditions 1
and 2 hold. By Condition 2, we see that the word $s_{1}s_{2}\ldots s_{k+1}$ is
a permutation of $w$, and moreover – from the way $w$ is obtained in
$s_{1}\shuffle{s_{2}}^{R}\shuffle
s_{3}\shuffle{s_{4}}^{R}\shuffle\ldots\shuffle s_{k+1}$ we can extract a jump
sequence $\mathbf{a}$ such that $w_{\mathbf{a}}=s_{1},\ldots,s_{k+1}$ and such
that the turning subwords of $\mathbf{a}$ are exactly
$s_{1},s_{2}^{R},\ldots,s_{k+1}$. Indeed, this follows from the same
observation as above – for odd $i$ we have that $s_{i}$ is an increasing
sequence of indices, and for even $i$ it is decreasing. In particular,
$|\mathtt{Turn}(\mathbf{a})|\leq k$, so $\mathcal{A}_{\textsc{rev}}(w)\leq k$.
∎

###  A.5 Proof of Lemma 18

The overall plan is to construct $\mathcal{B}$ so that it captures the
conditions in Lemma 17. Intuitively, $\mathcal{B}$ keeps track of $k+1$
coordinates, each corresponding to a turning subword (that are
nondeterministically constructed). The odd coordinates simulate the behavior
of $\mathcal{A}$, whereas the even ones simulate the reverse of $\mathcal{A}$.
In addition $\mathcal{B}$ checks (using its initial and accepting states) that
the runs on the subwords can be correctly concatenated. We proceed with the
precise details.

Denote $\mathcal{A}=\langle\Sigma,Q,\delta,Q_{0},F\rangle$. We construct
$\mathcal{B}=\langle\Sigma,Q^{\prime},\delta^{\prime},Q^{\prime}_{0},F^{\prime}\rangle$
as follows. $Q^{\prime}=Q^{k+1}$, and the initial and final states are:

$\displaystyle Q^{\prime}_{0}=\\{(q_{1},q_{2},\ldots q_{k+1})\ |\ q_{1}\in
Q_{0}\wedge q_{i}=q_{i+1}\text{ for all even }i\\}$ $\displaystyle
F^{\prime}=\\{(q_{1},q_{2},\ldots q_{k+1})\ |\ q_{k+1}\in F\wedge
q_{i}=q_{i+1}\text{ for all odd }i\\}$

For the transition function, we have that
$(q^{\prime}_{0},q^{\prime}_{1},\ldots
q^{\prime}_{k})\in\delta^{\prime}((q_{0},q_{1},\ldots q_{k}),\sigma)$ if and
only if there exists a single $1\leq j\leq k+1$ such that
$q^{\prime}_{j}\in\delta(q_{j},\sigma)$ if $j$ is odd, and
$q_{j}\in\delta(q^{\prime}_{j},\sigma)$ if $j$ is even. In addition, for every
$i\neq j$, it holds that $q^{\prime}_{i}=q_{i}$.

We turn to show the correctness of $\mathcal{B}$. Consider an accepting run
$\rho$ of $\mathcal{B}$ on some word. Then $\rho$ starts at state
$(q_{1},q_{2},\ldots,q_{k+1})\in Q^{\prime}_{0}$ and ends at state
$(s_{1},s_{2},\ldots,s_{k+1})\in F^{\prime}$. By the definition of
$\delta^{\prime}$, we can split $\rho$ according to which component
“progresses” in each transition, so that $\rho$ can be written as a shuffle of
run $\rho^{1},\ldots,\rho^{k+1}$ where $\rho^{i}$ leads from $q_{i}$ to
$s_{i}$ in $\mathcal{A}$ if $i$ is odd, and $\rho^{i}$ leads from $q_{i}$ to
$s_{i}$ in the _reverse_ of $\mathcal{A}$ if $i$ is even. The latter is
equivalent to $(\rho^{i})^{R}$ (i.e., the reverse run of $\rho^{i}$) leading
from $s_{i}$ to $q_{i}$ in $\mathcal{A}$ if $i$ is even.

We now observe that these runs can be concatenated as follows: Recall that
$q_{1}\in Q_{0}$ (by the definition of $Q^{\prime}_{0}$). Then, $\rho^{1}$
leads from $q_{1}$ to $s_{1}$ in $\mathcal{A}$. By the definition of $F$ we
have $s_{1}=s_{2}$, and $(\rho^{2})^{R}$ leads from $s_{2}$ to $q_{2}$ in
$\mathcal{A}$. Therefore, $\rho^{1}(\rho^{2})^{R}$ leads from $q_{1}$ to
$q_{2}$ in $\mathcal{A}$. Continuing in the same fashion, we have
$q_{2}=q_{3}$, and $\rho^{3}$ leading from $q_{3}$ to $s_{3}$, and so on up to
$s_{k+1}$.

Thus, we have that
$\rho^{1}(\rho^{2})^{R}\rho_{3}\cdots(\rho^{k})^{R}\rho^{k+1}$ is an accepting
run of $\mathcal{A}$.

By identifying each accepting run $\rho^{i}$ with the subword it induces, we
have that $w\in\mathfrak{L}(\mathcal{B})$ if and only if there are words
$s_{1},\ldots,s_{k+1}$ such that the two conditions in Lemma 17 are satisfied.
∎

###  A.6 Proof of Theorem 19

By Remark 16 we can assume without loss of generality that $k$ is even, and we
denote $k=2m$. We reduce the universality problem for NFAs to the
Univ-$2m$-Boundedness problem. Consider an NFA $\mathcal{A}=\langle
Q,\Sigma,\delta,Q_{0},\alpha\rangle$, and let
$\heartsuit,\spadesuit\notin\Sigma$ be fresh symbols. We first check whether
$\epsilon\in\mathfrak{L}(\mathcal{A})$. If
$\epsilon\notin\mathfrak{L}(\mathcal{A})$, then
$\mathfrak{L}(\mathcal{A})\neq\Sigma^{*}$ and we output some fixed unbounded
automaton $\mathcal{B}$ (e.g., as in Examples 1 and 31).

Otherwise, we obtain from $\mathcal{A}$ an NFA $\mathcal{B}$ over the alphabet
$\Sigma\cup\\{\heartsuit,\spadesuit\\}$ such that
$w\in\mathfrak{L}(\mathcal{B})$ if and only if the following hold:

  1. 1.

Either $w$ does not contain exactly $m$ occurrences of $\heartsuit$ and of
$\spadesuit$, or

  2. 2.

$w=(\heartsuit\spadesuit)^{m}x$ where $x\in\mathfrak{L}(\mathcal{A})$ (in
particular $x\in\Sigma^{*}$).

Constructing $\mathcal{B}$ from $\mathcal{A}$ is straightforward as the union
of two components: one that accepts words that satisfy Condition 1 (using
$2m+1$ states) and one for Condition $2$, which prepends to $\mathcal{A}$ a
component with $2m$ states accepting $(\heartsuit\spadesuit)^{m}$. In
particular, the reduction is in polynomial time.

We then have the following: if $\mathfrak{L}(\mathcal{A})=\Sigma^{*}$, then
for every $w\in(\Sigma\cup\\{\heartsuit,\heartsuit\\})^{*}$, if $w$ satisfies
Condition 1, then $\mathcal{B}_{\textsc{rev}}(w)=0$. Otherwise, $w$ has
exactly $m$ occurrences of $\heartsuit$ and of $\spadesuit$. Denote the
indices of $\heartsuit$ by $i_{1}<i_{2}<\ldots<i_{m}$ and of $\spadesuit$ by
$j_{1}<j_{2}<\ldots<j_{m}$. Also denote by $t_{0}<t_{1}<\ldots<t_{r}$ the
remaining indices of $w$. Then, consider the jump sequence

$\mathbf{a}=(0,i_{1},j_{1},i_{2},j_{2},\ldots,i_{m},j_{m},t_{0},t_{1},\ldots,t_{r},n+1)$

We claim that $w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{B})$ by Condition 2.
Indeed, $w$ starts with $(\heartsuit\spadesuit)^{m}$, followed by letters in
$\Sigma$ composing a word $x$. Since
$x\in\mathfrak{L}(\mathcal{A})=\Sigma^{*}$, we have that Condition 2 holds. In
addition, observe that since $t_{0}<t_{1}<\ldots<t_{r}<n+1$, then
$\mathtt{Turn}(\mathbf{a})\subseteq\\{i_{1},j_{1},\ldots,i_{m},j_{m},t_{0}\\}$,
and in particular $|\mathtt{Turn}(\mathbf{a})|\leq 2m+1$. Moreover, by Remark
16 we know that $|\mathtt{Turn}(\mathbf{a})|$ is even, so in fact
$|\mathtt{Turn}(\mathbf{a})|\leq 2m=k$. We conclude that
$\mathcal{B}_{\textsc{rev}}(w)\leq k$, so $\mathcal{B}$ is $k$-bounded.

Conversely, if $\mathfrak{L}(\mathcal{A})\neq\Sigma^{*}$, take
$x\notin\mathfrak{L}(\mathcal{A})$ such that $x\neq\epsilon$ (which exists
since we checked above that $\epsilon\in\mathfrak{L}(\mathcal{A})$). Consider
the word $w=\spadesuit^{m}\heartsuit^{m}x$, then have
$w\notin\mathfrak{L}(\mathcal{B})$. We claim that
$\mathcal{B}_{\textsc{rev}}(w)>2m$. Indeed, if there exists $\mathbf{a}$ such
that $w_{\mathbf{a}}\in\mathfrak{L}(\mathcal{B})$, then since $w$ has exactly
$m$ occurrences of $\spadesuit$ and of $\heartsuit$, it must be accepted by
Condition 2. By the structure of $w$, the jump sequence $\mathbf{a}$ needs to
permute $\spadesuit^{m}\heartsuit^{m}$ into $(\heartsuit\spadesuit)^{m}$.
Intuitively, this means that the head must jump “back and forth” for $2m$
steps. More precisely, for every $i\in\\{1,\ldots,|w|\\}$ it holds that

$a_{i}\in\begin{cases}\\{m+1,\ldots,2m\\}&i\leq 2m\text{ is odd}\\\
\\{1,\ldots,m\\}&i\leq 2m\text{ is even}\\\ \\{2m+1,\ldots,|w|\\}&i>2m\\\
\end{cases}$

In particular, $\\{1,\ldots,2m\\}\subseteq\mathtt{Turn}(\mathbf{a})$. Observe
that the remaining suffix of $w_{\mathbf{a}}$ starting at $2m+1$ cannot be
$x$, since $x\notin\mathfrak{L}{\mathcal{A}}$, so $\mathbf{a}$ is not the
identity starting from $2m+1$. It therefore has an additional reversal cost of
at least $1$. Thus, $|\mathtt{Turn}(\mathbf{a})|>2m$. In particular,
$\mathcal{B}_{\textsc{rev}}(w)>2m$, so $\mathcal{B}$ is not $2m$-bounded, and
we are done. ∎

###  A.7 Proof of Theorem 21

By definition we have that $\mathcal{A}_{\textsc{ham}}(w)\leq|w|$ for every
word $w$. Thus, in order to decide whether $\mathcal{A}_{\textsc{ham}}(w)\leq
k$ we can nondeterministically guess a permutation $w^{\prime}\sim w$ and
verify that $w^{\prime}\in\mathfrak{L}(\mathcal{A})$ and that
$d_{H}(w,w^{\prime})\leq k$. Both conditions are computable in polynomial
time. Therefore, the problem is in NP.

Hardness follows (similarly to the proof of Theorem 8) by reduction from
membership in JFA, noting that $w\in\mathfrak{J}(\mathcal{A})$ if and only if
$\mathcal{A}_{\textsc{ham}}(w)\leq|w|$. ∎

###  A.8 Proof ofLemma 22

We now turn to the formal details. Recall that
$\mathcal{A}=\langle\Sigma,Q,\delta,Q_{0},\alpha\rangle$. We define
$\mathcal{B}=\langle\Sigma,Q^{\prime},\delta^{\prime},Q_{0}^{\prime},\beta\rangle$.

The state space of $\mathcal{B}$ is
$Q^{\prime}=Q\times\\{-k,\ldots,k\\}^{\Sigma}\times\\{0,\ldots,k\\}$. We
denote a state of $\mathcal{B}$ by $(q,f,c)$ where $q\in Q$ is the current
state of $\mathcal{A}$, $f:\Sigma\to\\{-k,\ldots,k\\}$ describes for each
letter its _balance_ and $c\in\\{0,\ldots,k\\}$ is the total number of swaps
thus far.

The initial states of $\mathcal{B}$ are $Q^{\prime}_{0}=\\{(q,f,0)\mid q\in
Q_{0}\wedge f(\sigma)=0\text{ for all }\sigma\in\Sigma\\}$. That is, we start
in an initial state of $\mathcal{A}$ with balance and total cost of $0$. The
transition function is defined as follows. Consider a state $(q,f,c)$ and a
letter $\sigma\in\Sigma$, then
$(q^{\prime},f^{\prime},c^{\prime})\in\delta^{\prime}((q,f,c),\sigma)$ if and
only if either $q^{\prime}=\delta(q,\sigma)$ and $f^{\prime}=f$ and
$c^{\prime}=c$, or there exists $\tau\in\Sigma$, $\tau\neq\sigma$ such that
$q^{\prime}\in\delta(q,\tau)$, $c^{\prime}=c+1$,
$f^{\prime}(\sigma)=f(\sigma)-1$, and $f^{\prime}(\tau)=f(\tau)+1$. That is,
in each transition we either read the current letter $\sigma$, or swap for a
letter $\tau$ and update the balances accordingly.

Finally, the accepting states of $\mathcal{B}$ are $\beta=\\{(q,f,c)\mid
q\in\alpha\wedge f(\sigma)=0\text{ for all }\sigma\in\Sigma\\}$.

In order to establish correctness, we observe that every run of $\mathcal{B}$
on a word $w$ induces a word $w^{\prime}$ (with the nondeterministically
guessed letters) such that along the run the components $f$ and $c$ of the
states track the swaps made between $w$ and $w^{\prime}$. In particular, $c$
keeps track of the number of total swaps, and
$\sum_{\sigma\in\Sigma}f(\sigma)=0$. Moreover, for every word $\sigma$, the
value $f(\sigma)$ is exactly the number of times $\sigma$ was read in
$w^{\prime}$ minus the number of times $\sigma$ was read in $w$.

Since $\mathcal{B}$ accepts a word only if $f\equiv 0$ at the last state, it
follows that $\mathcal{B}$ accepts if and only if $w^{\prime}\sim w$, and the
run of $\mathcal{A}$ on $w^{\prime}$ is accepting. Finally, since $c$ is
bounded by $k$ and is increased upon every swap, then $w$ is accepted if and
only if its cost is at most $k$. Note that since $c$ is increased upon each
swap, then limiting the image of $f$ to values in $\\{-k,\ldots,k\\}$ does not
pose a restriction, as they cannot go beyond these bounds without $c$ going
beyond the bound $k$ as well. ∎