11institutetext: Technion, Israel 11email<EMAIL_ADDRESS>22institutetext: Technion, Israel 22email<EMAIL_ADDRESS>
# Jumping Automata over Infinite Words††thanks: This research was supported by
the ISRAEL SCIENCE FOUNDATION (grant No. 989/22)

Shaull Almagor 11 0000-0001-9021-1175 Omer Yizhaq 22

###### Abstract

Jumping automata are finite automata that read their input in a non-
consecutive manner, disregarding the order of the letters in the word. We
introduce and study jumping automata over infinite words. Unlike the setting
of finite words, which has been well studied, for infinite words it is not
clear how words can be reordered. To this end, we consider three semantics:
automata that read the infinite word in some order so that no letter is
overlooked, automata that can permute the word in windows of a given size k,
and automata that can permute the word in windows of an existentially-
quantified bound. We study expressiveness, closure properties and algorithmic
properties of these models.

###### Keywords:

Jumping Automata Parikh Image Infinite Words

##  1 Introduction

Traditional automata read their input sequentially. Indeed, this is the case
for most state-based computational models. In some settings, however, the
order of the input does not matter. 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 the languages, a.k.a. their _Parikh image_. To
capture this notion in a computation model, _Jumping Automata_ 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 [10, 11, 24, 9, 18].

One of the most exciting developments in automata and language theory has been
the extension to the setting of infinite words [4, 19, 16], which has led to
powerful tools in formal methods. The infinite-word setting is far more
complicated than that of finite words, involving several acceptance conditions
and intricate expressiveness relationships. Most notably perhaps,
nondeterministic Büchi automata cannot be determinized, but can be
determinized to Rabin automata [17, 19, 22].

In this work, we introduce jumping automata over infinite words. The first
challenge is to find meaningful definitions for this model. Indeed, the
intuition of having the reading head “jump” to points in the word is ill-
suited for infinite words, since one can construct an infinite run even
without reading every letter (possibly even skipping infinitely many letters)
(see Remark 2).

To this end, we propose three semantics for modes of jumping over infinite
words for an automaton $\mathcal{A}$.

  * •

In the _jumping_ semantics, a word $w$ is accepted if $\mathcal{A}$ accepts a
permutation of it, i.e., a word $w^{\prime}$ that has the same number of
occurrences of each letter as $w$ for letters occurring finitely often, and
the same set of letters that occur infinitely often.

  * •

In the _$k$ -window jumping_ semantics, $w$ is accepted if we can make
$\mathcal{A}$ accept it by permuting $w$ within contiguous windows of some
fixed size $k$.

  * •

In the _$\exists$ -window jumping_ semantics, $w$ is accepted if there exists
some $k$ such that we can make $\mathcal{A}$ accept it by permuting $w$ within
contiguous windows of size $k$.

###### Example 1

Consider a Büchi automaton for the language $\\{(ab)^{\omega}\\}$ (see Fig.
3). Its jumping language is $\\{w:w$ has infinitely many $a$’s and $b$’s
$\\}$. Its $3$-window jumping language, for example, consists of words whose
$a$’s and $b$’s can be rearranged to construct $(ab)^{\omega}$ in windows of
size $3$, such as $(aab\cdot bba)^{\omega}$. As for its $\exists$-window
jumping language, it contains e.g., the word $(aaaabbbb)^{\omega}$, which is
not in the 3-window language, but does not contain
$aba^{2}b^{2}a^{3}b^{3}\cdots$, which is in the jumping language.

The definitions above capture different intuitive meanings for jumping: the
first definition only looks at the Parikh image of the word, and corresponds
to e.g., a setting where a word describes resources, with some resources being
unbounded. The second (more restrictive) definition captures a setting where
the word corresponds to e.g., a sequence of tasks to be handled, and we are
allowed some bounded freedom in reordering them, and the third corresponds to
a setting where we may introduce any finite delay to a task, but the overall
delays we introduce must be bounded.

We study the expressiveness of these semantics, as well as closure properties
and decision problems. Specifically, we show that languages in the jumping
semantics are closed under union, intersection and complement. Surprisingly,
we also show that automata admit determinization in this semantics, in
contrast with standard Büchi automata. We further show that the complexity of
decision problems on these automata coincide with their finite-word jumping
counterparts. Technically, these results are attained by augmenting semilinear
sets to accommodate $\infty$, and by showing that jumping languages can be
described in a canonical form with such sets.

In the $k$-window semantics, we show a correspondence with $\omega$-regular
languages, from which we deduce closure properties and solutions for decision
problems. Finally, we show that the $\exists$-window semantics is strictly
more expressive than the jumping semantics.

#### Paper organization

In Section 2 we recap some basic notions and define our jumping semantics.
Section 3 is the bulk of the paper, where we study the jumping semantics. In
Section 3.1 we introduce our variant of semilinear sets, and prove that it
admits a canonical form and that it characterizes the jumping languages. Then,
in Sections 3.2 and 3.3 we study closure properties and decision problems for
jumping languages. In Sections 4 and 5 we study the $k$-window and
$\exists$-window semantics, respectively. Finally, we conclude with future
research in Section 6. Throughout the paper, our focus is on clean
constructions and decidability. We thus defer complexity analyses to notes
that follow each claim.

#### 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 [11]). The works in [10, 11] establish several expressiveness
results on jumping automata, as well as some complexity results. In [24] many
additional closure properties are established. An extension of jumping
automata with a two-way tape was studied in [9].

Technically, since jumping automata correspond to the semilinear Parikh
image/commutative closure [21], tools on semilinear sets are closely related.
The works in [3, 7, 23] provide algorithmic results on semilinear sets, which
we use extensively, and in [18] properties of semilinear sets are related to
the state complexity of automata.

More broadly, automata and commutative closure also intersect in Parikh
Automata [13, 6, 5, 12], which read their input and accept if a certain Parikh
image relating to the run belongs to a given semilinear set. In particular,
[12] studies an extension of these automata to infinite words. 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 [2] in a jumping-flavour, and in [1] in a $k$-window flavour.

##  2 Preliminaries and Definitions

####  2.0.1 Automata

A _nondeterministic automaton_ 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. When
$|Q_{0}|=1$ and $|\delta(q,\sigma)|=1$ for every $q\in Q$ and
$\sigma\in\Sigma$, we say that $\mathcal{A}$ is _deterministic_.

We consider automata both over finite and over infinite words. We denote by
$\Sigma^{*}$ the set of finite words over $\Sigma$, and by $\Sigma^{\omega}$
the set of infinite words. For a word $w=\sigma_{1},\sigma_{2},\ldots$ (either
finite or infinite), let $|w|\in\mathbb{N}\cup\\{\infty\\}$ be its length. A
_run_ of $\mathcal{A}$ on $w$ is a sequence $\rho=q_{0},q_{1},\ldots$ such
that $q_{0}\in Q_{0}$ and for every $0\leq i<|w|$ it holds that
$q_{i+1}\in\delta(q_{i},w_{i+1})$ (naturally, a run is finite if $w$ is
finite, and infinite if $w$ is infinite). For finite words, the run $\rho$ is
_accepting_ if $q_{|w|}\in\alpha$. For infinite words we use the Büchi
acceptance condition, whereby the run $\rho$ is accepting if it visits
$\alpha$ infinitely often. Formally, define $\mathrm{Inf}(\rho)=\\{q\in
Q\mid\forall i\in\mathbb{N}\ \exists j>i,\ \rho_{j}=q\\}$, then $\rho$ is
accepting if $\mathrm{Inf}(\rho)\cap\alpha\neq\emptyset$. A word $w$ is
accepted by $\mathcal{A}$ if there exists an accepting run of $\mathcal{A}$ on
$w$.

The _language_ of an automaton $\mathcal{A}$, denoted
$\mathfrak{L}(\mathcal{A})$ is the set of words it accepts. We emphasize an
automaton is over finite words by writing
$\mathfrak{L}_{\text{fin}}(\mathcal{A})$.

###### Remark 1

There are other acceptance conditions for automata over infinite words, e.g.,
parity, Rabin, Streett, co-Büchi and Muller. As we show in Proposition 3, for
our purposes it is enough to consider Büchi.

####  2.0.2 Parikh Images and Permutations

Fix an alphabet $\Sigma$. We start by defining Parikh images and permutations
for finite words. Consider a finite word $x\in\Sigma^{*}$. For each letter
$\sigma\in\Sigma$ we denote by $\\#_{\sigma}[x]$ the number of occurrences of
$\sigma$ in $x$. The _Parikh image_ of $x$ is then the vector
$\Psi(x)=(\\#_{\sigma}[x])_{\sigma\in\Sigma}\in\mathbb{N}^{\Sigma}$. We say
that a word $y$ is a _permutation_ of $x$ if $\Psi(y)=\Psi(x)$, in which case
we write $x\sim y$ (clearly $\sim$ is an equivalence relation). We extend the
Parikh image to sets of words by $\Psi(L)=\\{\Psi(w)\mid w\in L\\}$.

We now extend the definitions to infinite words. Let
$\mathbb{N}=\\{0,1,\ldots\\}$ be the non-negative integers, and write
$\mathbb{N}_{\infty}=\mathbb{N}\cup\\{\infty\\}$. Consider an infinite word
$w\in\Sigma^{\omega}$. We extend the definition of Parikh image to infinite
words in the natural way: $\Psi(w)=(\\#_{\sigma}[w])_{\sigma\in\Sigma}$ where
$\\#_{\sigma}[w]$ is the number of occurrences of $\sigma$ in $w$ if it is
finite, and is $\infty$ otherwise. Thus,
$\Psi(w)\in\mathbb{N}_{\infty}^{\Sigma}$. Moreover, since $w$ is infinite, at
least one coordinate of $\Psi(w)$ is $\infty$, since we often restrict
ourselves to the Parikh images of infinite words, we denote by
$\mathbb{M}^{\Sigma}=\mathbb{N}_{\infty}^{\Sigma}\setminus\mathbb{N}^{\Sigma}$
the set of vectors that have at least one $\infty$ coordinate. Note that
$\vec{v}\in\mathbb{M}^{\Sigma}$ if and only if $\vec{v}$ is the Parikh image
of some infinite word over $\Sigma$.

For words $w,w^{\prime}\in\Sigma^{\omega}$, we abuse notation slightly and
write $w\sim w^{\prime}$ if $\Psi(w)=\Psi(w^{\prime})$, as well as refer to
$w^{\prime}$ as a _permutation_ of $w$. We now refine the notion of
permutation by restricting permutations to finite “windows”: let
$k\in\mathbb{N}$, we say that $w$ is a _$k$ -window permutation_ of
$w^{\prime}$, and we write $w\sim_{k\boxplus}w^{\prime}$ (the symbol
$\boxplus$ represents “window”) if $w=x_{1}\cdot x_{2}\cdots$ and
$w^{\prime}=y_{1}\cdot y_{2}\cdots$ where for all $i\geq 1$ we have
$|x_{i}|=|y_{i}|=k$ and $x_{i}\sim y_{i}$. That is, $w^{\prime}$ can be
obtained from $w$ by permuting contiguous disjoint windows of size $k$ in $w$.
Note that if $w\sim_{k\boxplus}w^{\prime}$ then in particular $w\sim
w^{\prime}$, but the former is much more restrictive.

####  2.0.3 Semilinear Sets

Let $\mathbb{N}=\\{0,1,\ldots\\}$ be the natural numbers. For dimension $d\geq
1$, we denote vectors in $\mathbb{N}^{d}$ in bold (e.g.,
$\vec{p}\in\mathbb{N}^{d}$). Consider a vector $\vec{b}\in\mathbb{N}^{d}$ and
$P\subseteq\mathbb{N}^{d}$, the _linear set_ generated by the _base_ $\vec{b}$
and _periods_ $P$ is

$\mathrm{Lin}(\vec{b},P)=\\{\vec{b}+\sum_{\vec{p}\in
P}\lambda_{p}\vec{p}\mid\vec{b}\in\mathbb{N}^{d}\text{ and
}\lambda_{p}\in\mathbb{N}\text{ for all }\vec{p}\in P\\}$

A _semilinear set_ is then $\bigcup_{i\in I}\mathrm{Lin}(\vec{b_{i}},P_{i})$
for a finite set $I$ and pairs $(\vec{b_{i}},P_{i})$.

Semilinear sets are closely related to the Parikh image of regular languages
(in that the Parikh image of a regular language is semilinear) [21]. We will
cite specific results relating to this connection as we use them.

####  2.0.4 Jumping Automata

Consider an automaton
$\mathcal{A}=\langle\Sigma,Q,\delta,Q_{0},\alpha\rangle$. Over finite words,
we view $\mathcal{A}$ as a _jumping automaton_ by letting it read its input in
a non-sequential way, i.e. “jump” between letters as long as all letters are
read exactly once. Formally, $\mathcal{A}$ accepts a word $w$ as a jumping
automaton if it accepts some permutation of $w$. Thus, we define the _jumping
language_ of $\mathcal{A}$ to be

$\mathfrak{J}_{\text{fin}}(\mathcal{A})=\\{w\in\Sigma^{*}\mid\exists
w^{\prime}\sim w\text{ such that
}w^{\prime}\in\mathfrak{L}_{\text{fin}}(\mathcal{A})\\}$

We now turn to define jumping automata over infinite words. As discussed in
Section 1, we consider three jumping semantics for $\mathcal{A}$, as follows:

###### Definition 1

Consider an automaton
$\mathcal{A}=\langle\Sigma,Q,\delta,Q_{0},\alpha\rangle$.

  * •

Its _Jumping language_ is:
$\mathfrak{J}(\mathcal{A})=\\{w\in\Sigma^{\omega}\mid\exists w^{\prime}\sim
w\text{ such that }w^{\prime}\in\mathfrak{L}(\mathcal{A})\\}$.

  * •

For $k\in\mathbb{N}$, its _$k$ -window Jumping language_ is:
$\mathfrak{J}_{k\boxplus}(\mathcal{A})=\\{w\in\Sigma^{\omega}\mid\exists
w^{\prime}\sim_{k\boxplus}w\text{ such that
}w^{\prime}\in\mathfrak{L}(\mathcal{A})\\}$.

  * •

Its _$\exists$ -window Jumping language_ is:
$\mathfrak{J}_{\exists\boxplus}(\mathcal{A})=\\{w\in\Sigma^{\omega}\mid\exists
k\in\mathbb{N}\wedge\exists w^{\prime}\sim_{k\boxplus}w\text{ such that
}w^{\prime}\in\mathfrak{L}(\mathcal{A})\\}$.

###### Remark 2

For jumping automata over finite words, the model is sometimes defined by
allowing the transition function of the automaton to “jump” to any letter in
the input and consume it [20]. For infinite words, this definition does not
capture the (arguably) correct notion of jumping automata, since an automaton
could skip letters without ever returning to them, e.g., for input
$(ab)^{\omega}$ read only $a^{\omega}$ by jumping over all the $b$’s. Under
our definition, the latter is not allowed, since
$a^{\omega}\not\sim(ab)^{\omega}$. Clearly, however, one can still obtain our
“Jumping” definition by considering permutations of words, rather than a
jumping reading head.

##  3 Jumping Languages

In this section we study the properties of $\mathfrak{J}(\mathcal{A})$ for an
automaton $\mathcal{A}$. We start by characterizing
$\mathfrak{J}(\mathcal{A})$ using an extension of semilinear sets.

###  3.1 Jumping Languages and Masked Semilinear Sets

Recall that
$\mathbb{M}^{\Sigma}=\mathbb{N}_{\infty}^{\Sigma}\setminus\mathbb{N}^{\Sigma}$
and consider a vector $\vec{v}\in\mathbb{M}^{\Sigma}$. We separate the
$\infty$ coordinates of $\vec{v}$ from the finite ones by, intuitively,
writing $\vec{v}$ as a sum of a vector in $\mathbb{N}^{\Sigma}$ and a vector
from $\\{0,\infty\\}^{\Sigma}\setminus\\{\vec{0}\\}$. Formally, let
$\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}=\\{0,\infty\\}^{\Sigma}\setminus\\{\vec{0}\\}$ be the set of
_masks_ , namely vectors with entries $0$ and $\infty$ that are not all $0$,
we refer to each $\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}$ as a _mask_. We denote by
$\mathfrak{m}|_{0}=\\{\sigma\in\Sigma\mid\mathfrak{m}(\sigma)=0\\}$ and
$\mathfrak{m}|_{\infty}=\\{\sigma\in\Sigma\mid\mathfrak{m}(\sigma)=\infty\\}$
the 0 and $\infty$ coordinates of $\mathfrak{m}$, respectively.

For $\vec{x}\in\mathbb{N}^{\Sigma}$ and
$\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-twemojis.pdf}$ let
$\vec{x}\oplus\mathfrak{m}\in\mathbb{M}^{\Sigma}$ be the vector such that for
all $\sigma\in\Sigma$ $(\vec{x}+\mathfrak{m})_{\sigma}=\vec{x}_{\sigma}$ if
$\sigma\in\mathfrak{m}|_{0}$ and $(\vec{x}+\mathfrak{m})_{\sigma}=\infty$ if
$\sigma\in\mathfrak{m}|_{\infty}$. Note that every
$\vec{v}\in\mathbb{M}^{\Sigma}$ can be written as $\vec{x}+\mathfrak{m}$ where
$\vec{x}$ is obtained from $\vec{v}$ be replacing $\infty$ with 0 (or indeed
with any number), and having $\mathfrak{m}$ match the $\infty$ coordinates of
$\vec{v}$.

We now augment semilinear sets with masks. A _masked semilinear set_ is a
union of the form
$S=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}+\mathfrak{m}$ where $S_{\mathfrak{m}}$ is a
semilinear set for every $\mathfrak{m}$. We also interpret $S$ as a subset of
$\mathbb{M}^{\Sigma}$ by interpreting addition as adding $\mathfrak{m}$ to
each vector in the set $S_{\mathfrak{m}}$. Note that the union above is
disjoint, since adding distinct masks always results in distinct vectors.

Consider a mask $\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}$. Two vectors $\vec{u},\vec{v}\in\mathbb{N}^{\Sigma}$ are called
_$\mathfrak{m}$ -equivalent_ if $\vec{u}+\mathfrak{m}=\vec{v}+\mathfrak{m}$
(i.e., if they agree on $\mathfrak{m}|_{0}$). We say that a semilinear set
$R\subseteq\mathbb{N}^{\Sigma}$ is _$\mathfrak{m}$ -oblivious_ if for every
$\mathfrak{m}$-equivalent vectors $\vec{u},\vec{v}$ we have $\vec{u}\in
R\iff\vec{v}\in R$. Intuitively, an $\mathfrak{m}$-oblivious set does not
“look” at $\mathfrak{m}|_{\infty}$.

We say that the masked semilinear set $S$ above is _oblivious_ if every
$S_{\mathfrak{m}}$ is $\mathfrak{m}$-oblivious. Note that the property of
being oblivious refers to a specific representation of $S$ with semilinear
sets $S_{\mathfrak{m}}$ for every mask $\mathfrak{m}$. In a way, it is natural
for a masked semilinear set to be oblivious, since semantically, adding
$\mathfrak{m}$ to a vector in $S_{\mathfrak{m}}$ already ignores the $\infty$
coordinates of $\mathfrak{m}$, so $S_{\mathfrak{m}}$ should not “care” about
them. Moreover, if a set $S_{\mathfrak{m}}$ is $\mathfrak{m}$-oblivious, then
in each of its linear components we can, intuitively, partition its period
vectors to two types: those that have $0$ in all the masked coordinates, and
the remaining vectors that allow attaining any value in the masked
coordinates. We refer to this as a _canonical $\mathfrak{m}$-oblivious
representation_, as follows.

###### Definition 2

A semilinear set $R\subseteq\mathbb{N}^{\Sigma}$ is in _canonical
$\mathfrak{m}$-oblivious form_ for a mask $\mathfrak{m}$ if
$R=\bigcup_{i=1}^{k}\mathrm{Lin}(\vec{b_{i}},P_{i})$ such that for every
$1\leq i\leq k$ we have $P_{i}=Q_{i}\cup E_{\mathfrak{m}}$ with the following
conditions:

  * •

$\vec{b_{i}}(\sigma)=0$ for every $\sigma\in\mathfrak{m}|_{\infty}$.

  * •

$\vec{p}(\sigma)=0$ for every $p\in Q_{i}$ and
$\sigma\in\mathfrak{m}|_{\infty}$.

  * •

$E_{\mathfrak{m}}=\\{\vec{e_{\sigma}}\mid\sigma\in\mathfrak{m}|_{\infty}\\}$
with $\vec{e_{\sigma}}(\tau)=1$ if $\sigma=\tau$ and $0$ otherwise.

We now show that every masked semilinear set can be translated to an
equivalent one in canonical oblivious form (see example in Fig. 1).

$\mathrm{Lin}\left(\begin{pmatrix}1\\\ 0\\\ \vec{9}\\\
\vec{4}\end{pmatrix},\left\\{\begin{pmatrix}1\\\ 2\\\ \vec{5}\\\
\vec{7}\end{pmatrix},\begin{pmatrix}1\\\ 0\\\ \vec{1}\\\
\vec{3}\end{pmatrix}\right\\}\right)+\begin{pmatrix}0\\\ 0\\\ \infty\\\
\infty\end{pmatrix}$ $\rightsquigarrow$$\mathrm{Lin}\left(\begin{pmatrix}1\\\
0\\\ 0\\\ 0\end{pmatrix},\left\\{\begin{pmatrix}1\\\ 2\\\ 0\\\
0\end{pmatrix},\begin{pmatrix}1\\\ 0\\\ 0\\\
0\end{pmatrix},\begin{pmatrix}0\\\ 0\\\ 1\\\
0\end{pmatrix},\begin{pmatrix}0\\\ 0\\\ 0\\\
1\end{pmatrix}\right\\}\right)+\begin{pmatrix}0\\\ 0\\\ \infty\\\
\infty\end{pmatrix}$ Figure 1: On the left, a masked semilinear set (actually
linear), and on the right an equivalent oblivious canonical form. The bold
numbers on the left get masked away, so are replaced by $0$.

###### Lemma 1

Consider a masked semilinear set
$S=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}+\mathfrak{m}$. Then there exists an oblivious
masked semilinear set
$T=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}T_{\mathfrak{m}}+\mathfrak{m}$ that represents the same subset
of $\mathbb{M}^{\Sigma}$, and every $T_{\mathfrak{m}}$ is in canonical
$\mathfrak{m}$-oblivious form.

###### Proof

Intuitively, we obtain the oblivious representation by adding to each
$S_{\mathfrak{m}}$ vectors where the $\infty$-coordinates of $\mathfrak{m}$
can take any value.

Formally, for every mask
$\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-twemojis.pdf}$
define

$T_{\mathfrak{m}}=\\{\vec{v}\in\mathbb{N}^{\Sigma}\mid\exists\vec{u}\in
S_{\mathfrak{m}}\text{ such that
}\vec{u}+\mathfrak{m}=\vec{v}+\mathfrak{m}\\}$

That is, $T_{\mathfrak{m}}$ is obtained from $S_{\mathfrak{m}}$ by including
every vector that is $\mathfrak{m}$-equivalent to some vector in
$S_{\mathfrak{m}}$.

By construction, we have that $T_{\mathfrak{m}}$ is $\mathfrak{m}$-oblivious.
Moreover, it is easy to see that
$S_{\mathfrak{m}}+\mathfrak{m}=T_{\mathfrak{m}}+\mathfrak{m}$. Indeed,
$S_{\mathfrak{m}}\subseteq T_{\mathfrak{m}}$, thus giving one containment, and
for every $\vec{x}\in T_{\mathfrak{m}}+\mathfrak{m}$, write
$\vec{x}=\vec{v}+\mathfrak{m}$ for some $\vec{v}\in T_{\mathfrak{m}}$, then
there exists some $\vec{u}\in S_{\mathfrak{m}}$ with
$\vec{v}+\mathfrak{m}=\vec{u}+\mathfrak{m}\in S_{\mathfrak{m}}+\mathfrak{m}$.

It remains to show that $T_{\mathfrak{m}}$ is semilinear and represent it in
canonical form. To this end, for every vector $\vec{p}\in\mathbb{N}^{\Sigma}$,
define $\vec{p}|_{\mathfrak{m}}$ by
$\vec{p}|_{\mathfrak{m}}(\sigma)=\vec{p}(\sigma)$ if
$\sigma\in\mathfrak{m}|_{0}$ and $\vec{p}|_{\mathfrak{m}}(\sigma)=0$ if
$\sigma\in\mathfrak{m}|_{\infty}$. That is, we replace all the $\infty$
coordinates of $\mathfrak{m}$ in $\vec{p}$ by $0$. We lift this to sets of
vectors: for a set $P$, let
$P|_{\mathfrak{m}}=\\{\vec{p}|_{\mathfrak{m}}\mid\vec{p}\in P\\}$.

Now, write $S_{\mathfrak{m}}=\bigcup_{i\in I}\mathrm{Lin}(\vec{b_{i}},P_{i})$,
we claim the following:

$T_{\mathfrak{m}}=\bigcup_{i\in
I}\mathrm{Lin}(\vec{b_{i}}|_{\mathfrak{m}},P_{i}|_{\mathfrak{m}}\cup
E_{\mathfrak{m}})$

That is, $T_{\mathfrak{m}}$ is obtained by zeroing the $\infty$ coordinates of
$\mathfrak{m}$ in $S_{\mathfrak{m}}$, and then arbitrarily adding numbers in
these coordinates, using $\vec{e_{\sigma}}\in E_{\mathfrak{m}}$ (as per
Definition 2).

Let $\vec{v}\in T_{\mathfrak{m}}$, then there exists $\vec{u}\in
S_{\mathfrak{m}}$ such that $\vec{v}+\mathfrak{m}=\vec{u}+\mathfrak{m}$. That
is, $\vec{u}(\sigma)=\vec{v}(\sigma)$ for all $\sigma\in\mathfrak{m}|_{0}$.
Since $\vec{u}\in S_{\mathfrak{m}}$, we can write
$\vec{u}=\vec{b_{i}}+\lambda_{1}p_{1}+\ldots+\lambda_{k}p_{k}$ for some $i\in
I$, $p_{1},\ldots,p_{k}\in P_{i}$ and
$\lambda_{1},\ldots,\lambda_{k}\in\mathbb{N}$. It then follows that

$\vec{v}=\vec{b_{i}}|_{\mathfrak{m}}+\lambda_{1}p_{1}|_{\mathfrak{m}}+\ldots+\lambda_{k}p_{k}|_{\mathfrak{m}}+\sum_{\sigma\in\mathfrak{m}|_{\infty}}\vec{v}(\sigma)\vec{e_{\sigma}}$

and the latter form is in
$\mathrm{Lin}(\vec{b_{i}}|_{\mathfrak{m}},P_{i}|_{\mathfrak{m}}\cup
E_{\mathfrak{m}})$.

Conversely, let
$\vec{v}\in\mathrm{Lin}(\vec{b_{i}}|_{\mathfrak{m}},P_{i}|_{\mathfrak{m}}\cup
E_{\mathfrak{m}})$, and write

$\vec{v}=\vec{b_{i}}|_{\mathfrak{m}}+\lambda_{1}p_{1}|_{\mathfrak{m}}+\ldots+\lambda_{k}p_{k}|_{\mathfrak{m}}+\sum_{\sigma\in\mathfrak{m}|_{\infty}}\beta_{\sigma}\vec{e_{\sigma}}$

Define $\vec{u}=\vec{b_{i}}+\lambda_{1}p_{1}+\ldots+\lambda_{k}p_{k}$, then
$\vec{u}\in S_{\mathfrak{m}}$ and $\vec{u}+\mathfrak{m}=\vec{v}+\mathfrak{m}$
(since the only coordinates where $\vec{v}$ differs from $\vec{u}$ are those
in $\mathfrak{m}|_{\infty}$), so $\vec{v}\in T_{\mathfrak{m}}$, and we are
done.

We conclude by defining
$T=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}T_{\mathfrak{m}}+\mathfrak{m}$, which is an oblivious masked
semilinear set in canonical form, as required. ∎

######  Complexity Analysis 3.1 (of Lemma 1)

The description of $T$ involves introducing at most $|\Sigma|$ vectors to the
periods of each semilinear set, and changing some entries to $0$ in the
existing vectors. Thus, the description of $T$ is of polynomial size in that
of $S$.

Our main result in this section is that the Parikh images of jumping languages
coincide with masked semilinear sets. We prove this in the following lemmas.

###### Lemma 2

Let $\mathcal{A}$ be an automaton, then $\Psi(\mathfrak{J}(\mathcal{A}))$ is a
masked semilinear set. Moreover, we can effectively compute a representation
of it from that of $\mathcal{A}$.

###### Proof

Consider $\mathcal{A}=\langle\Sigma,Q,\delta,Q_{0},\alpha\rangle$. By
Definition 1 we have that
$\Psi(\mathfrak{J}(\mathcal{A}))=\Psi(\mathfrak{L}(\mathcal{A}))$. Indeed,
both sets contain exactly the Parikh images of words in
$\mathfrak{L}(\mathcal{A})$. Recall (or see Section 0.A.1) that every
$\omega$-regular language can be (effectively) written as a union of the form
$\mathfrak{L}(\mathcal{A})=\bigcup_{i=1}^{m}S_{i}\cdot T_{i}^{\omega}$ where
$S_{i},T_{i}\subseteq\Sigma^{*}$ are regular languages over finite words.

Intuitively, we will show that $\Psi(T_{i}^{\omega})$ can be separated to
letters that are seen finitely often, and those that are seen infinitely
often, where the latter will induce the mask. To this end, for every
$\emptyset\neq\Gamma\subseteq\Sigma^{*}$ define
$\mathfrak{m}_{\Gamma}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}$ by setting $\mathfrak{m}_{\Gamma}(\sigma)=\infty$ if
$\sigma\in\Gamma$ and $\mathfrak{m}_{\Gamma}(\sigma)=0$ if
$\sigma\notin\Gamma$. Now, for every regular language $T_{i}$ in the union
above define

$I(T_{i})=\\{\mathfrak{m}_{\Gamma}\mid\forall\sigma\in\Gamma\ \exists w\in
T_{i}\cap\Gamma^{*}\text{ s.t. }\Psi(w)(\sigma)>0\\}$

That is, $I(T_{i})$ is the set of masks $\mathfrak{m}_{\Gamma}$ such that
every letter in $\Gamma$ occurs in some word in $T_{i}$ that contains only
letters from $\Gamma$. Intuitively, $\mathfrak{m}_{\Gamma}\in I(T_{i})$ can be
attained by an infinite concatenation of words from $T_{i}$ by covering all
letters in $\Gamma$ whilst not using letters outside of $\Gamma$.

We now claim that for every $1\leq i\leq m$ it holds that $\Psi(S_{i}\cdot
T_{i}^{\omega})=\Psi(S_{i}\cdot T_{i}^{*})+I(T_{i})$. To reduce clutter, we
drop the subscript $i$ for this proof. Consider $\vec{v}\in\Psi(S\cdot
T^{\omega})$, then there exists a word $w=x_{1}x_{2}\cdots$ such that
$\Psi(w)=\vec{v}$ with $x_{1}\in S$ and $x_{j}\in T$ for all $j>1$. Let
$\Gamma$ be the set of letters that occur infinitely often in $w$, and let
$N_{0}\geq 2$ be such that for all $n\geq N_{0}$ we have $x_{n}\in\Gamma^{*}$.
Observe that $\mathfrak{m}_{\Gamma}\in I(T)$ since for every $\sigma\in\Gamma$
there exists some word $x_{j}\in T_{i}\cap\Gamma^{*}$ (for $j\geq N_{0}$) such
that $\sigma$ occurs in $x_{j}$. Thus,
$\Psi(x_{N_{0}}x_{N_{0}+1}\cdots)=\mathfrak{m}_{\Gamma}$. Moreover,
$x_{1}\cdots x_{N_{0}-1}\in S\cdot T^{*}$, so
$\vec{v}=\Psi(w)=\Psi(x_{1}\cdots
x_{N_{0}-1})+\mathfrak{m}_{\Gamma}\in\Psi(S\cdot T^{*})+I(T)$.

Conversely, let $\vec{v}\in\Psi(S\cdot T^{*})+I(T)$, then there exist $y\in
S\cdot T^{*}$ and $\mathfrak{m}_{\Gamma}\in I(T)$ for some
$\Gamma\subseteq\Sigma$ such that $\vec{v}=\Psi(y)+\mathfrak{m}_{\Gamma}$.
Since $\mathfrak{m}_{\Gamma}\in I(T)$, there exists a set of words
$\\{z_{1},\ldots,z_{r}\\}\subseteq T\cap\Gamma^{*}$ such that every
$\sigma\in\Gamma$ occurs in some word in this set. We thus have
$\Psi((z_{1}\cdots z_{r})^{\omega})=\mathfrak{m}_{\Gamma}$ and $(z_{1}\cdots
z_{r})^{\omega}\in T^{\omega}$, so $y\cdot(z_{1}\cdots z_{r})^{\omega}\in
S\cdot T^{\omega}$ and we have
$\vec{v}=\Psi(y)+\mathfrak{m}_{\Gamma}=\Psi(y\cdot(z_{1}\cdots
z_{r})^{\omega})\in\Psi(S\cdot T^{\omega})$, concluding our claim.

It follows that
$\Psi(\mathfrak{J}(\mathcal{A}))=\bigcup_{i=1}^{k}\Psi(S_{i}\cdot
T_{i}^{*})+I(T_{i})$. We can now rearrange the sum by masks instead of by
index $i$: for every mask
$\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-twemojis.pdf}$
write $S_{\mathfrak{m}}=\bigcup_{i:\mathfrak{m}\in I(T_{i})}\Psi(S_{i}\cdot
T_{i}^{*})$ (note that $S_{\mathfrak{m}}$ could be empty). Since $S_{i}\cdot
T_{i}^{*}$ is a regular language, then by Parikh’s theorem [21] its Parikh
image is semilinear, so $S_{\mathfrak{m}}$ is semilinear. Thus,
$\Psi(\mathfrak{J}(\mathcal{A}))=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}+\mathfrak{m}$ is a masked semilinear set. ∎

######  Complexity Analysis 3.2 (of Lemma 2)

Writing $\mathfrak{L}(\mathcal{A})$ as a union involves only a polynomial
blowup (see Section 0.A.1). Then, we split the resulting expression to a union
over $2^{|\Sigma|}$ masks. Within the union, we convert a nondeterministic
automaton for $S_{i}\cdot T_{i}^{*}$ to a semilinear set. By [23, Theorem 4.1]
(also [15]), the resulting semilinear set has description size polynomial in
the number of states $n$ of $\mathcal{A}$ and singly-exponential in
$|\Sigma|$. Moreover, the translation can be computed in time
$2^{O(|\Sigma|^{2}\log(n|\Sigma|))}$.

For the converse direction, we present a stronger result, namely that we can
construct a _deterministic_ automaton to capture a masked semilinear set.

###### Lemma 3

Consider a masked semilinear set $S$, then there exists a deterministic
automaton $\mathcal{A}$ such that $\Psi(\mathfrak{J}(\mathcal{A}))=S$.

###### Proof

By Lemma 1, we can assume
$S=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}+\mathfrak{m}$ and that every $S_{\mathfrak{m}}$
is in canonical $\mathfrak{m}$-oblivious form. Let
$\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-twemojis.pdf}$ and
write $S_{\mathfrak{m}}=\bigcup_{i=1}^{k}\mathrm{Lin}(\vec{b_{i}},P_{i}\cup
E_{\mathfrak{m}})$ as per Definition 2. Consider a linear set
$L=\mathrm{Lin}(\vec{b},P\cup E_{\mathfrak{m}})$ in the union above, and we
omit the subscript $i$ for brevity. We start by constructing a deterministic
automaton $\mathcal{D}$ such that
$\Psi(\mathfrak{J}_{\text{fin}}(\mathcal{D}))=L$. To this end, let
$w_{\vec{b}}\in\Sigma^{*}$ be a word such that $\Psi(w_{\vec{b}})=\vec{b}$ and
similarly for every $\vec{p}\in P$ let $w_{\vec{p}}\in\Sigma^{*}$ such that
$\Psi(w_{\vec{p}})=\vec{p}$. Note that $\Psi(\sigma)=\vec{e_{\sigma}}$ for
every $\sigma\in\mathfrak{m}|_{\infty}$.

Let $\mathcal{D}^{\prime}$ be a deterministic automaton for the regular
expression $w_{\vec{b}}\cdot(w_{\vec{p_{1}}}+\ldots+w_{\vec{p_{n}}})^{*}$
where $P=\\{\vec{p_{1}},\ldots,\vec{p_{n}}\\}$. Next, let
$w_{E}=\sigma_{1}\cdots\sigma_{k}$ be a word obtained by concatenating all the
letters in $\mathfrak{m}|_{\infty}$ in some order. We obtain $\mathcal{D}$
from $\mathcal{D}^{\prime}$ by connecting every accepting state of
$\mathcal{D}^{\prime}$, upon reading $\sigma_{1}$, to a cycle that allows
reading $w_{E}^{\omega}$. The accepting states of $\mathcal{D}$ are those on
the $w_{E}$ cycle. Crucially, the transition from $\mathcal{D}^{\prime}$ upon
reading $\sigma_{1}$ retains determinism, since $P$ is in canonical form, and
therefore $\vec{p}(\sigma_{1})=0$ for every $\vec{p}\in P$. That is, the
letter $\sigma_{1}$ is not seen in any transition of $\mathcal{D}^{\prime}$,
allowing us to use it in the construction of $\mathcal{D}$. The construction
is demonstrated in Fig. 2.

$a$$a$$b$$a$$b$$c$$d$$c$ Figure 2: The automaton $\mathcal{D}$ for the linear
set from Fig. 1 (over $\Sigma=\\{a,b,c,d\\}$), with the representative words
$w_{\vec{b}}=a$ and $\\{bab,a,c,d\\}$ for the period. The blue (dashed) parts
are the addition of $w_{E}$ and change of accepting states to obtain
$\mathcal{D}$ from $\mathcal{D}^{\prime}$.

By construction, we have that
$\mathfrak{L}(\mathcal{D})=w_{\vec{b}}\cdot(w_{\vec{p_{1}}}+\ldots+w_{\vec{p_{n}}})^{*}\cdot
w_{E}^{\omega}$. Since $\Psi(w_{E}^{\omega})=\mathfrak{m}$, we now have

$\Psi(\mathfrak{J}(\mathcal{D}))=\Psi(\mathfrak{L}(\mathcal{D}))=\Psi(w_{\vec{b}}\cdot(w_{\vec{p_{1}}}+\ldots+w_{\vec{p_{n}}})^{*}\cdot
w_{E}^{\omega})=\mathrm{Lin}(\vec{b},P)+\mathfrak{m}=L+\mathfrak{m}$

where the last equality is because adding $\mathfrak{m}$ to a vector in $L$
masks any addition of vectors in $E_{\mathfrak{m}}$ by $\infty$.

Next, we observe that for two deterministic automata
$\mathcal{D}_{1},\mathcal{D}_{2}$, we can construct a deterministic automaton
$\mathcal{D}_{3}$ such that
$\mathfrak{J}(\mathcal{D}_{3})=\mathfrak{J}(\mathcal{D}_{1})\cup\mathfrak{J}(\mathcal{D}_{2})$.
Indeed, the standard product construction (where the accepting states are
pairs of states where either $\mathcal{D}_{1}$ or $\mathcal{D}_{2}$ accept)
preserves determinism. Thus, we can take products to first capture
$S_{\mathfrak{m}}=\bigcup_{i=1}^{k}\mathrm{Lin}(\vec{b_{i}},P_{i}\cup
E_{\mathfrak{m}})$ and then
$S=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}+\mathfrak{m}$, as desired. ∎

######  Complexity Analysis 3.3 (of Lemma 3)

We can naively construct an automaton for the regular expression
$w_{\vec{b}}\cdot(w_{\vec{p_{1}}}+\ldots+w_{\vec{p_{n}}})^{*}$ of size
$\|\mathrm{Lin}(\vec{b},P)\|=\|\vec{b}\|+\sum_{i=1}^{n}\|\vec{p_{i}}\|$, where
e.g., $\|\vec{b}\|$ is the sum of entries in $\vec{b}$ (i.e., unary
representation). Then, determinization can yield a DFA of size singly
exponential. Then, we take unions by the product construction, where the
number of copies corresponds to the number of linear sets in $S$, and then to
$2^{|\Sigma|}-1$ many masks. This results in a DFA of size singly exponential
in the size of $S$ and doubly-exponential in $|\Sigma|$ (assuming $S$ is
represented in unary). Finally, adding the cycle for the mask adds at most
$2^{O(|\Sigma|)}$ states (both to a deterministic or nondeterministic
automaton).

Combining Lemmas 2 and 3 we have the following.

###### Theorem 3.4

A set $S$ is a masked semilinear set if and only if there exists an automaton
$\mathcal{A}$ such that $S=\Psi(\mathfrak{J}(\mathcal{A}))$.

###  3.2 Jumping Languages – Closure Properties

Using the characterizations obtained in Section 3.1, we can now obtain several
closure properties of jumping languages. First, we remark that jumping
languages are clearly closed under union, by taking the union of the automata
and nondeterministically choosing which one to start at. We proceed to tackle
intersection and complementation.

Note that the standard intersection construction of Büchi automata does not
capture the intersection of jumping languages, as demonstrated in Fig. 3.

$\mathcal{A}$:$q_{0}$$q_{1}$$a$$b$

$\mathcal{B}$:$s_{0}$$s_{1}$$a$$b$

Figure 3: The automata $\mathcal{A}$ and $\mathcal{B}$ satisfy
$\mathfrak{L}(\mathcal{A})=\\{(ab)^{\omega}\\}$ and
$\mathfrak{L}(\mathcal{B})=\\{(ba)^{\omega}\\}$. Thus,
$\mathfrak{J}(\mathcal{A})=\mathfrak{J}(\mathcal{B})=\\{w\in\Sigma^{\omega}\mid
w\text{ has infinitely many $a$'s and $b$'s}\\}$. However, if we start by
taking the standard intersection of $\mathcal{A}$ and $\mathcal{B}$, we would
end up with the empty language.

###### Proposition 1

Let $\mathcal{A}$ and $\mathcal{B}$ be automata, then we can effectively
construct an automaton $\mathcal{C}$ such that
$\mathfrak{J}(\mathcal{C})=\mathfrak{J}(\mathcal{A})\cap\mathfrak{J}(\mathcal{B})$.

###### Proof

Consider a word $w\in\Sigma^{\omega}$, and observe that
$w\in\mathfrak{J}(\mathcal{A})\cap\mathfrak{J}(\mathcal{B})$ if and only if
$\Psi(w)\in\Psi(\mathfrak{J}(\mathcal{A}))\cap\Psi(\mathfrak{J}(\mathcal{B}))$.
Thus, it suffices to prove that there exists automaton $\mathcal{C}$ such that
$\Psi(\mathfrak{J}(\mathcal{C}))=\Psi(\mathfrak{J}(\mathcal{A}))\cap\Psi(\mathfrak{J}(\mathcal{B}))$.
By Theorem 3.4 we can write
$\Psi(\mathfrak{J}(\mathcal{A}))=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}+\mathfrak{m}$ and
$\Psi(\mathfrak{J}(\mathcal{B}))=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}T_{\mathfrak{m}}+\mathfrak{m}$. Furthermore, by Lemma 1 we can
assume that these are oblivious masked semilinear sets.

We claim that
$\Psi(\mathfrak{J}(\mathcal{A}))\cap\Psi(\mathfrak{J}(\mathcal{B}))=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}\cap T_{\mathfrak{m}}+\mathfrak{m}$. That is, we
can take intersection by intersecting each pair of semilinear sets, while
keeping the masks. Intuitively, this holds because every word uniquely
determines the mask it can use to join the union, so intersecting the unions
amounts (using obliviousness) to intersecting the set of finite-valued vectors
corresponding to the finite parts of the Parikh images of words in the
language.

Indeed, let
$\vec{x}\in\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}\cap T_{\mathfrak{m}}+\mathfrak{m}$, then there
exists $\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}$ and $\vec{v}\in S_{\mathfrak{m}}\cap T_{\mathfrak{m}}$ such
that $\vec{x}=\vec{v}+\mathfrak{m}$. In particular,
$\vec{v}+\mathfrak{m}\in\Psi(\mathfrak{J}(\mathcal{A}))$ and
$\vec{v}+\mathfrak{m}\in\Psi(\mathfrak{J}(\mathcal{B}))$, so
$\vec{x}=\vec{v}+\mathfrak{m}\in\Psi(\mathfrak{J}(\mathcal{A}))\cap\Psi(\mathfrak{J}(\mathcal{B}))$.

Conversely, let
$\vec{x}\in\Psi(\mathfrak{J}(\mathcal{A}))\cap\Psi(\mathfrak{J}(\mathcal{B}))$.
Recall that $\vec{x}$ uniquely defines a mask $\mathfrak{m}$, so there exist
$\vec{u}\in S_{\mathfrak{m}}$, $\vec{v}\in T_{\mathfrak{m}}$ such that
$\vec{x}=\vec{u}+\mathfrak{m}=\vec{v}+\mathfrak{m}$. It follows that $\vec{u}$
and $\vec{v}$ are $\mathfrak{m}$-equivalent. Since $S_{\mathfrak{m}}$ and
$T_{\mathfrak{m}}$ are $\mathfrak{m}$-oblivious, we also have that $\vec{v}\in
S_{\mathfrak{m}}$ and $\vec{u}\in T_{\mathfrak{m}}$. In particular,
$\vec{v}\in S_{\mathfrak{m}}\cap T_{\mathfrak{m}}$ so
$\vec{x}=\vec{v}+\mathfrak{m}\in\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}\cap T_{\mathfrak{m}}+\mathfrak{m}$.

Finally, semilinear sets are closed under intersection [3, 7]. Thus,
$S_{\mathfrak{m}}\cap T_{\mathfrak{m}}$ is semilinear for every
$\mathfrak{m}$, so
$\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}\cap T_{\mathfrak{m}}+\mathfrak{m}$ is a
semilinear masked set and from Lemma 3 there exists an automaton $\mathcal{C}$
such that
$\mathfrak{J}(\mathcal{C})=\mathfrak{J}(\mathcal{A})\cap(\mathfrak{J}(\mathcal{B})$.
∎

######  Complexity Analysis 3.5 (of Proposition 1)

The description size of the intersection of semilinear sets is polynomial in
the description size of the entries of the vectors and the size of the union,
and singly exponential in $|\Sigma|$ [3, 7]. Since the blowup in Lemmas 2 and
1 is polynomial, then the only significant blowup is Lemma 3, due to the
construction of an automaton whose size is exponential in $|\Sigma|$. However,
it is not hard to see that the two exponential blowups in $|\Sigma|$ are
orthogonal, and can be merged to a singly-exponential blowup.

###### Proposition 2

Consider an automaton $\mathcal{A}$. There exists an automaton $\mathcal{B}$
such that
$\mathfrak{J}(\mathcal{B})=\Sigma^{\omega}\setminus\mathfrak{J}(\mathcal{A})$.

###### Proof

Observe that $w\in\Sigma^{\omega}\setminus\mathfrak{J}(\mathcal{A})$ if and
only if
$\Psi(w)\in\mathbb{M}^{\Sigma}\setminus\Psi(\mathfrak{J}(\mathcal{A}))$.
Indeed, $w\in\Sigma^{\omega}\setminus\mathfrak{J}(\mathcal{A})$ means that
every permutation of $w$ is not accepted by $\mathcal{A}$, i.e., the Parikh
image of $w$ is not a Parikh image of any word accepted by $\mathcal{A}$.
Thus, it suffices to construct $\mathcal{B}$ such that
$\Psi(\mathfrak{J}(\mathcal{B}))=\mathbb{M}^{\Sigma}\setminus\Psi(\mathfrak{J}(\mathcal{A}))$.

By Theorem 3.4, we can write
$\Psi(\mathfrak{J}(\mathcal{A}))=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}+\mathfrak{m}$. Moreover, by Lemma 1 we can
assume that this is an oblivious masked semilinear set. We claim that
$\mathbb{M}^{\Sigma}\setminus\Psi(\mathfrak{J}(\mathcal{A}))=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}(\mathbb{N}^{\Sigma}\setminus S_{\mathfrak{m}})+\mathfrak{m}$.
That is, we can complement the union by complementing each semilinear set,
while keeping the masks.

To show this, consider a word $w\in\Sigma^{\omega}$ and write
$\Psi(w)=\vec{x_{w}}+\mathfrak{m}_{w}$ where
$\vec{x_{w}}\in\mathbb{N}^{\Sigma}$, as per Section 3.1.

For the first direction, assume
$\vec{x_{w}}+\mathfrak{m}_{w}\in\mathbb{M}^{\Sigma}\setminus\Psi(\mathfrak{J}(\mathcal{A}))$,
then
$\vec{x_{w}}+\mathfrak{m}_{w}\notin\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}+\mathfrak{m}$. In particular,
$\vec{x_{w}}\notin S_{\mathfrak{m}_{w}}$ (otherwise we would have
$\vec{x_{w}}+\mathfrak{m}_{w}\in S_{\mathfrak{m}_{w}}+\mathfrak{m}_{w}$, which
is part of the union). It follows that
$\vec{x_{w}}+\mathfrak{m}_{w}\in(\mathbb{N}^{\Sigma}\setminus
S_{\mathfrak{m}_{w}})+\mathfrak{m}_{w}$, so
$\Psi(w)\in\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}(\mathbb{N}^{\Sigma}\setminus S_{\mathfrak{m}})+\mathfrak{m}$.

Conversely, assume
$\Psi(w)=\vec{x_{w}}+\mathfrak{m}_{w}\in\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}(\mathbb{N}^{\Sigma}\setminus S_{\mathfrak{m}})+\mathfrak{m}$,
then observe that
$\vec{x_{w}}+\mathfrak{m}_{w}\in(\mathbb{N}^{\Sigma}\setminus
S_{\mathfrak{m}_{w}})+\mathfrak{m}_{w}$. Indeed, no other part of the union
has the mask $\mathfrak{m}_{w}$. Assume by way of contradiction that
$\vec{x_{w}}+\mathfrak{m}_{w}\in\Psi(\mathfrak{J}(\mathcal{A}))=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}+\mathfrak{m}$, then by the same reasoning,
$\vec{x_{w}}+\mathfrak{m}_{w}\in S_{\mathfrak{m}_{w}}+\mathfrak{m}_{w}$. Thus,
there are two vectors $\vec{y}\notin S_{\mathfrak{m}_{w}}$ and $\vec{z}\in
S_{\mathfrak{m}_{w}}$ such that
$\vec{y}+\mathfrak{m}=\vec{x_{w}}+\mathfrak{m}=\vec{z}+\mathfrak{m}$. This
contradicts the assumption that $S_{\mathfrak{m}_{w}}$ is oblivious (note that
if $S_{\mathfrak{m}_{w}}$ is not oblivious, this is not a contradiction).

We conclude that
$\mathbb{M}^{\Sigma}\setminus\Psi(\mathfrak{J}(\mathcal{A}))=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}(\mathbb{N}^{\Sigma}\setminus S_{\mathfrak{m}})+\mathfrak{m}$,
and since semilinear sets are closed under complementation [3, 7], the latter
is also a masked semilinear set. By applying Theorem 3.4 in the converse
direction, we conclude that there exists an automaton $\mathcal{B}$ such that
$\Psi(\mathfrak{J}(\mathcal{B}))=\mathbb{M}^{\Sigma}\setminus\Psi(\mathfrak{J}(\mathcal{A}))$,
and as mentioned above, for such $\mathcal{B}$ we have
$\mathfrak{J}(\mathcal{B})=\Sigma^{\omega}\setminus\mathfrak{J}(\mathcal{A})$.
∎

######  Complexity Analysis 3.6 (of Proposition 2)

The description size of the complement of a semilinear set is singly
exponential, in both the degree and the description of the entries [3, 7]. We
proceed similarly to Theorem 3.5, ending up with a singly-exponential blowup
(not just in $|\Sigma|$).

Recall that Büchi automata are generally not determinizable. That is, there
exists an automaton $\mathcal{A}$ such that $\mathfrak{L}(\mathcal{A})$ is not
recognizable by a deterministic Büchi automaton [17]. In stark contrast, an
immediate corollary of Lemmas 2 and 3 is that jumping languages do admit
determinization (also see Theorem 3.3).

###### Proposition 3

For every automaton $\mathcal{A}$ there exists a deterministic automaton
$\mathcal{D}$ such that $\mathfrak{J}(\mathcal{A})=\mathfrak{J}(\mathcal{D})$.

In particular, this means that additional acceptance conditions (e.g., Rabin,
Streett, Muller and parity) cannot add expressiveness to the model.

###### Remark 3

Discussing determinization of jumping languages is slightly misleading: the
definition of acceptance in a jumping language asks that _there exists_ some
permutation that is accepted by the automaton. This existential quantifier can
be thought of as “semantic” nondeterminism. Thus, in a way, jumping languages
are inherently nondeterministic, regardless of the underlying syntactic
structure.

Finally, as is the case for jumping languages over finite words [20, 10, 11],
jumping languages and $\omega$-regular languages are incomparable. Indeed, the
automata in Fig. 3 are examples of Büchi automata whose languages are not
permutation-invariant, and are hence not jumping languages, and in Fig. 4 we
demonstrate that the converse also does not hold.

$q_{0}$$q_{1}$$q_{2}$$a$$b$$c$$c$ Figure 4: An automaton $\mathcal{A}$ for
which $\mathfrak{J}(\mathcal{A})=\\{u\cdot c^{\omega}\mid
u\in\\{a,b,c\\}^{*}\wedge\\#_{a}[u]=\\#_{b}[u]\\}$, which is not
$\omega$-regular by simple pumping arguments.

###  3.3 Jumping Languages - Algorithmic Properties

We turn our attention to algorithmic properties of jumping languages. We first
notice that given an automaton $\mathcal{A}$ we have that
$\mathfrak{J}(\mathcal{A})\neq\emptyset$ if and only if
$\mathfrak{L}(\mathcal{A})\neq\emptyset$. Thus, non-emptiness of
$\mathfrak{J}(\mathcal{A})$ is NL-Complete, as it is for Büchi automata [8,
16]. Next, we consider the standard decision problems:

  * •

Containment: given automata $\mathcal{A},\mathcal{B}$, is
$\mathfrak{J}(\mathcal{A})\subseteq\mathfrak{J}(\mathcal{B})$?

  * •

Equivalence: given automata $\mathcal{A},\mathcal{B}$, is
$\mathfrak{J}(\mathcal{A})=\mathfrak{J}(\mathcal{B})$?

  * •

Universality: given an automaton $\mathcal{A}$, is
$\mathfrak{J}(\mathcal{A})=\Sigma^{\omega}$?

We show that all of these problems reduce to their analogues in finite-word
jumping automata.

###### Theorem 3.7

Containment, Equivalence and Universality for jumping languages are coNP-
complete (for fixed size alphabet).

###### Proof

We start with containment. by Theorems 3.4 and 1, given automata
$\mathcal{A},\mathcal{B}$ we obtain canonical oblivious masked semilinear
representation:
$\Psi(\mathfrak{J}(\mathcal{A}))=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}+\mathfrak{m}$ and
$\Psi(\mathfrak{J}(\mathcal{B}))=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}T_{\mathfrak{m}}+\mathfrak{m}$. Then, we have
$\mathfrak{J}(\mathcal{A})\subseteq\mathfrak{J}(\mathcal{B})$ if and only if
$\Psi(\mathfrak{J}(\mathcal{A}))\subseteq\Psi(\mathfrak{J}(\mathcal{B}))$,
which in turn happens if and only if for every mask $\mathfrak{m}$ it holds
that $S_{\mathfrak{m}}+\mathfrak{m}\subseteq T_{\mathfrak{m}}+\mathfrak{m}$.
We claim that the latter holds if and only if $S_{\mathfrak{m}}\subseteq
T_{\mathfrak{m}}$.

Indeed, clearly if $S_{\mathfrak{m}}\subseteq T_{\mathfrak{m}}$ then
$S_{\mathfrak{m}}+\mathfrak{m}\subseteq T_{\mathfrak{m}}+\mathfrak{m}$.
Conversely, assume $S_{\mathfrak{m}}+\mathfrak{m}\subseteq
T_{\mathfrak{m}}+\mathfrak{m}$ and let $\vec{u}\in S_{\mathfrak{m}}$, so
$\vec{u}+\mathfrak{m}\in T_{\mathfrak{m}}+\mathfrak{m}$. Then, there exists
$\vec{v}\in T_{\mathfrak{m}}$ such that
$\vec{u}+\mathfrak{m}=\vec{v}+\mathfrak{m}$, but since $T_{\mathfrak{m}}$ is
$\mathfrak{m}$-oblivious, this means that $\vec{u}\in T_{\mathfrak{m}}$.

Thus, deciding whether
$\mathfrak{J}(\mathcal{A})\subseteq\mathfrak{J}(\mathcal{B})$ amounts to
deciding whether $S_{\mathfrak{m}}\subseteq T_{\mathfrak{m}}$ for every
$\mathfrak{m}$. Since the latter is decidable, we get decidability of
containment. Moreover, we can obtain in polynomial time nondeterministic
automata $\mathcal{C}^{\mathfrak{m}}_{1},\mathcal{C}^{\mathfrak{m}}_{2}$
corresponding to $S_{\mathfrak{m}}$ and $T_{\mathfrak{m}}$ (see Theorems 3.1
and 3.3), so it is enough to decide if
$\mathfrak{J}_{\text{fin}}(\mathcal{C}^{\mathfrak{m}}_{1})\subseteq\mathfrak{J}_{\text{fin}}(\mathcal{C}^{\mathfrak{m}}_{2})$
for all $\mathfrak{m}$. The latter problem is coNP-complete [15, 14] (for
fixed-size alphabet), and since we can start by nondeterministically guessing
$\mathfrak{m}$, we retain this complexity. Moreover, coNP hardness trivially
follows (by e.g., reducing a given language $L$ to $L\cdot\\#^{\omega}$ for a
new symbol $\\#$).

Similar arguments hold for equivalence and universality, concluding the proof.
∎

##  4 Fixed-Window Jumping Languages

Recall from Definition 1 that given an automaton $\mathcal{A}$ and
$k\in\mathbb{N}$, the language $\mathfrak{J}_{k\boxplus}(\mathcal{A})$
consists of the words that have a $k$-window permutation that is accepted by
$\mathcal{A}$.

Since $k$ is fixed, we can capture $k$-window permutations using finite
memory. Hence, as we now show, $\mathfrak{J}_{k\boxplus}(\mathcal{A})$ is
$\omega$-regular.

###### Theorem 4.1

Consider an automaton $\mathcal{A}$, then for every $k\in\mathbb{N}$ there
exists a Büchi automaton $\mathcal{B}_{k}$ such that
$\mathfrak{J}_{k\boxplus}(\mathcal{A})=\mathfrak{L}(\mathcal{B}_{k})$.

######  Proof (Sketch)

Intuitively, we construct $\mathcal{B}_{k}$ so that it stores in a state the
Parikh image of $k$ letters, then nondeterministically simulates $\mathcal{A}$
on all words with the stored Parikh image, while noting when an accepting
state may have been traversed. We illustrate the construction for $k=2$ in
Fig. 5. The details are in Section 0.A.2. ∎

######  Complexity Analysis 4.2 (of Theorem 4.1)

If $\mathcal{A}$ has $n$ states, then $\mathcal{B}$ has at most
$k^{|\Sigma|}\times n+n$ states. Moreover, computing $\mathcal{B}$ can be done
effectively, by keeping for every Parikh image the set of states that are
reachable (resp. reachable via an accepting state).

$\mathcal{D}$:$q_{0}$$q_{1}$$q_{2}$$q_{3}$$a$$b$$b$$b$$a$$b$

$\mathcal{B}_{2}$:$q_{0}\begin{pmatrix}0\\\
0\end{pmatrix}$$q_{0}\begin{pmatrix}1\\\
0\end{pmatrix}$$q_{0}\begin{pmatrix}0\\\
1\end{pmatrix}$$q_{3}$$q_{3}\begin{pmatrix}0\\\
1\end{pmatrix}$$a$$b$$b$$b$$a,b$$a$$b$$b$

Figure 5: An automaton $\mathcal{D}$, and the construction $\mathcal{B}_{2}$
for $\mathfrak{J}_{2\boxplus}(\mathcal{D})$ as per Theorem 4.1.

A converse of Theorem 4.1 also holds, in the following sense: we say that a
language $L\subseteq\Sigma^{\omega}$ is $k\boxplus$ invariant if $w\in L\iff
w^{\prime}\in L$ for every $w\sim_{k\boxplus}w^{\prime}$. The following result
follows by definition.

###### Proposition 4

Let $\mathcal{A}$ be an automaton such that $\mathfrak{L}(\mathcal{A})$ is
$k\boxplus$-invariant, then
$\mathfrak{L}(\mathcal{A})=\mathfrak{J}_{k\boxplus}(\mathcal{A})$.

Theorems 4.1 and 4 yield that $k$-window jumping languages are closed under
the standard operations under which $\omega$-regular languages are closed
(union, intersection, complementation), as these properties retain $k\boxplus$
invariance. Similarly, all algorithmic problems can be reduced to the same
problems on Büchi automata (by Theorem 4.2, assuming $|\Sigma|$ is fixed).

Notice that the construction in Theorem 4.1 yields a nondeterministic Büchi
automaton. This is not surprising in light of Remark 3. It does raise the
question of whether we can find a deterministic Büchi automaton for
$\mathfrak{J}_{k\boxplus}(\mathcal{D})$ for a _deterministic_ automaton
$\mathcal{D}$. In Proposition 5, we prove that this is not the case. That is,
even deterministic $k$-window jumping has inherent nondeterminism.

###### Proposition 5

There is no nondeterministic Büchi automaton whose language is
$\mathfrak{J}_{k\boxplus}(\mathcal{D})$ for $k\geq 2$ and $\mathcal{D}$ as in
Fig. 5.

###### Proof

Consider the deterministic automaton $\mathcal{D}$ in Fig. 5. We start by
showing that
$\mathfrak{L}(\mathcal{B}_{2})=\mathfrak{J}_{2\boxplus}(\mathcal{D})$ cannot
be recognized by a deterministic Büchi automaton. Below, we show this _mutatis
mutandis_ for every even $k$, and with slightly more effort – for all $k\geq
2$.

By way of contradiction, consider a deterministic automaton $\mathcal{A}$ such
that $\mathfrak{L}(\mathcal{A})=\mathfrak{J}_{2\boxplus}(\mathcal{D})$, then
$\mathcal{A}$ accepts $(ba)(bb)^{\omega}$, and therefore its run passes
through an accepting state after some $(ba)(bb)^{m_{1}}$. Then, $\mathcal{A}$
also accepts $(ba)(bb)^{m_{1}}(ab)(bb)^{\omega}$, so again there is $m_{2}$
such that $\mathcal{A}$ reaches an accepting state after
$(ba)(bb)^{m_{1}}(ab)(bb)^{m_{2}}$, we consider the word
$(ba)(bb)^{m_{1}}(ab)(bb)^{m_{2}}(ab)(bb)^{\omega}$ and proceed in this
fashion to construct an accepting run on a word with infinitely many $(ab)$,
which is not in $\mathfrak{J}_{2\boxplus}(\mathcal{D})$.

We now turn to show the same for any $k\geq 2$.

Assume by way of contradiction that there exists $k\in\mathbb{N},k\geq 2$ such
that $\mathfrak{J}_{k\boxplus}(\mathcal{D})=\mathfrak{L}(A)$ for a
deterministic automaton $\mathcal{A}$. $k$ can be either odd or even.

We first assume that $k$ is even and consider the word $w=bab^{\omega}$.
$w\in\mathfrak{J}_{k\boxplus}(\mathcal{D})$ as there is
$w^{\prime}\sim_{k\boxplus}w$ that is accepted by $\mathcal{D}$, namely
$w^{\prime}=w$. Since $bab^{\omega}\in\mathfrak{L}(\mathcal{A})$, the unique
run of $\mathcal{A}$ on it is accepting, and let $m_{1}$ be an index such that
$|bab^{m_{1}}|$ is divisible by $k$ and $\alpha$ was visited at least once
while reading $bab^{m_{1}}$. Now, consider the word
$w=bab^{m_{1}}bab^{\omega}$. $w\in\mathfrak{J}_{k\boxplus}(\mathcal{D})$ as
there is $w^{\prime}\sim_{k\boxplus}w$ that is accepted by $\mathcal{D}$, and
that is $w^{\prime}=abb^{m_{1}}bab^{\omega}$.
$bab^{m_{1}}bab^{\omega}\in\mathfrak{L}(\mathcal{A})$, then the unique run of
$\mathcal{A}$ on it is accepting, and let $m_{2}$ be an index such that
$|bab^{m_{1}}bab^{m_{2}}|$ is divisible by $k$ and $\alpha$ was visited at
least twice while reading $bab^{m_{1}}bab^{m_{2}}$. Consider the word
$w=bab^{m_{1}}bab^{m_{2}}bab^{\omega}$, it is also in
$\mathfrak{J}_{k\boxplus}(\mathcal{D})$ because
$w^{\prime}=abb^{m_{1}}abb^{m_{2}}bab^{\omega}$ is accepted by $\mathcal{D}$.
Following this fashion, we can construct an infinite word
$w=bab^{m_{1}}bab^{m_{2}}bab^{m_{3}}...$ such that $\mathcal{A}$’s run on it
visits $\alpha$ infinitely many often despite the fact that
$w\notin\mathfrak{J}_{k\boxplus}(\mathcal{D})$.

We then assume that $k\geq 2$ is odd and consider the word $w=ab^{\omega}$. We
have that $w\in\mathfrak{J}_{k\boxplus}(\mathcal{D})$ as there is
$w^{\prime}\sim_{k\boxplus}w$ that is accepted by $\mathcal{D}$, namely
$w^{\prime}=bab^{\omega}$. Since $ab^{\omega}\in\mathfrak{L}(A)$, the unique
run of $\mathcal{A}$ on it is accepting, and let $m_{1}$ be an index
$|ab^{m_{1}}|$ is divisible by $k$ and $\alpha$ was visited at least once
while reading $ab^{m_{1}}$. Now, consider the word $w=ab^{m_{1}}ab^{\omega}$.
Again $w\in\mathfrak{J}_{k\boxplus}(\mathcal{D})$ as there is
$w^{\prime}\sim_{k\boxplus}w$ that is accepted by $\mathcal{D}$, namely
$w^{\prime}=w$ (with the accepting run
$\rho=q_{0}q_{1}(q_{0}q_{2})^{k-2}q_{3}^{\omega}$). Since
$ab^{m_{1}}ab^{\omega}\in\mathfrak{L}(A)$, the unique run of $\mathcal{A}$ on
it is accepting, and let $m_{2}$ be an index such that
$|ab^{m_{1}}ab^{m_{2}}|$ is divisible by $k$ and $\alpha$ was visited at least
twice while reading $ab^{m_{1}}ab^{m_{2}}$. Similarly we can show that
$w=ab^{m_{1}}ab^{m_{2}}ab^{\omega}\in\mathfrak{J}_{k\boxplus}(\mathcal{D})$,
and we can proceed and construct an infinite word
$w=ab^{m_{1}}ab^{m_{2}}ab^{m_{3}}...$ such that $\mathcal{A}$’s run on it
visits $\alpha$ infinitely many often despite the fact that
$w\notin\mathfrak{J}_{k\boxplus}(\mathcal{D})$. It follows that there isn’t a
deterministic automaton $\mathcal{A}$ such that
$\mathfrak{J}_{k\boxplus}(\mathcal{D})=\mathfrak{L}(A)$ for any $k>1$. ∎

##  5 Existential-Window Jumping Languages

Recall from Definition 1 that given an automaton $\mathcal{A}$, the language
$\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$ contains the words that have a
$k$-window permutation that is accepted in $\mathcal{A}$ for some $k$, i.e.,
$\mathfrak{J}_{\exists\boxplus}(\mathcal{A})=\bigcup_{k\in\mathbb{N}}\mathfrak{J}_{k\boxplus}(\mathcal{A})$.
We briefly establish some expressiveness properties of
$\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$.

Perhaps surprisingly, we show that $\exists\boxplus$ languages are strictly
more expressive than Jumping languages. We start by showing that every jumping
language can be defined as the $\exists\boxplus$ language of some automaton.

###### Theorem 5.1

Let $\mathcal{A}$ be an automaton, then there exists an automaton
$\mathcal{B}$ such that
$\mathfrak{J}_{\exists\boxplus}(\mathcal{B})=\mathfrak{J}(\mathcal{A})$.

###### Proof

Intuitively, we modify the construction of the jumping automaton in Lemma 3 so
that it produces an automaton for which the $\exists\boxplus$ language
coincides with the given semilinear set.

Consider an automaton $\mathcal{A}$. By Lemmas 2 and 1, we can write
$\Psi(\mathfrak{J}(\mathcal{A}))=\bigcup_{\mathfrak{m}\in\includegraphics[page=488,height=0.0pt]{all-
twemojis.pdf}}S_{\mathfrak{m}}+\mathfrak{m}$ in canonical oblivious form.
Similarly to Lemma 3, consider a specific linear set
$L=\mathrm{Lin}(\vec{b},P\cup E_{\mathfrak{m}})$ in the union above, and
consider the words $w_{\vec{b}}\in\Sigma^{*}$ and $w_{\vec{p}}\in\Sigma^{*}$
for $\vec{p}\in P$ as in Lemma 3. Let $\mathcal{N}^{\prime}$ be a
nondeterministic automaton such that
$\mathfrak{L}_{\text{fin}}(\mathcal{N}^{\prime})=w_{\vec{b}}\cdot(w_{\vec{p_{1}}}+\ldots+w_{\vec{p_{n}}})^{*}$.
We now obtain an automaton $\mathcal{N}$ by connecting every accepting state
of $\mathcal{N}^{\prime}$ to a new nondeterministic automaton
$\mathcal{N}_{\mathfrak{m}}$ which, as a Büchi automaton, accepts the language
$L_{\mathfrak{m}}=\\{w\in\mathfrak{m}|_{\infty}^{\omega}\mid\text{ every
}\sigma\in\mathfrak{m}|_{\infty}^{\omega}\text{occurs infinitely often in
}w\\}$. The accepting states of $\mathcal{N}$ are those of
$\mathcal{N}_{\mathfrak{m}}$.

Observe that $L_{\mathfrak{m}}$ is permutation invariant, and in particular
$\mathfrak{J}_{\exists\boxplus}(\mathcal{N}_{\mathfrak{m}})=L_{\mathfrak{m}}$.
Indeed, trivially we have
$L_{\mathfrak{m}}=\mathfrak{L}(\mathcal{N}_{\mathfrak{m}})\subseteq\mathfrak{J}_{\exists\boxplus}(\mathcal{N}_{\mathfrak{m}})$,
and for the other direction – if
$w\in\mathfrak{J}_{\exists\boxplus}(\mathcal{N}_{\mathfrak{m}})$, then
$w\sim_{k\boxplus}w^{\prime}$ for some
$w^{\prime}\in\mathfrak{L}(\mathcal{N}_{\mathfrak{m}})=L_{\mathfrak{m}}$ and
some $k\in\mathbb{N}$, but since $L_{\mathfrak{m}}$ is permutation invariant,
and since we have in particular that $w\sim w^{\prime}$, then $w\in
L_{\mathfrak{m}}$.

Furthermore, $\Psi(\mathfrak{L}(\mathcal{N}))=\mathrm{Lin}(\vec{b},P\cup
E_{\mathfrak{m}})+\mathfrak{m}$. We construct $\mathcal{B}$ by taking the
union over $\mathfrak{m}$ in the masked semilinear set.

We claim that
$\mathfrak{J}_{\exists\boxplus}(\mathcal{B})=\mathfrak{J}(\mathcal{A})$. For
the “easy” direction, let $w\in\mathfrak{J}_{\exists\boxplus}(\mathcal{B})$,
then in particular
$\Psi(w)\in\Psi(\mathfrak{L}(\mathcal{N}))=\mathrm{Lin}(\vec{b},P\cup
E_{\mathfrak{m}})\subseteq S=\Psi(\mathfrak{J}(\mathcal{A}))$ (for some set in
the union), so $w\in\mathfrak{J}(\mathcal{A})$ (as $\mathfrak{J}(\mathcal{A})$
is permutation invariant).

For the “hard” direction, assume $w\in\mathfrak{J}(\mathcal{A})$, then
$\Psi(w)\in\mathrm{Lin}(\vec{b},P\cup E_{\mathfrak{m}})+\mathfrak{m}$ for some
set in the union. We construct a word $w^{\prime}\sim_{k\boxplus}w$ for some
$k\in\mathbb{N}$ such that $w^{\prime}\in\mathfrak{L}(\mathcal{B})$, thus
showing $w\in\mathfrak{J}_{\exists\boxplus}(\mathcal{B})$. Let
$k\in\mathbb{N}$ be large enough so that $w=u\cdot z$ with
$z\in\mathfrak{m}|_{\infty}^{\omega}$ and $|u|\leq k$. There exists such $k$
since $w$ contains only finitely many letters outside
$\mathfrak{m}|_{\infty}$. Recall that we assumed our sets are $\mathfrak{m}$
oblivious, and therefore $\Psi(u)\in\mathrm{Lin}(\vec{b},P\cup
E_{\mathfrak{m}})$. Moreover, $\Psi(z)=\mathfrak{m}$, since $z\in
L_{\mathfrak{m}}$. In particular, we can find a permutation $u^{\prime}$ of
$u$ such that $u^{\prime}\in\mathfrak{L}(\mathcal{N})$. Denote
$w^{\prime}=u^{\prime}z$, then $w^{\prime}$ satisfies the conditions above, so
$w\in\mathfrak{J}_{\exists\boxplus}(\mathcal{B})$ and we are done. ∎

Next, we show that jumping languages are strictly less expressive that
$\exists\boxplus$ languages.

###### Example 2

Consider the automaton $\mathcal{A}$ in Fig. 3. We claim that
$\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$ is not the jumping language of
any automaton. Indeed, it suffices to show that
$\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$ is not permutation invariant.
Trivially, $(ab)^{\omega}\in\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$.
However, note that $(ab)^{\omega}\sim(a^{n}b^{n})_{n=1}^{\infty}$ (i.e., the
word $aba^{2}b^{2}a^{3}b^{3}\cdots$), since their Parikh images are both
$(\infty,\infty)$. The latter, however, is not in
$\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$, since any $k$-window
permutation of $(a^{n}b^{n})_{n=1}^{\infty}$ will eventually reach windows of
the form $a^{k}$ (inside a long enough sequence $a^{n}$), so any permutation
of it will cause $\mathcal{A}$ to reject. ∎

We finally show that $\omega$-regular languages are incomparable with
$\exists\boxplus$ languages:

###### Example 3

Recall the automaton $\mathcal{A}$ in Fig. 4, with
$\mathfrak{L}(\mathcal{A})=(ab)^{*}\cdot c^{\omega}$. Observe that
$\mathfrak{J}_{\exists\boxplus}(\mathcal{A})=\mathfrak{J}(\mathcal{A})=\\{u\cdot
c^{\omega}\mid u\in\\{a,b,c\\}^{*}\wedge\\#_{a}[u]=\\#_{b}[u]\\}$. Indeed, if
$w=u\cdot c^{\omega}$ as described, then
$w\in\mathfrak{J}_{|u|\boxplus}(\mathcal{A})$ by rearranging the equal number
of $a$’s and $b$’s to $(ab)^{*}\cdot c^{\omega}$. Conversely, if
$w\in\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$ then in particular
$w\in\mathfrak{J}(\mathcal{A})$ (indeed, every $\exists\boxplus$-permutation
is also a permutation). Thus, $\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$ is
not $\omega$-regular.

For the converse (i.e., an $\omega$-regular language that is not
$\exists\boxplus$), we argue that every
$\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$ is $k$-window invariant for
every $k$, and since e.g., $\\{(ab)^{\omega}\\}$ is not 2-window invariant,
then it is not recognizable as an $\exists\boxplus$ language.

Indeed, consider $w\in\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$, and let
$w_{1}\sim_{k\boxplus}w$ for some $k$. Then there exists
$w_{2}\sim_{k\boxplus}w$ such that $w_{2}\in\mathfrak{L}(\mathcal{A})$ and
$k^{\prime}\in\mathbb{N}$. But then $w_{2}\sim_{k\boxplus}w$ and
$w_{1}\sim_{k\boxplus}w$, so by transitivity $w_{1}\sim_{k\boxplus}w_{2}$, and
so $w_{2}\in\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$. Thus,
$\mathfrak{J}_{\exists\boxplus}(\mathcal{A})$ is $k$-window invariant. ∎

######  Remark 4 (Alternative Semantics)

Note that instead of the $\exists\boxplus$ semantics, we could require that
there exists a partition of $w$ into windows of size _at most_ $k$ for some
$k\in\mathbb{N}$. All our proofs carry out under this definition as well.

##  6 Future Research

We have introduced three semantics for jumping automata over infinite words.
For the existing definitions, the class of $\exists\boxplus$ semantics is yet
to be explored for closure properties and decision problems.

In a broader view, it would be interesting to consider quantitative semantics
for jumping – instead of the coarse separation between letters that occur
finitely and infinitely often, one could envision a semantics that takes into
account e.g., the frequency with which letters occur. Alternatively, one could
return to the view of a “jumping reading head”, and place constraints over the
strategy used by the automaton to move the head (e.g., restrict to strategies
implemented by one-counter machines).

## References

  * [1] Abu Nassar, A., Almagor, S.: Simulation by rounds of letter-to-letter transducers. In: 30th EACSL Annual Conference on Computer Science Logic (2022)
  * [2] Almagor, S.: Process symmetry in probabilistic transducers. In: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2020)
  * [3] Beier, S., Holzer, M., Kutrib, M.: On the descriptional complexity of operations on semilinear sets. EPTCS 252 p. 41 (2017)
  * [4] Büchi, J.R.: Symposium on decision problems: On a decision method in restricted second order arithmetic. In: Studies in Logic and the Foundations of Mathematics, vol. 44, pp. 1–11. Elsevier (1966)
  * [5] Cadilhac, M., Finkel, A., McKenzie, P.: Affine parikh automata. RAIRO-Theoretical Informatics and Applications 46(4), 511–545 (2012)
  * [6] Cadilhac, M., Finkel, A., McKenzie, P.: Bounded parikh automata. International Journal of Foundations of Computer Science 23(08), 1691–1709 (2012)
  * [7] Chistikov, D., Haase, C.: The taming of the semi-linear set. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)
  * [8] Emerson, E.A., Lei, C.L.: Modalities for model checking (extended abstract) branching time strikes back. In: Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. pp. 84–96 (1985)
  * [9] Fazekas, S.Z., Hoshi, K., Yamamura, A.: Two-way deterministic automata with jumping mode. Theoretical Computer Science 864, 92–102 (2021)
  * [10] Fernau, H., Paramasivan, M., Schmid, M.L.: Jumping finite automata: characterizations and complexity. In: International Conference on Implementation and Application of Automata. pp. 89–101. Springer (2015)
  * [11] Fernau, H., Paramasivan, M., Schmid, M.L., Vorel, V.: Characterization and complexity results on jumping finite automata. Theoretical Computer Science 679, 31–52 (2017)
  * [12] Guha, S., Jecker, I., Lehtinen, K., Zimmermann, M.: Parikh automata over infinite words. In: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2022)
  * [13] Klaedtke, F., Rueß, H.: 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. pp. 681–696. Springer (2003)
  * [14] Kopczynski, E.: Complexity of problems of commutative grammars. Logical Methods in Computer Science 11 (2015)
  * [15] Kopczynski, E., To, A.W.: Parikh images of grammars: Complexity and applications. In: 2010 25th Annual IEEE Symposium on Logic in Computer Science. pp. 80–89. IEEE (2010)
  * [16] Kupferman, O.: Automata theory and model checking. Handbook of model checking pp. 107–151 (2018)
  * [17] Landweber, L.H.: Decision problems for w-automata. Tech. rep., University of Wisconsin-Madison Department of Computer Sciences (1968)
  * [18] Lavado, G.J., Pighizzini, G., Seki, S.: 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. pp. 294–305. Springer (2014)
  * [19] McNaughton, R.: Testing and generating infinite sequences by a finite automaton. Information and control 9(5), 521–530 (1966)
  * [20] Meduna, A., Zemek, P.: Jumping finite automata. International Journal of Foundations of Computer Science 23(07), 1555–1578 (2012)
  * [21] Parikh, R.J.: On context-free languages. Journal of the ACM (JACM) 13(4), 570–581 (1966)
  * [22] Safra, S.: On the complexity of $\omega$-automata. In: Proc. 29th IEEE Symp. Found. of Comp. Sci. pp. 319–327 (1988)
  * [23] To, A.W.: Parikh images of regular languages: Complexity and applications. arXiv preprint arXiv:1002.1464 (2010)
  * [24] Vorel, V.: On basic properties of jumping finite automata. International Journal of Foundations of Computer Science 29(01), 1–15 (2018)

##  Appendix 0.A Proofs

###  0.A.1 $\omega$-regular languages as union

The following claim is a folklore simple exercise, and we bring it for
completeness.

###### Claim

Consider an automaton $\mathcal{A}=\langle
Q,\Sigma,\delta,q_{0},\alpha\rangle$, then we can write
$\mathfrak{L}(\mathcal{A})=\bigcup_{i=1}^{k}S_{i}\cdot T_{i}^{\omega}$ where
the $S_{i}$ and $T_{i}$ are regular languages.

###### Proof

For states $p,q\in Q$, denote $\mathcal{A}_{p}^{q}$ the automaton
$\mathcal{A}$ with initial state $p$ and accepting states $\\{q\\}$. Observe
that $\mathcal{A}$ accepts a word if there is a run of $\mathcal{A}$ that
starts in $q_{0}$, and visits some state $q\in\alpha$ infinitely often
(indeed, since $Q$ is finite, then if $\alpha$ is visited infinitely often, so
is some state in $\alpha$).

We thus have
$\mathfrak{L}(\mathcal{A})=\bigcup_{q\in\alpha}\mathfrak{L}_{\text{fin}}(\mathcal{A}_{q_{0}}^{q})\cdot\mathfrak{L}_{\text{fin}}(\mathcal{A}_{q}^{q})^{\omega}$.
∎

###  0.A.2 Proof of Theorem 4.1

###### Proof

Intuitively, we construct $\mathcal{B}_{k}$ so that it stores in a state the
Parikh image of $k$ letters, then nondeterministically simulates $\mathcal{A}$
on all words with the stored Parikh image, while noting when an accepting
state may have been traversed. We illustrate the construction for $k=2$ in
Fig. 5.

We now formalize this intuition.

Let $\mathcal{A}=\langle Q,\Sigma,\delta,q_{0},\alpha\rangle$. We construct
$\mathcal{B}_{k}=\langle
Q^{\prime},\Sigma,\delta^{\prime},q_{0}^{\prime},\alpha^{\prime}\rangle$ as
follows.

  * •

Let $Q_{\alpha}=\\{q_{\alpha}\ |q\in Q\\}$ be a copy of $Q$, and
$P=\\{\Psi(x)|x\in\Sigma^{<k}\\}\subseteq\\{0,\ldots,k-1\\}^{|\Sigma|}$ be the
set of Parikh images of all words of length $<k$ (note that $P$ is finite),
then the states of $\mathcal{B}_{k}$ are $Q^{\prime}=(Q\times P)\cup
Q_{\alpha}$.

  * •

The initial state is $q_{0}^{\prime}=(q_{0},\vec{0})$ (Note that
$\Psi(\epsilon)=\vec{0}$).

  * •

$\alpha^{\prime}=Q_{\alpha}$.

  * •

The transition function is defined as follows. For a state $(q,\vec{v})$ and
letter $\sigma\in\Sigma$ let $\vec{u}=\vec{v}+\Psi(\sigma)$. If
$\sum_{\sigma\in\Sigma}\vec{u}(\sigma)<k$ we define
$\delta((q,\vec{v}),\sigma)=(q,\vec{u})$. If
$\sum_{\sigma\in\Sigma}\vec{u}(\sigma)=k$, define $\delta^{*}(q,\vec{u})$ to
be the set of states reachable from $q$ upon reading a word $x$ with
$\Psi(x)=\vec{u}$, and define $\delta_{\alpha}^{*}(q,\vec{u})$ to be the
states reachable from $q$ upon reading a word $x$ with $\Psi(x)=\vec{u}$ via a
run that visits $\alpha$. We then have

$\delta^{\prime}((q,\vec{v}),\sigma)=\\{(p,\vec{0})\mid
p\in\delta^{*}(q,\vec{v})\\}\cup\\{p_{\alpha}\mid
p\in\delta_{\alpha}^{*}(q,\vec{v})\\}$

Finally, for every $q\in Q_{\alpha}$ we define
$\delta^{\prime}(q,\sigma)=\delta^{\prime}((q,\vec{0}),\sigma)$ (that is, the
$Q_{\alpha}$ copy behaves identically to the $\vec{0}$ copy of $Q$).

We now claim that
$\mathfrak{J}_{k\boxplus}(\mathcal{A})=\mathfrak{L}(\mathcal{B}_{k})$: Let
$w\in\mathfrak{J}_{k\boxplus}(\mathcal{A})$ and write $w=x_{1}x_{2}x_{3}...$
where $|x_{i}|=k$ for all $i$. Then, there is
$w^{\prime}=y_{1}y_{2}y_{3}...\sim_{k\boxplus}w$ (with all $|y_{i}|=k$) such
that $\mathcal{A}$ has an accepting run $\rho$ on $w^{\prime}$. Denote by
$q_{0},q_{1},\ldots$ the states where for $i\geq 1$ we have $q_{i}=\rho_{ik}$.
That is, the states that $\rho$ visits after reading each $y_{i}$. Observe
that for all $i$ we have that
$q_{k(i+1)}\in\delta^{*}(q_{ik},\psi(y_{i+1}))=\delta^{*}(q_{ik},\psi(x_{i+1}))$.
Thus, there is a run of $\mathcal{B}$ that upon reading $x_{i+1}$ reaches the
state $(q_{(i+1)k},\vec{0})$ if $\rho$ does not go through an accepting state
on $y_{i+1}$ or $(q_{(i+1)k})_{\alpha}$ if it does. Since $\rho$ traverses
infinitely many accepting states, so does the run of $\mathcal{B}_{k}$ on $w$,
and thus $w\in\mathfrak{L}(\mathcal{B}_{k})$.

Conversely, assume $w\in\mathfrak{L}(\mathcal{B}_{k})$ and again write
$w=x_{1}x_{2}x_{3}...$ with $|x_{i}|=k$. Then there is an accepting run of
$\mathcal{B}_{k}$ on $w$. By viewing the run in consecutive $k$-windows, we
can construct words $y_{1},y_{2},\ldots$ such that $y_{i}\sim x_{i}$ for all
$i$ and such that $\mathcal{A}$ accepts $w^{\prime}=y_{1}\cdot y_{2}\cdots$.
Indeed, in every $k$-window, $\mathcal{B}$ simulates the run of $\mathcal{A}$
on some permutation of the read word. We conclude that
$w\in\mathfrak{J}_{k\boxplus}(\mathcal{A})$. ∎