text:
\section{Introduction}

In his groundbreaking work~\cite{buechi} from 1960 Büchi initiated the study of $\omega$-regular languages and introduced Büchi automata.
By his famous theorem $\omega$-regular languages are characterized as languages of the form $\bigcup_i U_i V_i^\omega$, where the $U_i$ and $V_i$ are regular languages.
One shortcoming of Büchi automata, and also of many more powerful models, is that they cannot count.
For example, the language $\{a^nb^nc^n \mid n \in \mathbb{N}\}^\omega$ is not $\omega$-regular, and not even $\omega$-context-free.
This shortcoming led to the study of automata on infinite words with counters, see e.g.~\cite{allredCounting, bojanczykbeyond, beyondomegabs}.

Parikh automata (PA) are another model of automata (on finite words) with counters~\cite{klaedtkeruess}.
A PA with~$d$~counters is a non-deterministic finite automaton that is additionally equipped with a semi-linear set~$C$.
Furthermore, every transition is equipped with a $d$-tuple of non-negative integers and every time a transition is used, the counters are incremented by the values in the tuple accordingly.
A finite input word is accepted if the PA ends in a final state and additionally, the resulting $d$-tuple in the counters lies in~$C$. The class of languages recognized by PA contains all regular languages, and even some, but not all, context-sensitive languages, e.g.\ the language $\{a^nb^nc^n \mid n \in \mathbb{N}\}$.

Recently, several possible extensions of Parikh automata on infinite words were proposed and studied by Grobler et al.~\cite{infiniteOurs} and Guha et al.~\cite{infiniteZimmermann}.
In fact, it turns out that one of the models proposed in~\cite{infiniteOurs} is equivalent to synchronous blind counter machines, which were introduced by Fernau and Stiebe~\cite{blindcounter}.
Fernau and Stiebe also considered the class of all $\omega$-languages of the form $\bigcup_iU_iV_i^\omega$, where the $U_i,V_i$ are Parikh-recognizable languages of finite words.
They called this class $\ensuremath{\mathcal{K}}\xspace_*$ and proved that the class of \mbox{$\omega$-languages} recognized by blind counter machines is a proper subset of $\ensuremath{\mathcal{K}}\xspace_*$.

\smallskip
In the light of Büchi's famous theorem it is a natural question to find an automata theoretic characterization of the class $\ensuremath{\mathcal{K}}\xspace_*$. In fact, more generally, we define the four classes $\ensuremath{\Lmc_\mathsf{Reg, Reg}^\omega}\xspace$, $\ensuremath{\Lmc_\mathsf{PA, Reg}^\omega}\xspace$, $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$ and $\ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace$ of $\omega$-languages of the form $\bigcup_iU_iV_i^\omega$, where the $U_i,V_i$ are regular or Parikh-recognizable languages of finite words, respectively. By Büchi's theorem the class $\ensuremath{\Lmc_\mathsf{Reg, Reg}^\omega}\xspace$ is the class of $\omega$-regular languages.
In this work we provide automata theoretic characterizations of the other three classes.

\smallskip
We first introduce the new model of \emph{limit Parikh Büchi automata} (LPBA), which was suggested in the concluding remarks of Klaedtke and Ruess~\cite{klaedtkeruess}.
An LPBA accepts an infinite word if an accepting state is visited infinitely often (satisfies the Büchi condition) and the infinite sum of the counters belongs to the semi-linear set, which for this purpose is extended with the symbol $\infty$ if the sum of some counter diverges (satisfies the newly introduced \emph{limit Parikh condition}).

We also introduce a new model, which is obtained by a small modification of reachability Parikh automata as introduced by Guha et al.~\cite{infiniteZimmermann}, that we call \emph{reachability Parikh Büchi automata}
(RPBA). An RPBA accepts an infinite word if an
accepting state is visited infinitely often (satisfies the Büchi condition) and satisfies the Parikh condition \emph{once}.

Quite surprisingly, both models turn out to capture exactly the class $\ensuremath{\Lmc_\mathsf{PA, Reg}^\omega}\xspace$, and hence are equivalent.

\smallskip
We then study \emph{strong reset Parikh automata} (SPBA), which were introduced by Grobler et al.~\cite{infiniteOurs}. We consider the automata as directed graphs and provide two graph theoretic definitions of subclasses of SPBA that exactly capture the classes $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$ and~$\ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace$. These definitions are based on an analysis of the strongly connected components of the underlying graph, where the accepting states can be found and how they are connected to the rest of the graph.

\smallskip
We believe that our results provide interesting insights into the theory of Parikh-recognizable $\omega$-languages.
It remains an interesting open question to characterize the new classes of $\omega$-languages by logics.

\section{Preliminaries}
\label{sec:prelims}

\subsection{Finite and infinite words}
We write $\ensuremath{\mathbb{N}}\xspace$ for the set of non-negative integers including $0$. Let $\Sigma$ be an alphabet, i.\,e.\xspace, a finite non-empty set and let $\Sigma^*$ be the set of all finite words over $\Sigma$.
For a word $w \in \Sigma^*$, we denote by $|w|$ the length of $w$, and by $|w|_a$ the number of occurrences of the letter $a \in \Sigma$ in $w$.
We write $\varepsilon$ for the empty word of length~$0$.

An \emph{infinite word} over an alphabet $\Sigma$ is a function $\alpha : \ensuremath{\mathbb{N}}\xspace \setminus \{0\} \rightarrow \Sigma$. We often write~$\alpha_i$ instead of~$\alpha(i)$.
Thus, we can understand an infinite word as an infinite sequence of symbols $\alpha = \alpha_1\alpha_2\alpha_3\ldots$ For $m \leq n$, we abbreviate the finite infix $\alpha_m \ldots \alpha_n$ by $\alpha[m,n]$.
We denote by $\Sigma^\omega$ the set of all infinite words over $\Sigma$.
We call a subset $L \subseteq \Sigma^\omega$ an \emph{$\omega$-language}.
Moreover, for $L \subseteq \Sigma^*$, we define $L^\omega = \{w_1w_2\dots \mid w_i \in L \setminus \{\varepsilon\}\} \subseteq \Sigma^\omega$.

\subsection{Regular and $\omega$-regular languages}

A \emph{Nondeterministic Finite Automaton} (NFA) is a tuple $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F)$, where~$Q$ is the finite set of states, $\Sigma$ is the input alphabet, $q_0 \in Q$ is the initial state, $\Delta \subseteq Q \times \Sigma \times Q$ is the set of transitions and $F \subseteq Q$ is the set of accepting states.
A \emph{run} of $\ensuremath{\mathcal{A}}\xspace$ on a word $w = w_1 \ldots w_n\in \Sigma^*$ is a (possibly empty) sequence of transitions $r = r_1 \ldots r_n$ with $r_i = (p_{i-1}, w_i, p_i)\in \Delta$ such that $p_0=q_0$.
We say $r$ is \emph{accepting} if $p_n \in F$. The empty run on~$\epsilon$ is accepting if $q_0 \in F$. We define the \emph{language recognized by \ensuremath{\mathcal{A}}\xspace} as $L(\ensuremath{\mathcal{A}}\xspace) = \{w \in \Sigma^* \mid \text{there is an accepting run of $\ensuremath{\mathcal{A}}\xspace$ on $w$}\}$. If a language $L$ is recognized by some NFA $\ensuremath{\mathcal{A}}\xspace$, we call $L$ \emph{regular}.

A \emph{Büchi Automaton} (BA) is an NFA $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F)$ that takes infinite words as input.
A \emph{run} of $\ensuremath{\mathcal{A}}\xspace$ on an infinite word $\alpha_1\alpha_2\alpha_3\dots$ is an infinite sequence of transitions $r = r_1 r_2 r_3 \dots$ with $r_i = (p_{i-1}, \alpha_i, p_i) \in \Delta$ such that $p_0=q_0$.
We say $r$ is \emph{accepting} if there are infinitely many~$i$ such that $p_i \in F$.
We define the \emph{$\omega$-language recognized by~$\ensuremath{\mathcal{A}}\xspace$} as $L_\omega(\ensuremath{\mathcal{A}}\xspace) = \{\alpha \in \Sigma^\omega \mid \text{there is an accepting run of $\ensuremath{\mathcal{A}}\xspace$ on $\alpha$}\}$.
If an $\omega$-language $L$ is recognized by some BA $\ensuremath{\mathcal{A}}\xspace$, we call $L$ \emph{$\omega$-regular}. Büchi's theorem establishes an important connection between regular and $\omega$-regular languages:
\begin{theorem}[Büchi]
\label{thm:buechi}
A language $L \subseteq \Sigma^\omega$ is $\omega$-regular if and only if there are regular languages $U_1, V_1, \dots, U_n, V_n \subseteq \Sigma^*$ for some $n \geq 1$ such that $L = U_1V_1^\omega \cup \dots \cup U_nV_n^\omega$.
\end{theorem}

\subsection{Semi-linear sets}
A \emph{linear set} of dimension $d$ for $d \geq 1$ is a set of the form $\{b_0 + b_1z_1 + \dots + b_\ell z_\ell \mid z_1, \dots, z_\ell \in \ensuremath{\mathbb{N}}\xspace\} \subseteq \ensuremath{\mathbb{N}}\xspace^d$ for $b_0,\ldots, b_\ell\in \ensuremath{\mathbb{N}}\xspace^d$.
A \emph{semi-linear set} is the finite union of linear sets.
For vectors $\ensuremath{\mathbf{u}}\xspace = (u_1, \dots, u_c)\in \ensuremath{\mathbb{N}}\xspace^c, \ensuremath{\mathbf{v}}\xspace = (v_1, \dots, v_d) \in \ensuremath{\mathbb{N}}\xspace^d$, we denote by $\ensuremath{\mathbf{u}}\xspace \cdot \ensuremath{\mathbf{v}}\xspace = (u_1, \dots, u_c, v_1, \dots, v_d) \in \ensuremath{\mathbb{N}}\xspace^{c+d}$ the \emph{concatenation of $\ensuremath{\mathbf{u}}\xspace$ and $\ensuremath{\mathbf{v}}\xspace$}.
We extend this definition to sets of vectors. Let $C \subseteq \ensuremath{\mathbb{N}}\xspace^c$ and $D \subseteq \ensuremath{\mathbb{N}}\xspace^d$. Then $C \cdot D = \{\ensuremath{\mathbf{u}}\xspace \cdot \ensuremath{\mathbf{v}}\xspace \mid \ensuremath{\mathbf{u}}\xspace \in C, \ensuremath{\mathbf{v}}\xspace \in D\} \subseteq \ensuremath{\mathbb{N}}\xspace^{c+d}$.
We denote by~$\ensuremath{\mathbf{0}}\xspace^d$ (or simply $\ensuremath{\mathbf{0}}\xspace$ if $d$ is clear from the context) the all-zero vector, and by~$\ensuremath{\mathbf{e}}\xspace^d_i$ (or simply $\ensuremath{\mathbf{e}}\xspace_i)$ the $d$-dimensional vector where the $i$th entry is~$1$ and all other entries are~0.
We also consider semi-linear sets over $(\ensuremath{\mathbb{N}}\xspace \cup \{\infty\})^d$, that is semi-linear sets with an additional symbol $\infty$ for infinity. As usual, addition of vectors and multiplication of a vector with a number is defined component-wise, where $z + \infty = \infty + z = \infty + \infty = \infty$ for all $z \in \ensuremath{\mathbb{N}}\xspace$, $z \cdot \infty = \infty \cdot z = \infty$ for all $z > 0\in \ensuremath{\mathbb{N}}\xspace$, and $0 \cdot \infty = \infty \cdot 0 = 0$.

\subsection{Parikh-recognizable languages}
A \emph{Parikh Automaton} (PA) is a tuple $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F, C)$ where $Q$, $\Sigma$, $q_0$, and~$F$ are defined as for NFA, $\Delta \subseteq Q \times \Sigma \times \ensuremath{\mathbb{N}}\xspace^d \times Q$ is the set of \emph{labeled transitions}, and $C \subseteq \ensuremath{\mathbb{N}}\xspace^d$ is a semi-linear set.
We call $d$ the \emph{dimension} of $\ensuremath{\mathcal{A}}\xspace$ and refer to the entries of a vector $\ensuremath{\mathbf{v}}\xspace$ in a transition $(p, a, \ensuremath{\mathbf{v}}\xspace, q)$ as \emph{counters}.
Similar to NFA, a \emph{run} of $\ensuremath{\mathcal{A}}\xspace$ on a word $w = x_1 \dots x_n$ is a (possibly empty) sequence of labeled transitions $r = r_1 \dots r_n$ with $r_i = (p_{i-1}, x_i, \ensuremath{\mathbf{v}}\xspace_i, p_i) \in \Delta$ such that $p_0 = q_0$. We define the \emph{extended Parikh image} of a run $r$ as $\rho(r) = \sum_{i \leq n} \ensuremath{\mathbf{v}}\xspace_i$ (with the convention that the empty sum equals $\ensuremath{\mathbf{0}}\xspace$).
We say $r$ is accepting if $p_n \in F$ and $\rho(r) \in C$,
referring to the latter condition as the \emph{Parikh condition}.
We define the \emph{language recognized by \ensuremath{\mathcal{A}}\xspace} as $L(\ensuremath{\mathcal{A}}\xspace) = \{w \in \Sigma^* \mid \text{there is an accepting run of $\ensuremath{\mathcal{A}}\xspace$ on $w$}\}$.
If a language $L\subseteq \Sigma^*$ is recognized by some PA, then we call $L$ \emph{Parikh-recognizable}.

\subsection{Graphs}
A \emph{(directed) graph} $G$ consists of its vertex set $V(G)$ and edge set \mbox{$E(G) \subseteq V(G) \times V(G)$}. In particular, a graph $G$ may have loops, that is, edges of the form $(u, u)$. A \emph{path} from a vertex $u$ to a vertex $v$ in $G$ is a sequence of pairwise distinct vertices $v_1 \dots v_k$ such that $v_1 = u$, $v_k = v$, and $(v_i, v_{i+1}) \in E(G)$ for all $1 \leq i < k$. Similarly, a \emph{cycle} in $G$ is a sequence of pairwise distinct vertices $v_1 \dots v_k$ such that $(v_i, v_{i+1}) \in E(G)$ for all $1 \leq i < k$, and $(v_k, v_1) \in E(G)$. If $G$ has no cylces, we call $G$ a directed acyclic graph (DAG).
For a subset $U \subseteq V(G)$, we denote by $G[U]$ the graph $G$ \emph{induced by} $U$, i.\,e.\xspace, the graph with vertex set $U$ and edge set $\{(u,v) \in E(G) \mid u, v \in U\}$.
A \emph{strongly connected component} (SCC) in $G$ is a maximal subset $U \in V(G)$ such that for all $u, v \in U$ there is a path from~$u$ to $v$, i.\,e.\xspace, all vertices in $U$ are reachable from each other.
We write $SCC(G)$ for the set of all strongly connected components of $G$ (observe that $SCC(G)$ partitions~$V(G)$).
The \emph{condensation} of $G$, written $C(G)$, is the DAG obtained from $G$ by contracting each SCC of $G$ into a single vertex, that is $V(C(G)) = SCC(G)$ and $(U, V) \in E(C(G))$ if and only if there is $u \in U$ and $v \in V$ with $(u, v) \in E(G)$.
We call the SCCs with no outgoing edges in $C(G)$ leaves.
Note that an automaton can be seen as a labeled graph. Hence, all definitions translate to automata by considering the underlying graph (to be precise, an automaton can be seen as a labeled multigraph; however, we simply drop parallel edges).

\section{Parikh automata on infinite words}
In this section, we recall the relevant definitions of Parikh automata operating on infinite words introduced by Grobler et al. \cite{infiniteOurs} and Guha et al. \cite{infiniteZimmermann}. We then propose further definitions and compare the resulting automata.

\smallskip
A \emph{Parikh-Büchi automaton} (PBA) is a PA $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F, C)$. A run of $\ensuremath{\mathcal{A}}\xspace$ on an infinite word $\alpha = \alpha_1 \alpha_2 \alpha_3 \dots$ is an infinite sequence of labeled transitions $r = r_1 r_2 r_3 \dots$ with $r_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)\in \Delta$ such that $p_0 = q_0$. The automata defined below differ only in their acceptance conditions. In the following, whenever we say that an automaton $\ensuremath{\mathcal{A}}\xspace$ accepts an infinite word $\alpha$, we mean that there is an accepting run of $\ensuremath{\mathcal{A}}\xspace$ on $\alpha$.

Let us first recall the definition of \emph{(strong) reset PBA} (SPBA) introduced by Grobler et al.~\cite{infiniteOurs}: let $k_0 = 0$ and denote by $k_1, k_2, \dots$ the positions of all accepting states in~$r$. Then $r$ is accepting if $k_1, k_2, \dots$ is an infinite sequence and $\rho(r_{k_{i-1}+1} \dots r_{k_i}) \in C$ for all $i \geq 1$. The $\omega$-language recognized by an SPBA $\ensuremath{\mathcal{A}}\xspace$ is $S_\omega(\ensuremath{\mathcal{A}}\xspace) = \{\alpha \mid \ensuremath{\mathcal{A}}\xspace \text{ accepts }\alpha\}$. Intuitively worded, whenever an SPBA enters an accepting state, the Parikh condition \emph{must} be satisfied. Then the counters are reset.

Let us now recall the definition of \emph{(synchronous) reachability Parikh automata} (RPA) introduced by Guhe et al.~\cite{infiniteZimmermann}. The run $r$ is accepting if there is an $i \geq 1$ such that $p_i \in F$ and $\rho(r_1 \dots r_i) \in C$. We say there is an accepting hit in $r_i$. The $\omega$-language recognized by an RPA $\ensuremath{\mathcal{A}}\xspace$ is $R_\omega(\ensuremath{\mathcal{A}}\xspace) = \{\alpha \mid \ensuremath{\mathcal{A}}\xspace \text{ accepts }\alpha\}$.

Let us finally recall the definition of \emph{prefix PBA} (PPBA) introduced by Grobler et al.~\cite{infiniteOurs}, which are obviously equivalent to \emph{(synchronous) Büchi Parikh automata} introduced by Guhe et al. \cite{infiniteZimmermann}. The run $r$ is accepting if there are infinitely many $i \geq 1$ such that $p_i \in F$ and $\rho(r_1 \dots r_i) \in C$. The $\omega$-language recognized by a PPBA $\ensuremath{\mathcal{A}}\xspace$ is $P_\omega(\ensuremath{\mathcal{A}}\xspace) = \{\alpha \mid \ensuremath{\mathcal{A}}\xspace \text{ accepts }\alpha\}$. Hence, a PPBA can be seen as a stronger variant of RPA where we require infinitely many accepting hits instead of a single one.

We remark that we stick to the notation of the original papers, that is, we abbreviate (strong) reset Parikh-Büchi automata by SPBA and (synchronous) reachability Parikh automata by RPA.
The attentive reader may have noticed that we do not use the term~RPBA.
The reason for this (in addition to sticking to the original notation) is that, unlike Büchi automata, RPA do \emph{not} need to see an accepting state infinitely often.
We show that this property implies that there are $\omega$-regular languages that are not RPA-recogniazble.
This motivates the study of RPA that additionally need to satisfy the Büchi-condition (which we hence will call RPBA).

\smallskip
We begin with a simple lemma. A similar result was proved in Theorem~3 of~\cite{infiniteZimmermann}, however, RPA in~\cite{infiniteZimmermann} are assumed to be \emph{complete}, i.e., for every state and every symbol there is at least one transition. The proof presented in~\cite{infiniteZimmermann} does not go through for the more general setting of non-complete RPA.

\begin{lemma}
\label{lem:RPAregular}
 There is an $\omega$-regular language that is not recognized by any RPA.
\end{lemma}
\begin{proof}
    We show that $L = \{\alpha \in \{a,b\}^\omega \mid |\alpha|_a = \infty\}$ is not RPA-recognizable.
    Assume that there is an RPA $\ensuremath{\mathcal{A}}\xspace$ with $R_\omega(\ensuremath{\mathcal{A}}\xspace) = L$ and let $n$ be the number of states of~$\ensuremath{\mathcal{A}}\xspace$. As $\alpha = (a^n b^n)^\omega \in L$, there is an accepting run $r = r_1 r_2 r_3 \dots$ of $\ensuremath{\mathcal{A}}\xspace$ on $\alpha$. Let $i$ be the first position of an accepting hit in $r$.
    Now consider $\beta = (a^n b^n)^i \cdot b^\omega \notin L$.
    As $\alpha$ and $\beta$ share the same prefix of length $i$, the run $r_1 \dots r_i$ is also a partial run on~$\beta[1,i]$, hence, generating an accepting hit.
    Now observe that in every infix of the form $b^n$ a state is visited at least twice by the pigeonhole principle. Hence, we can ``infinitely pump" a $b$-block after the accepting hit in $r_i$ and obtain an accepting run on~$\beta$, contradicting $R_\omega(\ensuremath{\mathcal{A}}\xspace) = L$.
\end{proof}
\begin{remark}
\label{remark:RPA}
    In fact, complete RPA are strictly weaker than general RPA, as there is no complete RPA recognizing $\{a\}^\omega$ over $\Sigma = \{a,b\}$; an $\omega$-language that is obviously RPA-recognizable.
\end{remark}

As mentioned above, this weakness motivates the study of \emph{reachability Parikh-Büchi automata} (RPBA).
The run $r$ is accepting if there is an $i \geq 1$ such that $\rho(r_1 \dots r_i) \in C$ and $p_i \in F$, and if there are infinitely many $j$ such that $p_j \in F$. We define
the $\omega$-language recognized by an RPBA $\ensuremath{\mathcal{A}}\xspace$ as $B_\omega(\ensuremath{\mathcal{A}}\xspace) = \{\alpha \mid \ensuremath{\mathcal{A}}\xspace \text{ accepts }\alpha\}$.

Every $\omega$-regular language is RPBA-recognizable, as we can turn an arbitrary Büchi automaton into an equivalent RPBA by labeling every transition with $0$ and \mbox{setting~$C = \{0\}$}.

\smallskip
Finally, we define a variant of PBA motivated by a proposal of Klaedke and Ruess~\cite{klaedtkeruess}. Here we consider semi-linear sets over $(\ensuremath{\mathbb{N}}\xspace \cup \{\infty\})^d$ and compute the extended Parikh image of an infinite run using transfinite induction.
A \emph{limit Parikh-Büchi automaton} (LPBA) is a PA $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F, C)$ where $C$ may use the symbol $\infty$.
The run $r$ is accepting
if there are infinitely many~$i \geq 1$ such that $p_i \in F$, and if additionally $\rho(r) \in C$, where the $j$-th component of $\rho(r)$ is computed as follows. If there are infinitely many~$i \geq 1$ such that the $j$-th component of $\ensuremath{\mathbf{v}}\xspace_i$ has a non-zero value, then the $j$-th component of $\rho(C)$ is~$\infty$. In other words, if the sum of values in a component diverges, then its value is set to $\infty$.
Otherwise, the infinite sum yields a positive integer. We define the $\omega$-language recognized by an LPBA $\ensuremath{\mathcal{A}}\xspace$ as $L_\omega(\ensuremath{\mathcal{A}}\xspace) = \{\alpha \mid \ensuremath{\mathcal{A}}\xspace \text{ accepts }\alpha\}$.

\begin{example}
\label{ex}
\begin{figure}
	\centering
	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm, semithick]
	\tikzstyle{every state}=[minimum size=1cm]

	\node[initial, initial text={}, state] (q0) {$q_0$};
	\node[state, accepting] (q1) [right of=q0] {$q_1$};

	\path
	(q0) edge [loop above] node {$a, \begin{pmatrix}1\\ensuremath{\mathbf{0}}\xspace\end{pmatrix}$} (q0)
	(q0) edge              node {$b, \begin{pmatrix}0\\1\end{pmatrix}$} (q1)
	(q1) edge [loop above] node {$b, \begin{pmatrix}0\\1\end{pmatrix}$} (q1)
	(q1) edge [bend left]  node {$a, \begin{pmatrix}1\\ensuremath{\mathbf{0}}\xspace\end{pmatrix}$} (q0)
	;
	\end{tikzpicture}
	\caption{The automaton $\ensuremath{\mathcal{A}}\xspace$ with $C=\{(z,z), (z, \infty) \mid z \in \ensuremath{\mathbb{N}}\xspace\}$ from \Cref{ex}.}
	\label{fig:ex}
\end{figure}

Let $\ensuremath{\mathcal{A}}\xspace$ be the automaton in \Cref{fig:ex} with $C = \{(z,z), (z, \infty) \mid z \in \ensuremath{\mathbb{N}}\xspace\}$.
\begin{itemize}
    \item If we interpret $\ensuremath{\mathcal{A}}\xspace$ as a PA (over finite words), then we have $L(\ensuremath{\mathcal{A}}\xspace) = \{w \in \{a,b\}^* \cdot \{b\} \mid |w|_a = |w|_b\}$. The automaton is in the accepting state after reading a $b$. The first counter counts the number of read $a$s, the second one reads the number of read $b$s. By definition of $C$ the automaton only accepts when both counters are equal (note that vectors containing an $\infty$-entry have no additional effect).
    \item If we interpret $\ensuremath{\mathcal{A}}\xspace$ as an SPBA, then we have $S_\omega(\ensuremath{\mathcal{A}}\xspace) = \{ab\}^\omega$. Whenever the automaton reaches an accepting state also the Parikh condition must be satisfied. In the example this is only possible after reading exactly one $a$ and one $b$. After that the counters are reset.
    \item If we interpret $\ensuremath{\mathcal{A}}\xspace$ as a PPBA, then we have $P_\omega(\ensuremath{\mathcal{A}}\xspace) = L(\ensuremath{\mathcal{A}}\xspace)^\omega$. The automaton accepts a word if infinitely often the Parikh condition is satisfied in the accepting state. Observe that $C$ has no base vector and the initial state as well as the accepting state have the same outgoing edges.
    \item If we interpret $\ensuremath{\mathcal{A}}\xspace$ as an LPBA, then we have $L_\omega(\ensuremath{\mathcal{A}}\xspace) = \{\alpha \in \{a,b\}^\omega \mid |\alpha|_a < \infty\}$. The automaton must visit the accepting state infinitely often. At the same time the extended Parikh image must belong to $C$, which implies that the word contains only some finite number $z$ of $a$s (note that only the vectors of the form $(z, \infty)$ have an effect here, as at least one symbol must be seen infinitely often by the infinite pigeonhole principle).
    \item If we interpret $\ensuremath{\mathcal{A}}\xspace$ as an RPA, then we have $R_\omega(\ensuremath{\mathcal{A}}\xspace) = \{\alpha \in \{a,b\}^\omega \mid \alpha \text{ has a prefix in }$ $L(\ensuremath{\mathcal{A}}\xspace)\}$. The automaton has satisfied the reachability condition after reading a prefix in $L(\ensuremath{\mathcal{A}}\xspace)$. Since the automaton is complete it cannot get stuck and accepts any continuation after that.
    \item If we interpret $\ensuremath{\mathcal{A}}\xspace$ as an RPBA, then we have $B_\omega(\ensuremath{\mathcal{A}}\xspace) = \{\alpha \in \{a,b\}^\omega \mid \alpha \text{ has a prefix}$ in $L(\ensuremath{\mathcal{A}}\xspace) \text{ and } |\alpha|_b = \infty\}$. After having met the reachability condition the automaton still needs to satisfy the Büchi condition, which enforces infinitely many visits of the accepting state.
\end{itemize}
\end{example}

\begin{remark}
The automaton $\ensuremath{\mathcal{A}}\xspace$ in the last example is deterministic. We note that $L_\omega(\ensuremath{\mathcal{A}}\xspace)$ is not deterministic $\omega$-regular but deterministic LPBA-recognizable.
\end{remark}

We denote the class of $\omega$-languages recognized by an SPBA (PPBA, RPA, RPBA, LPBA) by \ensuremath{\Lmc_\mathsf{SPBA}}\xspace (\ensuremath{\Lmc_\mathsf{PPBA}}\xspace, \ensuremath{\Lmc_\mathsf{RPA}}\xspace, \ensuremath{\Lmc_\mathsf{RPBA}}\xspace, \ensuremath{\Lmc_\mathsf{LPBA}}\xspace). Furthermore, denote by $\ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace$ the class of $\omega$-languages of the form $\bigcup_i U_iV_i^\omega$, where the $U_i$ and $V_i$ are Parikh-recognizable, by $\ensuremath{\Lmc_\mathsf{PA, Reg}^\omega}\xspace$ such languages where the $U_i$ are Parikh-recognizable and the $V_i$ are regular, and by $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$ such languages where the $U_i$ are regular and the $V_i$ are Parikh-recognizable.
As shown by Guhe et al.\ we have $\ensuremath{\Lmc_\mathsf{RPA}}\xspace \subsetneq \ensuremath{\Lmc_\mathsf{PPBA}}\xspace$ \cite{infiniteZimmermann}. Likewise, Grobler et al.~\cite{infiniteOurs} have shown $\ensuremath{\Lmc_\mathsf{PPBA}}\xspace \subsetneq \ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace \subsetneq \ensuremath{\Lmc_\mathsf{SPBA}}\xspace$. We conclude this section by showing $\ensuremath{\Lmc_\mathsf{RPA}}\xspace \subsetneq \ensuremath{\Lmc_\mathsf{RPBA}}\xspace \subsetneq \ensuremath{\Lmc_\mathsf{PPBA}}\xspace$. In the next section we show that $\ensuremath{\Lmc_\mathsf{RPBA}}\xspace = \ensuremath{\Lmc_\mathsf{LPBA}}\xspace = \ensuremath{\Lmc_\mathsf{PA, Reg}^\omega}\xspace$.

\begin{lemma}
\label{lem:RPARPBA}
$\ensuremath{\Lmc_\mathsf{RPA}}\xspace \subsetneq \ensuremath{\Lmc_\mathsf{RPBA}}\xspace$.
\end{lemma}
\begin{proof}
 We show $\ensuremath{\Lmc_\mathsf{RPA}}\xspace \subseteq \ensuremath{\Lmc_\mathsf{RPBA}}\xspace$. Strictness follows from \Cref{lem:RPAregular}.
 The proof is very similar to the proof that $\ensuremath{\Lmc_\mathsf{RPA}}\xspace \subsetneq \ensuremath{\Lmc_\mathsf{PPBA}}\xspace$ \cite[Theorem 3]{infiniteZimmermann}.
 Let $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F, C)$ be an RPA. The idea is to create two copies of $\ensuremath{\mathcal{A}}\xspace$, where the second copy is modified such that all counters are zero and all states are accepting. Then we use non-determinism to guess the accepting hit and transition into the second copy where the counters are frozen and all states are accepting.
 Let $\ensuremath{\mathcal{A}}\xspace' = (Q', \Sigma, q_0, \Delta', F', C)$ where $Q' = \{q, q' \mid q \in Q\}$, $F' = \{q' \mid q \in Q\}$ and $ \Delta' = \Delta \cup \{(p',a, \ensuremath{\mathbf{0}}\xspace, q') \mid (p, a, \ensuremath{\mathbf{v}}\xspace, q) \in \Delta\} \cup \{(p, a, \ensuremath{\mathbf{v}}\xspace, q') \mid (p, a, \ensuremath{\mathbf{v}}\xspace, q) \in \Delta, q \in F\}$ be a RPBA.
 We claim that $R_\omega(\ensuremath{\mathcal{A}}\xspace) = B_\omega(\ensuremath{\mathcal{A}}\xspace')$.

 \smallskip
 $\Rightarrow$ To show $R_\omega(\ensuremath{\mathcal{A}}\xspace) \subseteq B_\omega(\ensuremath{\mathcal{A}}\xspace')$, let $\alpha \in R_\omega(\ensuremath{\mathcal{A}}\xspace)$ with accepting run $r = r_1 r_2 r_3 \dots$ where $r_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$. Let $i \geq 1$ be an arbitrary position such that there is an accepting hit in $r_i$ (which exists by definition). Let $r'_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{0}}\xspace, p_i')$ and define $r'_j = (p'_{j-1}, \alpha_j, \ensuremath{\mathbf{0}}\xspace, p'_j)$ for all $j > i$.
 Then $r'=r_1 r_2 \dots r_{i-1} r'_i r'_{i+1} r'_{i+2} \dots$ is a run of $\ensuremath{\mathcal{A}}\xspace'$ on $\alpha$.
 Furthermore, $r'$ is accepting: the accepting hit in $r_i$ translates one-to-one to an accepting hit in $r'_i$. Furthermore, all $p_j$ for $j \geq i$ are accepting by the definition of $F'$. Hence, $r'$ is accepting, thus $\alpha \in B_\omega(\ensuremath{\mathcal{A}}\xspace')$.

 \smallskip
 $\Leftarrow$ To show $B_\omega(\ensuremath{\mathcal{A}}\xspace') \subseteq R_\omega(\ensuremath{\mathcal{A}}\xspace)$, let $\alpha \in B_\omega(\ensuremath{\mathcal{A}}\xspace')$ with accepting run $r' = r'_1 r'_2 r'_3 \dots$ where $r'_i = (\hat p_{i-1}, \alpha_i, \ensuremath{\mathbf{v}}\xspace_i, \hat p_i)$ with $\hat p_i \in \{p_i, p'_i\}$. Again, let $i \geq 1$ be an arbitrary position such that there is an accepting hit in $r'_i$.
 As there are no accepting states in the first copy of $\ensuremath{\mathcal{A}}\xspace$ in $\ensuremath{\mathcal{A}}\xspace'$, there is a point where $r$ transitions from the first copy to the second copy, i.\,e.\xspace, there is a $j \leq i$ such that $r'_j = (p_{j-1}, \alpha_j, \ensuremath{\mathbf{v}}\xspace_j, p_j')$.
 Observe that the counters are frozen after transitioning to the second copy, hence, we have $\rho(r'_1 \dots r'_i) = \rho(r'_1 \dots r'_j) \in C$. Furthermore, we have $p_j \in F$ by the choice of $\Delta'$.
 Finally, observe that $\hat p_\ell = p_\ell$ for all $\ell < j$, and $\hat p_\ell = p'_\ell$ for all $\ell \geq j$.
 Hence, we can replace $r'_j$ by $r_j = (p_{j-1}, \alpha_j, \ensuremath{\mathbf{v}}\xspace_j, p_j)$, and for all $\ell > j$ we replace $r'_\ell$ by $r_\ell = (p_{\ell - 1}, \alpha_\ell, \ensuremath{\mathbf{v}}\xspace_\ell, p_\ell)$, where $\ensuremath{\mathbf{v}}\xspace_\ell$ is arbitrary such that $r_\ell \in \Delta$ (observe that at least one such $\ensuremath{\mathbf{v}}\xspace$ exists by definition of $\Delta'$). Then $r = r'_1 r'_2 \dots r'_{j-1} r_j r_{j+1} r_{j+2} \dots$ is a run of $\ensuremath{\mathcal{A}}\xspace$ on $\alpha$ that is furthermore accepting as witnessed by the accepting hit in $r_j$. Hence $\alpha \in R_\omega(\ensuremath{\mathcal{A}}\xspace)$.
\end{proof}

Observe that a very similar construction can be used to turn an arbitrary RPBA into an equivalent PPBA. The only difference is that we choose $F' = \{q' \mid q \in F\}$. Hence we obtain the following corollary.
\begin{corollary}
\label{cor:LRPBAtoLPPBA}
$\ensuremath{\Lmc_\mathsf{RPBA}}\xspace \subseteq \ensuremath{\Lmc_\mathsf{PPBA}}\xspace$.
\end{corollary}

Finally, we show that this inclusion is also strict.
\begin{lemma}
\label{lem:LRPBAstrict}
 There is an $\omega$-language that is PPBA-recognizable but not RPBA-recognizable.
\end{lemma}
\begin{proof}
    Consider $L = \{\alpha \in \{a,b\}^\omega \mid |\alpha[1, i]|_a = |\alpha[1,i]|_b \text{ for infinitely many $i$}\}$, which is obviously PPBA-recognazable.

    Assume that $L$ is recognized by an RPBA $\ensuremath{\mathcal{A}}\xspace$ and let $n$ be the number of states of $\ensuremath{\mathcal{A}}\xspace$. Consider an accepting run $r = r_1 r_2 r_3\ldots$ of $\ensuremath{\mathcal{A}}\xspace$ on $\alpha = (a^n b^n)^\omega$ where $r_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$, and let $k$ be the position of the accepting hit, i.\,e.\xspace $p_k \in F$ and $\rho(r_1 \dots r_k) \in C$. By definition there are infinitely many $j \geq 1$ (and hence infinitely many $j \geq k$) such that $p_j \in F$.
    By the pigeonhole principle, there is a state $q$ that is visited twice while reading an arbitrary $a^n$-infix, say at positions $k \leq c < d$, i.\,e.\xspace, $p_c = p_d = q$ and $d - c < n$.
    Hence, we can pump an infix of the form $a^{d-c}$ and obtain an accepting run on an infinite word of the form $(a^n b^n)^* (a^{n + d - c} b^n) (a^n b^n)^\omega$, which is not in~$L$, a contradiction.
\end{proof}

\section{Characterization of \ensuremath{\Lmc_\mathsf{PA, Reg}^\omega}\xspace by limit PBA and reachability PBA}
The main goal of this section is to prove the following theorem.
\begin{theorem}
\label{thm:LimitEqualsReach}
 The following are equivalent for all $\omega$-languages $L \subseteq \Sigma^\omega$.
 \begin{enumerate}
    \item $L$ is of the form $\bigcup_i U_i V_i^\omega$, where $U_i \in \Sigma^*$ is Parikh-recognizable, and $V_i \subseteq \Sigma^*$ is regular.
    \item $L$ is LPBA-recognizable.
    \item $L$ is RPBA-recognizable.
\end{enumerate}
\end{theorem}

Observe that in the first item we may assume that $L$ is of the form $\bigcup_i U_i V_i$, where \mbox{$U_i \in \Sigma^*$} is Parikh-recognizable, and $V_i \subseteq \Sigma^\omega$ is $\omega$-regular. Then, by simple combinatorics and Büchi's theorem we have $\bigcup_i U_i V_i = \bigcup_i U_i (\bigcup_{j_i} X_{j_i} Y_{j_i}^\omega) = \bigcup_{i, j_i} U_i (X_{j_i} Y_{j_i}^\omega) = \bigcup_{i, j_i} (U_i X_{j_i}) Y_{j_i}^\omega$, for regular languages $X_{j_i}, Y_{j_i}$, where $U_i X_{j_i}$ is regular, as regular languages are closed under concatenation.

To simplify the proof, it is convenient to consider the following generalizations of Büchi automata. A \emph{generalized Büchi automaton} (GBA) is a tuple $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, \ensuremath{\mathcal{F}}\xspace)$ where $Q, \Sigma, q_0$ and $\Delta$ are defined as for BA, and $\ensuremath{\mathcal{F}}\xspace \subseteq 2^Q$ is a collection of sets of accepting states. Then a run $r_1 r_2 r_3 \dots$ with $r_i = (p_{i-1}, \alpha_i, p_i)$ is accepting if for all $F \in \ensuremath{\mathcal{F}}\xspace$ there are infinitely many $i$ such that $p_i \in F$. It is well-known that GBA are not more expressive than BA, see e.\,g.\xspace \cite[Theorem 4.56]{modelchecking}.

Furthermore, we consider a variant of GBA where acceptance is not defined via states that are seen infinitely often, but rather via transitions that are used infinitely often. A \emph{Generalized Transition Büchi Automaton} (GTBA) is a tuple $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, \ensuremath{\mathcal{T}}\xspace)$ where $\ensuremath{\mathcal{T}}\xspace \subseteq 2^\Delta$ is a collection of sets of transitions. Then a run $r_1 r_2 r_3 \dots$ is accepting if for all $T \in \ensuremath{\mathcal{T}}\xspace$ there are infinitely many $i$ such that $r_i \in T$.

\begin{lemma}\label{lem:GTBA-BA}
GTBA and BA have the same expressiveness.
\end{lemma}

\begin{proof}
Obviously, every BA can be turned into an equivalent GTBA by choosing $\ensuremath{\mathcal{T}}\xspace = \{ \{(p,a,q) \mid q \in F\}\}$, hence we focus on the other direction.

Let $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, \ensuremath{\mathcal{T}}\xspace)$ be a GTBA. As GBA are as expressive as BA, it is sufficient to convert $\ensuremath{\mathcal{A}}\xspace$ into an equivalent GBA.
The idea is basically to consider the line graph of $\ensuremath{\mathcal{A}}\xspace$, that is, to use $\Delta$ as the new state set, keeping the initial state.
Then there is a $b$-transition from the \emph{state} $(p, a, q)$ to every state of the form $(q, b, t)$. Hence, the acceptance component translates directly.
To be precise, we construct the GBA $\ensuremath{\mathcal{A}}\xspace' = (\Delta \cup \{q_0\}, \Sigma, q_0, \Delta', \ensuremath{\mathcal{T}}\xspace)$ where $\Delta' = \{((p,a,q), b, (q,b,t) \mid (p,a,q), (q,b,t) \in \Delta\} \cup \{(q_0, a, (q_0, a, q) \mid (q_0, a, q) \in \Delta\}$. It is now easily verified that $L_\omega(\ensuremath{\mathcal{A}}\xspace) = L_\omega(\ensuremath{\mathcal{A}}\xspace')$.
\end{proof}

\Cref{thm:LimitEqualsReach} will be a direct consequence from the following lemmas. The first lemma shows the implication $(1) \Rightarrow (2)$.

\begin{lemma}
 If $L \in \ensuremath{\Lmc_\mathsf{PA, Reg}^\omega}\xspace$, then $L$ is LPBA-recognizable.
\end{lemma}
\begin{proof}
    First observe that $\ensuremath{\Lmc_\mathsf{LPBA}}\xspace$ is closed under union (this can be shown using a standard construction).
    Hence, it is sufficient to show how to construct an LPBA for an $\omega$-language of the form $L = UV^\omega$, where $U$ is Parikh-recognizable and $V$ is regular.

    Let $\ensuremath{\mathcal{A}}\xspace_1 = (Q_1, \Sigma, q_1, \Delta_1, F_1, C)$ be a PA with $L(\ensuremath{\mathcal{A}}\xspace_1) = U$ and $\ensuremath{\mathcal{A}}\xspace_2 = (Q_2, \Sigma, q_2, \Delta_2, F_2)$ be a Büchi automaton with $L_\omega(\ensuremath{\mathcal{A}}\xspace_2) = V^\omega$. We use the following standard construction for concatenation. Let $\ensuremath{\mathcal{A}}\xspace = (Q_1 \cup Q_2, \Sigma, q_1, \Delta, F_2, C)$ be an LPBA where
    $$\Delta = \Delta_1 \cup \{(p, a, \ensuremath{\mathbf{0}}\xspace, q) \mid (p, a, q) \in \Delta_2\} \cup \{(f, a, \ensuremath{\mathbf{0}}\xspace, q) \mid (q_2, a, q) \in \Delta_2, f \in F_1\}.$$
    We claim that $L_\omega(\ensuremath{\mathcal{A}}\xspace) = L$.

    \smallskip
    $\Rightarrow$ To show $L_\omega(\ensuremath{\mathcal{A}}\xspace) \subseteq L$, let $\alpha \in L_\omega(\ensuremath{\mathcal{A}}\xspace)$ with accepting run $r_1 r_2 r_3 \dots$ where $r_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$. As only the states in $F_2$ are accepting, there is a position $j$ such that $p_{j-1} \in F_1$ and $p_j \in Q_2$.
    In particular, all transitions of the copy of $\ensuremath{\mathcal{A}}\xspace_2$ are labeled with $\ensuremath{\mathbf{0}}\xspace$, i.\,e.\xspace, $\ensuremath{\mathbf{v}}\xspace_i = \ensuremath{\mathbf{0}}\xspace$ for all $i \geq j$. Hence $\rho(r) = \rho(r_1 \dots r_{j-1}) \in C$ (in particular, there is no $\infty$ value in $\rho(r)$).
    We observe that $r_1 \dots r_{j-1}$ is an accepting run of $\ensuremath{\mathcal{A}}\xspace_1$ on $\alpha[1,j-1]$, as $p_{j-1} \in F_1$ and $\rho(r_1 \dots r_{j-1}) \in C$.
    For all $i \geq j$ let $r'_i = (p_{i-1}, \alpha_i, p_i)$. Now observe that $(q_2, \alpha_j, p_j)r'_{j+1} r'_{j+2} \dots$ is an accepting run of $\ensuremath{\mathcal{A}}\xspace_2$ on $\alpha_j \alpha_{j+1} \alpha_{j+2} \dots$, hence $\alpha \in L(\ensuremath{\mathcal{A}}\xspace_1) \cdot L_\omega(\ensuremath{\mathcal{A}}\xspace_2) = L$.

    \smallskip
    $\Leftarrow$ To show $L = UV^\omega \subseteq L_\omega(\ensuremath{\mathcal{A}}\xspace)$, let $w \in L(\ensuremath{\mathcal{A}}\xspace_1)=U$ with accepting run $s$, and $\alpha \in L_\omega(\ensuremath{\mathcal{A}}\xspace_2)=V^\omega$ with accepting run $r = r_1 r_2 r_3 \dots$, where $r_i = (p_{i-1}, \alpha_1, p_i)$.
    Observe that~$s$ is also a partial run of $\ensuremath{\mathcal{A}}\xspace$ on $w$, ending in an accepting state $f$. By definition of~$\Delta$, we can continue the run $s$ in $\ensuremath{\mathcal{A}}\xspace$ basically as in $r$. To be precise, let $r'_1 = (f, \alpha_1, \ensuremath{\mathbf{0}}\xspace, p_1)$, and, for all $i > 1$ let $r'_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{0}}\xspace, p_i)$. Then $s r'_1 r'_2 r'_3 \dots$ is an accepting run of $\ensuremath{\mathcal{A}}\xspace$ on $w \alpha$, hence $w \alpha \in L_\omega(\ensuremath{\mathcal{A}}\xspace)$.
\end{proof}

Observe that the construction in the proof of the lemma works the same way when we interpret $\ensuremath{\mathcal{A}}\xspace$ as an RPBA (every visit of an accepting state has the same good counter value; this argument is even true if we interpret $\ensuremath{\mathcal{A}}\xspace$ as a PPBA), showing the implication~$(1) \Rightarrow (3)$.
\begin{corollary}
If $L \in \ensuremath{\Lmc_\mathsf{PA, Reg}^\omega}\xspace$, then $L$ is RPBA-recognizable.
\end{corollary}

For the backwards direction we need an auxiliary lemma, essentially stating that semi-linear sets over $C \subseteq (\ensuremath{\mathbb{N}}\xspace \cup \{\infty\})^d$ can be modified such that $\infty$-entries in vectors in~$C$ are replaced by arbitrary integers, and remain semi-linear.

\begin{lemma}
    \label{lem:semi-linear-inf}
    Let $C \subseteq (\ensuremath{\mathbb{N}}\xspace \cup \{\infty\})^d$ be semi-linear and $D \subseteq \{1, \dots, d\}$. Let $C_D \subseteq \ensuremath{\mathbb{N}}\xspace^d$ be the set obtained from $C$ by the following procedure.
    \begin{enumerate}
        \item Remove every vector $\ensuremath{\mathbf{v}}\xspace = (v_1, \dots, v_d)$ where $v_i = \infty$ for an $i \notin D$.
        \item As long as $C_D$ contains a vector $\ensuremath{\mathbf{v}}\xspace = (v_1, \dots, v_n)$ with $v_i = \infty$ for an $i \leq d$: replace $\ensuremath{\mathbf{v}}\xspace$ by all vectors of the form $(v_1, \dots v_{i-1}, z, v_{i+1}, \dots, v_d)$ for $z \in \ensuremath{\mathbb{N}}\xspace$.
    \end{enumerate}
    Then $C_D$ is semi-linear.
\end{lemma}
\begin{proof}
For a vector $\ensuremath{\mathbf{v}}\xspace = (v_1, \dots, v_d) \in (\ensuremath{\mathbb{N}}\xspace \cup \{\infty\})^d$, let $\ensuremath{\mathsf{Inf}}(\ensuremath{\mathbf{v}}\xspace) = \{i \mid v_i = \infty\}$ denote the positions of $\infty$-entries in $\ensuremath{\mathbf{v}}\xspace$.
Furthermore, let $\bar\ensuremath{\mathbf{v}}\xspace = (\bar{v}_1, \dots, \bar{v}_d)$ denote the vector obtained from $v$ by replacing every $\infty$-entry by 0, i.\,e.\xspace, $\bar{v}_i = 0$ if $v_i = \infty$, and $\bar{v}_i = v_i$ otherwise.

We carry out the following procedure for every linear set of the semi-linear set independently, hence we assume that $C = \{b_0 + b_1z_1 + \dots + b_\ell z_\ell \mid z_1, \dots, z_\ell \in \ensuremath{\mathbb{N}}\xspace\}$ is linear.
We also assume that there is no $b_j$ with $\ensuremath{\mathsf{Inf}}(b_j) \not\subseteq D$, otherwise, we simply remove it.

Now, if $\ensuremath{\mathsf{Inf}}(b_0) \not\subseteq D$, then $C_D = \varnothing$.
Otherwise, $C_D = \{b_0 + \sum_{j\leq \ell} \bar{b}_j z_j + \sum_{i \in \ensuremath{\mathsf{Inf}}(b_j)} \ensuremath{\mathbf{e}}\xspace_i z_{ij} \mid z_j, z_{ij} \in \ensuremath{\mathbb{N}}\xspace\}$, which is linear by definition.
\end{proof}

We are now ready to prove the following lemma, showing the implication $(2) \Rightarrow (1)$.
\begin{lemma}
If $L$ is LPBA-recognizable, then $L \in \ensuremath{\Lmc_\mathsf{PA, Reg}^\omega}\xspace$.
\end{lemma}
\begin{proof}
    Let $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F, C)$ be an LPBA of dimension $d$. The idea is as follows. We guess a subset $D \subseteq \{1, \dots, d\}$ of counters whose values we expect to be $\infty$.
    Observe that every counter not in $D$ has a finite value, hence for every such counter there is a point where all transitions do not increment the counter further.
    For every subset $D \subseteq \{1, \dots, d\}$ we decompose $\ensuremath{\mathcal{A}}\xspace$ into a PA and a GTBA. In the first step we construct a PA where every counter not in $D$ reaches its final value and is verified. In the second step we construct a GTBA ensuring that for every counter in $D$ at least one transition adding a non-zero value to that counter is used infinitely often. This can be encoded directly into the GTBA. Furthermore we delete all transitions that modify counters not in $D$.

    Fix $D \subseteq \{1, \dots, d\}$ and $f \in F$, and define the PA $\ensuremath{\mathcal{A}}\xspace^D_f = (Q, \Sigma, q_0, \Delta, \{f\}, C_D)$ where~$C_D$ is defined as in \Cref{lem:semi-linear-inf}.
    Furthermore, we define the GTBA $\ensuremath{\mathcal{B}}\xspace^D_f = (Q, \Sigma, f, \Delta^D, \ensuremath{\mathcal{T}}\xspace^D)$ where $\Delta^D$ contains the subset of transitions of $\Delta$ where the counters not in $D$ have zero-values (just the transitions without vectors for the counters, as we construct a GTBA). On the other hand, for every counter $i$ in $D$ there is one acceptance component in $\ensuremath{\mathcal{T}}\xspace^D$ that contains exactly those transitions (again without vectors) where the $i$-th counter has a non-zero value. Finally, we encode the condition that at least one accepting state in $F$ needs to by seen in $\ensuremath{\mathcal{T}}\xspace^D$ by further adding the component $\{(p, a, q) \in \Delta \mid q \in F\}$.

    We claim that $L_\omega(\ensuremath{\mathcal{A}}\xspace) = \bigcup_{D \subseteq \{1, \dots, d\}, f \in F} L(\ensuremath{\mathcal{A}}\xspace^D_f)\cdot L_\omega(\ensuremath{\mathcal{B}}\xspace^D_f)$, which by the comment below \Cref{thm:LimitEqualsReach} and \Cref{lem:GTBA-BA} implies the statement of the lemma.

    \smallskip
    $\Rightarrow$ To show $L_\omega(\ensuremath{\mathcal{A}}\xspace) \subseteq \bigcup_{D \subseteq \{1, \dots, d\}, f \in F} L(\ensuremath{\mathcal{A}}\xspace^D_f) \cdot L_\omega(\ensuremath{\mathcal{B}}\xspace^D_f)$, let $\alpha \in L_\omega(\ensuremath{\mathcal{A}}\xspace)$ with accepting run $r_1 r_2 r_3 \dots$ where $r_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$. Let $D$ be the positions of $\infty$-entries in $\rho(r) = (v_1, \dots, v_d)$. As the $v_i$ with $i \notin D$ have integer values, there is a position $j$ such that in all $\ensuremath{\mathbf{v}}\xspace_k$ for $k \geq j$ the $i$-th entry of $\ensuremath{\mathbf{v}}\xspace_k$ is 0. Let $\ell \geq j$ be minimal such that $p_\ell$ in $F$. We split $\alpha = w \beta$, where $w = \alpha[1,\ell]$, and $\beta = \alpha_{\ell + 1} \alpha_{\ell +2} \dots$.

    First we argue that $w \in L_\omega(\ensuremath{\mathcal{A}}\xspace^D_{p_{\ell}})$. Observe that $\ensuremath{\mathcal{A}}\xspace^D_{p_{\ell}}$ inherits all transitions from $\ensuremath{\mathcal{A}}\xspace$, hence $r_1 \dots r_{\ell}$ is a run of $\ensuremath{\mathcal{A}}\xspace^D_{p_{\ell}}$ on $w$. As $p_\ell$ is accepting by definition, it remains to show that $\rho(r_1, \dots r_\ell) \in C_D$.
    By the choice of $\ell$, all counters not in $D$ have reached their final values. As $C_D$ contains all vectors of $C$ where all $\infty$-entries are replaced by arbitrary values, the claim follows, hence $w \in L(\ensuremath{\mathcal{A}}\xspace^D_{p_{\ell}})$.

    Now we argue that $\beta \in L_\omega(\ensuremath{\mathcal{B}}\xspace^D_{p_\ell})$. For every $k > \ell$ define $r'_k = (p_{k-1}, \alpha_k, p_k)$. Observe that $r' = r'_{k+1} r'_{k+2} \dots$ is a run of $\ensuremath{\mathcal{B}}\xspace^D_{p_\ell}$ on $\beta$ (all $r'_{k+1}$ exist in $\ensuremath{\mathcal{B}}\xspace^D_{p_\ell}$, as the counters not on~$D$ of all transitions $r_k$ have zero-values by the definition of $\ell$).
    It remains to show that~$r'$ is accepting, i.\,e.\xspace, that for every counter in $D$ at least one transition with a non-zero values is used infinitely often, and an accepting state is visited infinitely often. This is the case, as these counter values are $\infty$ in $\rho(r)$ and by the acceptance condition of LPBA, hence $\beta \in L_\omega(\ensuremath{\mathcal{B}}\xspace^D_{p_\ell})$.

    We conclude $\alpha \in \bigcup_{D \subseteq \{1, \dots, d\}, f \in F} L(\ensuremath{\mathcal{A}}\xspace^D_f) \cdot L_\omega(\ensuremath{\mathcal{B}}\xspace^D_f)$. \hfill $\lrcorner$

\smallskip
    $\Leftarrow$ To show $\bigcup_{D \subseteq \{1, \dots, d\}, f \in F} L(\ensuremath{\mathcal{A}}\xspace^D_f) \cdot L_\omega(\ensuremath{\mathcal{B}}\xspace^D_f) \subseteq L_\omega(\ensuremath{\mathcal{A}}\xspace)$, let $w \in L(\ensuremath{\mathcal{A}}\xspace^D_f)$ and $\beta \in L_\omega(\ensuremath{\mathcal{B}}\xspace^D_f)$ for some $D \subseteq \{1, \dots, d\}$ and $f \in F$. We show that $w\beta \in L_\omega(\ensuremath{\mathcal{A}}\xspace)$.

    Let $s$ be an accepting run of $\ensuremath{\mathcal{A}}\xspace^D_f$ on $w$, which ends in the accepting state $f$ by definition. Let $\rho(s) = (v_1, \dots, v_d)$. By definition of $C_D$, there is a vector $\ensuremath{\mathbf{u}}\xspace = (u_1, \dots, u_d)$ in $C$ where $u_i = \infty$ if $i \in D$, and $u_i = v_i$ if $i \notin D$.
    Furthermore, let $r = r_1r_2r_3\dots$, where $r_i = (p_{i-1}, \alpha_i, p_i)$, be an accepting run of $\ensuremath{\mathcal{B}}\xspace^D_f$ on $\beta$, which starts in the accepting state~$f$ by definition.
    By definition of $\ensuremath{\mathcal{T}}\xspace^d$, for every counter $i \in D$ at least one transition where the $i$-th counter of the corresponding transition in $\Delta$ is non-zero is used infinitely often.
    Hence, let $r' = r'_1 r'_2 r'_3 \dots$ where $r'_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$ for a suitable vector $\ensuremath{\mathbf{v}}\xspace_i$.
    Furthermore, the labels of transitions of counters not in $D$ have a value of zero, hence $\rho(r') = (x_1, \dots, x_d)$, where $x_i = \infty$ if $i \in D$, and $x_i = 0$ if $i \notin D$.
    A technical remark: it might be the case that there are more than one transitions in $\Delta$ that collapse to the same transition in $\Delta^D$, say $\delta_1 = (p, a, \ensuremath{\mathbf{u}}\xspace, q)$ and $\delta_2 = (p, a, \ensuremath{\mathbf{v}}\xspace, q)$ appear in $\Delta$ and collapse to $(p, a, q)$ in $\Delta^D$. If both transitions, $\delta_1$ and $\delta_2$, are seen infinitely often, we need to take care that we also see both infinitely often when translating the run $r$ back. This is possible using a round-robin procedure.

    Now observe that $sr'$ is a run of $\ensuremath{\mathcal{A}}\xspace$ on $w\beta$ (recall that $s$ ends in $f$, and $r'$ starts in $f$). Furthermore, we have $\rho(sr') = \rho(s) + \rho(r') = (v_1 + x_1, \dots, v_d + x_d)$, where $v_i + x_i = \infty$ if $i \in D$, and $v_i + x_i = v_i$ if $i \notin D$ by the observations above. Hence $\rho(sr') \in C$. Finally, $\ensuremath{\mathcal{T}}\xspace^D$ enforces that at least one accepting state in $\ensuremath{\mathcal{B}}\xspace^D_f$ is seen infinitely often, hence $w\beta \in L_\omega(\ensuremath{\mathcal{A}}\xspace)$.
\end{proof}

Finally we show the implication $(3) \Rightarrow (1)$.
\begin{lemma}
    If $L$ is RPBA-recognizable, then $L \in \ensuremath{\Lmc_\mathsf{PA, Reg}^\omega}\xspace$.
\end{lemma}
\begin{proof}
    Let $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F, C)$ be an RPBA. The intuition is as follows. An RPBA just needs to verify the counters a single time. Hence, we can recognize the prefixes of infinite words $\alpha \in B_\omega(\ensuremath{\mathcal{A}}\xspace)$ that generate the accepting hit with a PA. Further checking that an accepting state is seen infinitely often can be done with a Büchi automaton.

    Fix $f \in F$ and let $\ensuremath{\mathcal{A}}\xspace_f = (Q, \Sigma, q_0, \Delta, \{f\}, C)$ be the PA that is syntactically equal to $\ensuremath{\mathcal{A}}\xspace$ with the only difference that $f$ is the only accepting state. Similarly, let $\ensuremath{\mathcal{B}}\xspace_f = (Q, \Sigma, f, \{(p,a,q) \mid (p,a,\ensuremath{\mathbf{v}}\xspace, q) \in \Delta\}, F)$ be the Büchi automaton obtained from $\ensuremath{\mathcal{A}}\xspace$ by setting $f$ as the initial state and the forgetting the vector labels.

    We claim that $B_\omega(\ensuremath{\mathcal{A}}\xspace) = \bigcup_{f \in F} L(\ensuremath{\mathcal{A}}\xspace_f) \cdot L_\omega(\ensuremath{\mathcal{B}}\xspace_f)$.

\smallskip
    $\Rightarrow$ To show $B_\omega(\ensuremath{\mathcal{A}}\xspace) \subseteq \bigcup_{f \in F} L(\ensuremath{\mathcal{A}}\xspace_f) \cdot L_\omega(\ensuremath{\mathcal{B}}\xspace_f)$, let $\alpha \in B_\omega(\ensuremath{\mathcal{A}}\xspace)$ with accepting run $r = r_1 r_2 r_3 \dots$ where $r_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$. Let $k$ be arbitrary such that there is an accepting hit in $r_k$ (such a $k$ exists by definition) and consider the prefix $\alpha[1,k]$. Obviously $r_1 \dots r_k$ is an accepting run of $\ensuremath{\mathcal{A}}\xspace_{p_k}$ on $\alpha[1,k]$.
    Furthermore, there are infinitely many $j$ such that $p_j \in F$ by definition. In particular, there are also infinitely many $j \geq k$ with this property. Let $r'_i = (p_{i-1}, \alpha_i, p_i)$ for all $i > k$.
    Then $r'_{k+1} r'_{k+2} \dots$ is an accepting run of $\ensuremath{\mathcal{B}}\xspace_{p_k}$ on $\alpha_{k+1} \alpha_{k+2}\dots$ (recall that $p_k$ is the initial state of $\ensuremath{\mathcal{B}}\xspace_{p_k}$). Hence we have $\alpha[1,k] \in L(\ensuremath{\mathcal{A}}\xspace_{p_k})$ and $\alpha_{k+1} \alpha_{k+2} \dots \in L_\omega(\ensuremath{\mathcal{B}}\xspace_{p_k})$.

    \smallskip
    $\Leftarrow$ To show $\bigcup_{f \in F} L(\ensuremath{\mathcal{A}}\xspace_f) \cdot L_\omega(\ensuremath{\mathcal{B}}\xspace_f) \subseteq B_\omega(\ensuremath{\mathcal{A}}\xspace)$, let $w \in L(\ensuremath{\mathcal{A}}\xspace_f)$ and $\beta \in L_\omega(\ensuremath{\mathcal{B}}\xspace_f)$ for some $f \in F$. We show $w\beta \in B_\omega(\ensuremath{\mathcal{A}}\xspace)$.
    Let $s = s_1 \dots s_n$ be an accepting run of $\ensuremath{\mathcal{A}}\xspace_f$ on $w$, which ends in the accepting state $f$ with $\rho(s) \in C$ by definition.
    Furthermore, let $r = r_1 r_2 r_3 \dots$ be an accepting run of $\ensuremath{\mathcal{B}}\xspace^D_f$ on $\beta$ which starts in the accepting state $f$ by definition. It is now easily verified that $sr'$ with $r' = r'_1r'_2r'_3\dots$ where $r'_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$ (for an arbitrary $\ensuremath{\mathbf{v}}\xspace_i$ such that $r'_i \in \Delta)$ is an accepting run of $\ensuremath{\mathcal{A}}\xspace$ on $w\beta$, as there is an accepting hit in $s_n$, and the (infinitely many) visits of an accepting state in $r$ translate one-to-one, hence $w\beta \in B_\omega(\ensuremath{\mathcal{A}}\xspace)$.
\end{proof}

\section{Characterization of \ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace and \ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace}
In this section we give a characterization of $\ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace$ and a characterization of $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$. Grobler et al.~\cite{infiniteOurs} have shown that $\ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace \subsetneq \ensuremath{\Lmc_\mathsf{SPBA}}\xspace$, i.\,e.\xspace, SPBA are too strong to capture this class. However, restrictions of SPBA are a good candidate to capture $\ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace$ as well as $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$. In fact we show that it is sufficient to restrict the appearances of accepting states to capture $\ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace$, as specified by the first theorem of this section. Further restricting the vectors yields a model capturing $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$, as specified in the second theorem of this section. Recall that the condensation of $\ensuremath{\mathcal{A}}\xspace$ is the DAG of strong components of the underlying graph of $\ensuremath{\mathcal{A}}\xspace$.

\begin{theorem}
\label{thm:lpapa}
    The following are equivalent for all $\omega$-languages $L \subseteq \Sigma^\omega$.
    \begin{enumerate}
        \item $L$ is of the form $\bigcup_i U_i V_i^\omega$, where $U_i, V_i \subseteq \Sigma^*$ are Parikh-recognizable.
        \item $L$ is recognized by an SPBA $\ensuremath{\mathcal{A}}\xspace$ with the property that accepting states appear only in the leaves of the condensation of $\ensuremath{\mathcal{A}}\xspace$, and there is at most one accepting state per leaf.
    \end{enumerate}
\end{theorem}

In fact, the proof of Grobler et al.~\cite{infiniteOurs} showing $\ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace \subseteq \ensuremath{\Lmc_\mathsf{SPBA}}\xspace$ is constructive and \emph{almost} yields an SPBA with the desired property. A key notion are \emph{normalized} PA (on finite words), where a PA $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F)$ is normalized if $F = \{f\}$ and $f$ has no outgoing transitions. It was shown that one can, given a PA $\ensuremath{\mathcal{A}}\xspace$, construct a normalized PA $\ensuremath{\mathcal{A}}\xspace_N$ with $L(\ensuremath{\mathcal{A}}\xspace_N) = L(\ensuremath{\mathcal{A}}\xspace) \setminus \{\varepsilon\}$.
For our proofs it is convenient to introduce a similar, yet stronger notion.
\begin{lemma}\label{lem:AIO}
Let $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F, C)$ be a PA of dimension $d$. Then there exists a~PA~$\ensuremath{\mathcal{A}}\xspace^{IO}$ of dimension $d + 1$ with the following properties.
\begin{itemize}
    \item The initial state of $\ensuremath{\mathcal{A}}\xspace^{IO}$ is the only accepting state.
    \item $L(\ensuremath{\mathcal{A}}\xspace) \setminus \{\varepsilon\} = L(\ensuremath{\mathcal{A}}\xspace^{IO}) \setminus \{\varepsilon\}$.
    \item $SCC(\ensuremath{\mathcal{A}}\xspace) = \{Q\}$.
\end{itemize}
We say that $\ensuremath{\mathcal{A}}\xspace^{IO}$ is \emph{IO-normalized}.
\end{lemma}
\begin{proof}
    Define $\ensuremath{\mathcal{A}}\xspace^{IO} = \{Q \cup \{q_0'\}, \Sigma, q_0', \Delta^{IO}, \{q_0'\}, C \cdot \{1\})$, where
    \begin{align*}
    \Delta^{IO} =&\ \{(p, a, \ensuremath{\mathbf{v}}\xspace \cdot 0, q) \mid (p, a, \ensuremath{\mathbf{v}}\xspace, q) \in \Delta\} \\
    \cup&\ \{(q_0', a, \ensuremath{\mathbf{v}}\xspace \cdot 0, q) \mid (q_0, a, \ensuremath{\mathbf{v}}\xspace, q) \in \Delta\} \\ \cup&\ \{(p, a, \ensuremath{\mathbf{v}}\xspace \cdot 1, q_0') \mid (p, a, \ensuremath{\mathbf{v}}\xspace, f) \in \Delta, f \in F\} \\
    \cup&\ \{(q_0', a, \ensuremath{\mathbf{v}}\xspace \cdot 1, q_0') \mid (q_0, a, \ensuremath{\mathbf{v}}\xspace, f) \in \Delta, f \in F\}.
    \end{align*}

    That is, $\ensuremath{\mathcal{A}}\xspace^{IO}$ is obtained from $\ensuremath{\mathcal{A}}\xspace$ by adding a fresh state $q_0'$, which is the initial state and only accepting state, inherits all outgoing transitions from $q_0$ and all in-going transitions from the accepting states. Furthermore, all transitions get a new counter, which is set to 0 except for the new ingoing transitions of $q_0'$ where the counter is set to $1$, and all vectors in $C$ are concatenated with $1$.
    Finally, we remove all states that cannot reach $q'_0$ (such states can appear when shortcutting the ingoing transitions of $F$, and are useless in the sense that their removal does not change the accepted language; however, this removal is necessary for the third property).
    We claim that $L(\ensuremath{\mathcal{A}}\xspace) \setminus \{\varepsilon\} = L(\ensuremath{\mathcal{A}}\xspace^{IO}) \setminus \{\varepsilon\}$.

    \smallskip
    $\Rightarrow$ To show $L(\ensuremath{\mathcal{A}}\xspace) \setminus \{\varepsilon\} \subseteq L(\ensuremath{\mathcal{A}}\xspace^{IO}) \setminus \{\varepsilon\}$, let $w_1 \dots w_n \in L(\ensuremath{\mathcal{A}}\xspace)$ for $n \geq 1$ with accepting run $r = r_1 \dots r_n$ where $r_i = (p_{i-1}, w_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$.
    By definition of $\Delta^{IO}$, there is a transition $r'_1 = (q_0', w_1, \ensuremath{\mathbf{v}}\xspace_1 \cdot 0, p_1)$ as well as a transition $r'_n = (p_{n-1}, w_n, \ensuremath{\mathbf{v}}\xspace_n \cdot 1, q_0')$ (or in case $n = 1$ the loop $(q_0', w_1, \ensuremath{\mathbf{v}}\xspace_1 \cdot 1, q_0')$). For all $1 < i < n$ define $r'_i = (p_{i-1}, w_i, \ensuremath{\mathbf{v}}\xspace_i \cdot 0, p_i)$. It is now easily verified that $r'_1 \dots r'_n$ (or simply $(q_0', w_1, \ensuremath{\mathbf{v}}\xspace_1 \cdot 1, q_0')$) is an accepting run of $\ensuremath{\mathcal{A}}\xspace^{IO}$ on $w_1 \dots w_n$.

    \smallskip
    $\Leftarrow$ To show $L(\ensuremath{\mathcal{A}}\xspace^{IO}) \setminus \{\varepsilon\} \subseteq L(\ensuremath{\mathcal{A}}\xspace) \setminus \{\varepsilon\}$, let $w_1 \dots w_n \in L(\ensuremath{\mathcal{A}}\xspace^{IO})$ for $n \geq 1$ with accepting run $r' = r'_1 \dots r'_n$ where $r'_i = (p_{i-1}, w_i, \ensuremath{\mathbf{v}}\xspace_i \cdot c_i, p_i)$ with $c_i \in \{0,1\}$.
    Observe that $p_0 = p_n = q_0'$, and for all $0 < i < n$ we have $p_i \neq q_0'$ as enforced by the additional counter (that is, $c_n = 1$ and $c_i = 0$ for all $i < n$, as $C \cdot \{1\}$ is the semi-linear set of~$\ensuremath{\mathcal{A}}\xspace^{IO}$).
    By definition of $\Delta^{IO}$ there is a transition $r_1 = (q_0, w_1, \ensuremath{\mathbf{v}}\xspace_1, p_1)$, and a transition $r_n = (p_{n-1}, w_n, \ensuremath{\mathbf{v}}\xspace_n, f)$ for some $f \in F$ in $\Delta$ (or in case $n = 1$ the transition $(q_0, w_1, \ensuremath{\mathbf{v}}\xspace_1, f)$). For all $1 < i < n$ define $r_i = (p_{i-1}, w_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$. It is now easily verified that $r_1 \dots r_n$ (or simply $(q_0, w_1, \ensuremath{\mathbf{v}}\xspace_1, f)$) is an accepting run of $\ensuremath{\mathcal{A}}\xspace$ on $w_1 \dots w_n$.
\end{proof}
Observe that $L(\ensuremath{\mathcal{A}}\xspace)^\omega = L(\ensuremath{\mathcal{A}}\xspace^{IO})^\omega$ for every PA $\ensuremath{\mathcal{A}}\xspace$, as $L^\omega = (L \setminus \{\varepsilon\})^\omega$ for every language~$L$ by definition. In fact, it is easily observed that we even have $S_\omega(\ensuremath{\mathcal{A}}\xspace^{IO}) = L(\ensuremath{\mathcal{A}}\xspace)^\omega$. We are now ready to proof the main theorem.

\begin{proof}[Proof of \Cref{thm:lpapa}]
$(1) \Rightarrow (2)$. Let $\ensuremath{\mathcal{A}}\xspace_i = (Q_i, \Sigma, q_i, \Delta_i, F_i)$ for $i \in \{1,2\}$ be PA and let $L = L(\ensuremath{\mathcal{A}}\xspace_1) \cdot L(\ensuremath{\mathcal{A}}\xspace_2)^\omega$. By \Cref{lem:AIO} and the observation above we can equivalently write $L = L(\ensuremath{\mathcal{A}}\xspace_1) \cdot S_\omega(\ensuremath{\mathcal{A}}\xspace^{IO}_2)$.
As $\ensuremath{\mathcal{A}}\xspace^{IO}_2$ is IO-normalized it satisfies the property of the theorem.

We can now easily adapt the construction in \cite{infiniteOurs} showing that the concatenation of a Parikh-recognizable language and an SPBA-recognizable $\omega$-language is SPBA-recognizable to obtain an SPBA for $L(\ensuremath{\mathcal{A}}\xspace_1) \cdot S_\omega(\ensuremath{\mathcal{A}}\xspace^{IO}_2)$ that only keeps the accepting state of $\ensuremath{\mathcal{A}}\xspace^{IO}_2$, maintaining the property of the theorem. Finally, the closure under union is shown using a standard construction, hence combining SPBA with the desired property still yields an SPBA with the property.
Overall, we obtain an SPBA $\ensuremath{\mathcal{A}}\xspace$ recognizing $L$ where the only accepting states appear in the leaves of $C(\ensuremath{\mathcal{A}}\xspace)$. \hfill$\lrcorner$

\medskip
$(2) \Rightarrow (1)$. Let $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F, C)$ be an SPBA of dimension $d$ with the property of the theorem.
Let $f \in F$ and let $\ensuremath{\mathcal{A}}\xspace_f = (Q, \Sigma, q_0, \Delta_f, \{f\}, C \cdot \{1\})$ with $\Delta_{f} = \{p,a,\ensuremath{\mathbf{v}}\xspace \cdot 0,q) \mid (p,a,\ensuremath{\mathbf{v}}\xspace, q) \in \Delta, q \neq f\} \cup \{(p, a, \ensuremath{\mathbf{v}}\xspace \cdot 1, f) \mid (p, a, \ensuremath{\mathbf{v}}\xspace, f) \in \Delta\}$ be the PA of dimension $d+1$ obtained from $\ensuremath{\mathcal{A}}\xspace$ by setting $f$ as the only accepting state with an additional counter that is 0 at every transition except of the ingoing transitions of $f$, where the counter is set to 1.
Additionally all vectors in $C$ are concatenated with $1$. Similarly, let $\ensuremath{\mathcal{A}}\xspace_{f,f} = (Q, \Sigma, f, \Delta_{f}, \{f\}, C \cdot \{1\})$ be the PA of dimension $d+1$ obtained from $\ensuremath{\mathcal{A}}\xspace$ by setting $f$ as the initial state and only accepting state, where $\Delta_f$ is defined as for $\ensuremath{\mathcal{A}}\xspace_f$. We claim $S_\omega(\ensuremath{\mathcal{A}}\xspace) = \bigcup_{f \in F} L(\ensuremath{\mathcal{A}}\xspace_{f}) \cdot L(\ensuremath{\mathcal{A}}\xspace_{f,f})^\omega$.

\smallskip
$\Rightarrow$ To show $S_\omega(\ensuremath{\mathcal{A}}\xspace) \subseteq \bigcup_{f \in F} L(\ensuremath{\mathcal{A}}\xspace_{f}) \cdot L(\ensuremath{\mathcal{A}}\xspace_{f,f})^\omega$, let $\alpha \in S_\omega(\ensuremath{\mathcal{A}}\xspace)$ with accepting run $r = r_1 r_2 r_3 \dots$ where $r_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$. Let $k_1 < k_2 < \dots$ be the positions of accepting states in $r$, i.\,e.\xspace, $p_{k_i} \in F$ for all $i \geq 1$.
First observe that the property in the theorem implies $p_{k_i} = p_{k_j}$ for all $i, j \geq 1$, i.\,e.\xspace, no two distinct accepting states appear in~$r$, since accepting states appear only in different leaves of the condensation of $\ensuremath{\mathcal{A}}\xspace$.

For all $j \geq 1$ define $r'_j = (p_{j-1}, \alpha_j, \ensuremath{\mathbf{v}}\xspace_j \cdot 0, p_j)$ if $j \neq k_i$ for all $i \geq 1$, and $r'_j = (p_{j-1}, \alpha_j, \ensuremath{\mathbf{v}}\xspace_j \cdot 1, p_j)$ if $j = k_i$ for some $i \geq 1$, i.\,e.\xspace, we replace every transition $r_j$ by the corresponding transition in $\Delta_f$.

Now consider the partial run $r_1 \dots r_{k_1}$ and observe that $p_i \neq p_{k_1}$ for all $i < k_1$, and $\rho(r_1 \dots r_{k_1}) \in C$ by the definition of SPBA. Hence $r' = r'_1 \dots r'_{k_1}$ is an accepting run of~$\ensuremath{\mathcal{A}}\xspace_{p_{k_1}}$ on $\alpha[1, k_1]$, as only a single accepting state appears in $r'$, the newly introduced counter has a value of $1$ when entering $p_{k_1}$, i.\,e.\xspace, $\rho(r') \in C \cdot \{1\}$, hence $\alpha[1, k_1] \in L(\ensuremath{\mathcal{A}}\xspace_{p_{k_1}})$.

Finally, we show that $\alpha[k_i + 1, k_{i+1}] \in L(\ensuremath{\mathcal{A}}\xspace_{p_{k_1},p_{k_1}})$.
Observe that $r'_{k_i + 1} \dots r'_{k_{i+1}}$ is an accepting run of $\ensuremath{\mathcal{A}}\xspace_{p_{k_1},p_{k_1}}$ on $\alpha[k_1 + 1, k_{i+1}]$: we have $\rho(r_{k_i + 1} \dots r_{k_{i+1}}) = \ensuremath{\mathbf{v}}\xspace \in C$ by definition. Again, as only a single accepting state appears in $r'_{k_i + 1} \dots r_{k_{i+1}}$, we have $\rho(r'_{k_i + 1} \dots r_{k_{i+1}}) = \ensuremath{\mathbf{v}}\xspace \cdot 1 \in C \cdot \{1\}$, and hence $\alpha[k_1 + 1, k_{i+1}] \in L(\ensuremath{\mathcal{A}}\xspace_{p_{k_1},p_{k_1}})$. We conclude $\alpha \in L(\ensuremath{\mathcal{A}}\xspace_{p_{k_1}}) \cdot L(\ensuremath{\mathcal{A}}\xspace_{p_{k_1}, p_{k_1}})^\omega$.

\smallskip
$\Leftarrow$ To show $\bigcup_{f \in F} L(\ensuremath{\mathcal{A}}\xspace_{f}) \cdot L(\ensuremath{\mathcal{A}}\xspace_{f,f})^\omega \subseteq S_\omega(\ensuremath{\mathcal{A}}\xspace)$, let $u \in L(\ensuremath{\mathcal{A}}\xspace_{f})$, and $v_1, v_2, \dots \in L(\ensuremath{\mathcal{A}}\xspace_{f,f})$ for some $f \in F$. We show that $uv_1v_2 \dots \in S_\omega(\ensuremath{\mathcal{A}}\xspace)$.

First let $u = u_1 \dots u_n$ and $r' = r'_1 \dots r'_n$ with $r'_i = (p_{i-1}, u_i, \ensuremath{\mathbf{v}}\xspace_i \cdot c_i, p_i)$, where $c_i \in \{0,1\}$, be an accepting run of $\ensuremath{\mathcal{A}}\xspace_{f}$ on $u$.
Observe that $\rho(r') \in C \cdot \{1\}$, hence $\sum_{i \leq n} c_i = 1$, i.\,e.\xspace,~$p_n$ is the only occurrence of an accepting state in $r'$ (if there was another, say $p_j$, then $c_j = 1$ by the choice of $\Delta_f$, hence $\sum_{i \leq n} c_i > 1$, a contradiction).
For all  $1 \leq i \leq n$ let $r_i = (p_{i-1}, u_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$. Then $r_1 \dots r_n$ is a partial run of $\ensuremath{\mathcal{A}}\xspace$ on $w$ with $\rho(r_1 \dots r_n) \in C$ and $p_n = f$.

Similarly, no run of $\ensuremath{\mathcal{A}}\xspace_{f,f}$ on any $v_i$ visits an accepting state before reading the last symbol, hence we continue the run from $r_n$ on $v_1, v_2, \dots$ using the same argument. Hence $uv_1v_2 \dots \in S_\omega(\ensuremath{\mathcal{A}}\xspace)$, concluding the proof.
\end{proof}

As a side product of the proof of \Cref{thm:lpapa} we get the following corollary, which is in general not true for SPBA.
\begin{corollary}
Let $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F, C)$ be an SPBA with the property that accepting states appear only in the leaves of the condensation of $\ensuremath{\mathcal{A}}\xspace$, and there is at most one accepting state per leaf. Then we have $S_\omega(\ensuremath{\mathcal{A}}\xspace) = \bigcup_{f \in F} S_\omega(Q, \Sigma, q_0, \Delta, \{f\}, C)$.
\end{corollary}

By even further restricting the power of SPBA, we get the following characterization of $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$.

\begin{theorem}
\label{thm:lregpa}
    The following are equivalent for all $\omega$-languages $L \subseteq \Sigma^\omega$.
    \begin{enumerate}
        \item $L$ is of the form $\bigcup_i U_i V_i^\omega$, where $U_i \subseteq \Sigma^*$ is regular and $V_i \subseteq \Sigma^*$ is Parikh-recognizable.
        \item $L$ is recognized by an SPBA $\ensuremath{\mathcal{A}}\xspace$ with the following properties.
        \begin{enumerate}
            \item At most one state $q$ per leaf of the condensation of $\ensuremath{\mathcal{A}}\xspace$ may have ingoing transitions from outside the leaf, this state $q$ is the only accepting state in the leaf, and there are no accepting states in non-leaves.
            \item only transitions connecting states in a leaf may be labeled with a non-zero vector.
        \end{enumerate}
    \end{enumerate}
\end{theorem}
Observe that property (a) is a stronger property than the one of \Cref{thm:lpapa}, hence, SPBA with this restriction are at most as powerful as those that characterize $\ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace$. However, as a side product of the proof we get that property (a) is equivalent to the property of \Cref{thm:lpapa}. Hence, property (b) is mandatory to sufficiently weaken SPBA such that they capture $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$.
In fact, using the notion of IO-normalization, we can re-use most of the ideas in the proof of \Cref{thm:lpapa}.

\begin{proof}[Proof of \Cref{thm:lregpa}]

$(1) \Rightarrow (2)$. We can trivially convert an NFA into an equivalent PA by labeling every transition with $0$ and choosing $C = \{0\}$.
Let $\ensuremath{\mathcal{A}}\xspace$ be an arbitrary PA and observe that $\ensuremath{\mathcal{A}}\xspace^{IO}$ has only a single SCC by definition.
Again, we have $L(\ensuremath{\mathcal{A}}\xspace)^\omega = S_\omega(\ensuremath{\mathcal{A}}\xspace^{IO})$ and the constructions for concatenation and union do not destroy the properties, hence we obtain an SPBA of the desired form. \hfill $\lrcorner$

\medskip
$(2) \Rightarrow (1)$ Let $\ensuremath{\mathcal{A}}\xspace = (Q, \Sigma, q_0, \Delta, F, C)$ be an SPBA of dimension $d$ with properties~(a) and (b). Fix $f \in F$ and let \mbox{$\ensuremath{\mathcal{B}}\xspace_f = (Q_f, \Sigma, q_0, \{(p, a, q) \mid (p, a, \ensuremath{\mathbf{v}}\xspace, q) \in \Delta, p,q \in Q_f\}, \{f\})$} with $Q_f = \{q \in Q \mid q \text{ appears in a non-leaf SCC of } C(\ensuremath{\mathcal{A}}\xspace)\} \cup \{f\}$
be the NFA obtained from $\ensuremath{\mathcal{A}}\xspace$ by removing all leaf states except $f$, and removing all labels from the transitions.
Recycling the automaton from \Cref{thm:lpapa}, let \mbox{$\ensuremath{\mathcal{A}}\xspace_{f,f} = (Q, \Sigma, f, \Delta_{f}, \{f\}, C \cdot \{1\})$} with $\Delta_{f} = \{p,a,\ensuremath{\mathbf{v}}\xspace \cdot 0,q) \mid (p,a,\ensuremath{\mathbf{v}}\xspace, q) \in \Delta, q \neq f\} \cup \{(p, a, \ensuremath{\mathbf{v}}\xspace \cdot 1, f) \mid (p, a, \ensuremath{\mathbf{v}}\xspace, f) \in \Delta\}$.
We claim $S_\omega(\ensuremath{\mathcal{A}}\xspace) = \bigcup_{f \in F} L(\ensuremath{\mathcal{B}}\xspace_f) \cdot L(\ensuremath{\mathcal{A}}\xspace_f)^\omega$.

\smallskip
$\Rightarrow$ To show $S_\omega(\ensuremath{\mathcal{A}}\xspace) = \bigcup_{f \in F} L(\ensuremath{\mathcal{B}}\xspace_f) \cdot L(\ensuremath{\mathcal{A}}\xspace_{f,f})^\omega$, let $\alpha \in S_\omega(\ensuremath{\mathcal{A}}\xspace)$ with accepting run $r = r_1r_2r_3 \dots$ where $r_i = (p_{i-1}, \alpha_i, \ensuremath{\mathbf{v}}\xspace_i, p_i)$, and let $k_1< k_2< \dots$ be the positions of the accepting states in $r$, and consider the partial run $r_1 \dots r_{k_1}$ (if $k_1 = 0$, i.\,e.\xspace, the initial state is already accepting, then $r_1 \dots r_{k_1}$ is empty).

By property (a) we have that $p_{k_1}$ is the first state visited in $r$ that is located in a leaf of $C(\ensuremath{\mathcal{A}}\xspace)$. Hence $r'_1 \dots r'_{k_1}$, where $r'_i = (p_{i-1}, \alpha_i, p_i)$, is an accepting run of $\ensuremath{\mathcal{B}}\xspace_{p_{k_1}}$ on $\alpha[1, k_1]$ (in the case $k_1 = 0$ we define $\alpha[1, k_1] = \varepsilon$).

By the same argument as in the proof of \Cref{thm:lpapa} we have $p_{k_i} = p_{k_j}$ for all $i,j \geq 1$, hence $\alpha[k_i + 1, k_{i+1}] \in L(\ensuremath{\mathcal{A}}\xspace_{p_{k_1}, p_{k_1}})$, and hence $\alpha \in L(\ensuremath{\mathcal{B}}\xspace_{p_k}) \cdot L(\ensuremath{\mathcal{A}}\xspace_{p_{k_1}, p_{k_1}})^\omega$.

\smallskip
$\Leftarrow$ To show $\bigcup_{f \in F} L(\ensuremath{\mathcal{A}}\xspace_{f}) \cdot L(\ensuremath{\mathcal{A}}\xspace_{f,f})^\omega \subseteq S_\omega(\ensuremath{\mathcal{A}}\xspace)$, let $u \in L(\ensuremath{\mathcal{B}}\xspace_{f})$, and $v_1, v_2, \dots \in L(\ensuremath{\mathcal{A}}\xspace_{f,f})$ for some $f \in F$. We show that $uv_1v_2 \dots \in S_\omega(\ensuremath{\mathcal{A}}\xspace)$.

First observe that properties (a) and (b) enforce that $\ensuremath{\mathbf{0}}\xspace \in C$, as the accepting state of a leaf of $C(\ensuremath{\mathcal{A}}\xspace)$ is visited before a transition labeled with a non-zero can be used.
Let $u = u_1 \dots u_n$ and $s_1 \dots s_n$ with $s_i = (p_{i_1}, u_i, p_i)$ be an accepting run of $\ensuremath{\mathcal{B}}\xspace_f$ on $u$. Define $s'_i = (p_{i_1}, u_i, \ensuremath{\mathbf{0}}\xspace, p_i)$ and observe that $s'_1 \dots s'_n$ is a partial run of $\ensuremath{\mathcal{A}}\xspace$ with $\rho(s'_1 \dots s'_n) \in C$ and $p_n = f$ by the observation above.

Again we can very similarly continue the run on $v_1, v_2, \dots$ using the same argument. Hence $uv_1v_2 \dots \in S_\omega(\ensuremath{\mathcal{A}}\xspace)$, concluding the proof.
\end{proof}

\section{Conclusion}
We conclude with an overview of our results shown in \Cref{fig:overview}.
\begin{figure}
\centering
    \begin{tikzpicture}[%
      node distance=27mm,>=Latex,
      initial text="", initial where=below left,
      every state/.style={rectangle,rounded corners,draw=black,thin,fill=black!5,inner sep=1mm,minimum size=6mm},
      every edge/.style={draw=black,thin}
    ]
    \node[state] (cRPA) {complete RPA};
    \node[state,right = 1cm of cRPA] (RPA) {RPA};
    \node[state,above right = 1cm and 0cm of RPA]  (RPBA) {RPBA = LPBA = $\ensuremath{\Lmc_\mathsf{PA, Reg}^\omega}\xspace$};
    \node[state,below right = 1cm and -1cm of cRPA]  (reg) {BA = $\ensuremath{\Lmc_\mathsf{Reg, Reg}^\omega}\xspace$};
    \node[state,right = 1cm of reg] (regPA) {SPBA $(**)$ = $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$};
    \node[state,below right = 1cm and 0cm of RPBA] (PPBA) {PPBA};
    \node[state,right = 1cm of PPBA] (PAPA) {SPBA $(*)$ = $\ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace$};
    \node[state,below right = 1cm and -1.15cm of PAPA] (SPBA) {SPBA};

    \path[-{Latex}]
    (cRPA) edge node[above=3mm] {\small\Cref{remark:RPA}} (RPA)
    (RPA) edge node[below right] {\small\Cref{lem:RPARPBA}} (RPBA)
    (RPBA) edge node[above right = -1mm and -1mm] {\small\Cref{cor:LRPBAtoLPPBA}} (PPBA)
    (PPBA) edge node[above=2.5mm] {\small \cite{blindcounter, infiniteOurs}, \cite{infiniteZimmermann}} (PAPA)
    (PAPA) edge node[right] {\small\cite{infiniteOurs}} (SPBA)
    (reg) edge (regPA)
    (regPA) edge[bend right = 15] (PAPA);
    ;

    \path[dotted]
    (cRPA) edge node {$\neq$} node[left=3mm] {\small\Cref{lem:RPAregular}} (reg)
    (RPA) edge node {$\neq$} (reg)
    (RPA) edge node {$\neq$} (regPA)
    (PPBA) edge node {$\neq$} (regPA)
    ;

    \node[above=0mm of RPBA] {\small \Cref{thm:LimitEqualsReach}};
    \node[below=0mm of regPA] {\small \Cref{thm:lregpa}};
    \node[below=0mm of reg] {\small \Cref{thm:buechi}};
    \node[above=0mm of PAPA] {\small \Cref{thm:lpapa}};

    \draw[-{Latex}] (reg) -- ++(-3, 0) -- ++(0,3.2) -- (RPBA);

    \node[align=left, anchor=west] at (-1.5, -3) {\small $(*)$ At most one state $q$ per leaf of $C(\ensuremath{\mathcal{A}}\xspace)$ may have ingoing transitions from outside the  leaf, this \\\small\phantom{$(*)$} state $q$ is the only accepting state in the leaf, and there are no accepting states in non-leaves;};
    \node[align=left, anchor=west] at (-1.65, -3.66) {\small $(**)$ and only transitions connecting states in leaves may be labeled with non-zero vectors.};

    \end{tikzpicture}
    \caption{Overview of our results. Arrows mean strict inclusions and $\neq$ means orthogonal.}
    \label{fig:overview}
\end{figure}
To finalize the picture, we observe the following.
\begin{observation}
\mbox{}
\begin{enumerate}
    \item There are RPA-recognizable $\omega$-languages not contained in $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$, for example $\{a^n b^n \mid n \geq 0\} \{a\}^\omega$.
    \item We have $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace \subseteq \ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace$ by definition, and there are $\omega$-languages contained in $\ensuremath{\Lmc_\mathsf{PA, PA}^\omega}\xspace$ that are not contained in $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$, for example $\{a^n b^n \mid n \geq 1\} \{c^n d^n \mid n \geq 1\}^\omega$.
    \item We have $\ensuremath{\Lmc_\mathsf{Reg, Reg}^\omega}\xspace \subseteq \ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$ by definition, and there are $\omega$-languages contained in $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$ that are neither PPBA-recognizable nor $\omega$-regular, as witnessed by many $\omega$-closures of Parikh-recognizable languages (which are trivially contained in $\ensuremath{\Lmc_\mathsf{Reg, PA}^\omega}\xspace$), for example $\{a^n b^n \mid n \geq 1\}^\omega$ (a formal proof can be found for blind counter machines in \cite{blindcounter}, which are known to be equivalent to PPBA \cite{infiniteOurs}).
\end{enumerate}
\end{observation}

Finally, we recall that deterministic $\omega$-regular languages are characterized as regular arrow-languages $\vec{L}$, where $\vec{L} = \{\alpha \mid \alpha[1,i] \in L \text{ for infinitely many }i\}$ \cite{thomasinfinite}. This characterization can easily be adapted to show that deterministic PPBA-recognizable $\omega$-languages are captured by arrows of deterministic Parikh-recognizable languages. We conjecture that PPBA-recognizable $\omega$-languages are captured by arrows of Parikh-recognizable languages yielding a similar characterization of $\ensuremath{\Lmc_\mathsf{PPBA}}\xspace$.

\newpage
\bibliographystyle{plain}

redpajama_set_name: RedPajamaArXiv


text:
Q: Keystore Alias lost Google Developer I archived my keystore file and its password and used a software to build my apps (Monaca). Now i programmed them using React and Expo, and i have to indicate may keystore file, its password AND the same for the Keystore Alias, but i don't have it.
There's a way of talking with the support of Google Developer by email or phone?
Or anyone knows what can I do?
...remembering that I have the keystore file, but not the Alias Keystore...

A: If you have password then you can get alias from keystore file:
Goto to bin folder in command prompt C:\Program Files\Android\Android Studio\jre\bin>
Add command keytool -v -list -keystore keystorePath
C:\Program Files\Android\Android Studio\jre\bin>keytool -v -list -keystore keystorePath

redpajama_set_name: RedPajamaStackExchange


It's easy to be thankful when there's money in my wallet, food in my belly, and friends by my side. Our hearts tell a different story when terrorism is in the news, immorality is in our faces, and sickness invades our families. When the Bible tells us to be thankful in "all" circumstances—it includes both scenarios.
It's not hard to make a list of things we're not thankful for—cancer, broken relationships, anxiety, hate, and sin, to name a few—but the Bible doesn't instruct us to make that list. It instructs us to be thankful all the time.
The word that chokes me in these verses is "everything." Everything? Even in that list of things I'm not happy about? Evidently so. If Paul, who was bound in a dungeon because of his faith in Jesus could be moved by the Holy Spirit to say give thanks in all circumstances, maybe we should listen.
Could you be thankful if you were sold into slavery and then falsely imprisoned? If not, you wouldn't be thankful for how God used Joseph to reunite his family and save many from starvation.
Would you be thankful for a judge who didn't care about justice and knowingly condemned an innocent man while letting a terrorist go free? If not, you wouldn't be thankful for the way God arranged our salvation.
Scripture isn't telling us that we should be happy about pain and suffering, but instead that we trust God enough to be thankful during pain and suffering. You never know what he might be up to!
We have all sorts of names for the same phenomenon: back-seat driving, arm-chair quarterbacking, second-guesser…you get the idea. When Neil Anderson was the editor of the Gospel Advocate, he said that based on the letters, emails, and phone calls he got, he must be the only person in the world who didn't know how to run his business! All of us have this tendency to question things over which we have no control.
I wonder sometimes if we don't set our eyes on things "too great" for our finite minds. We question God more than is healthy. We forget that his ways are infinitely higher than ours (Isaiah 55:9). Paul chastised the Corinthians by asking, "Who has understood the mind of the Lord so as to instruct him?" (1 Corinthians 2:16). I imagine after that part of the letter was read, there was silence–kind of like when God showed up and started asking questions at the end of Job.
…and I didn't even know it!
Jacob isn't the only one in scripture who had this experience. Much later in Israel's history in 2 Kings 6, Elisha's servant was afraid. Israel was vastly outnumbered. The city was surrounded by an army with horses and chariots. He cried out, "What shall we do?" Elisha's answer was beautiful: "Do not be afraid, for those who are with us are more than those who are with them." Elisha prayed, and God opened the eyes of the young man so that he saw that the mountain was overflowing with horses and chariots of fire. God was present, and the servant didn't even know it.
On the morning of the resurrection, two men were walking to Emmaus from Jerusalem. They kept recounting the story of the weekend's events—the late-night trials, the arrest, and the death of the beloved rabbi. As the men walked, Jesus joined them and spoke with them about the Messiah and how he had to suffer for them to see glory. After their eyes were opened and they recognized the one with whom they walked, they said to each other, "Did not our hearts burn within us while he talked to us on the road?" (Luke 24:32) They were literally walking with Jesus, and didn't know it.
I share these three stories to say this: sometimes you feel alone. Sometimes you don't think your prayers are making it past the ceiling. Sometimes you're not sure what future you have at all. When you feel that way, let scripture remind you of this truth: God can be present right there beside you—and you didn't even know it.


Happy Vintage Cottage Dated 1930 Applique Blue Flower QUILT. A gorgeous pattern, sure to make you smile! Features a rich Cornflower blue and green flowers, and trailing border. Has an off white background.
Expertly hand quilted at 10 stitches per inch. Features 1/2 grid and feathered vines quilting. Measures 90 1/2" x 73". In very good condition with some very light age tanning/spotting, two petals with a couple tiny surface holes, and some very mild fading.
The backing has storage tanning. This one coordinates well with the blue ocean wave quilt that we are listing. A beautiful quilt from the depression era, gorgeous example of fine quilt making!
We like to do business the old fashion way. Get to know us by visiting our Me Page. We would love for you to visit! Our buyers can now sign up for our "STORE REWARDS" program!
Savings can add up quickly, so be sure to sign up! Happy Vintage Cottage Dated 1930 Applique Blue Flower QUILT" is in sale since Monday, November 19, 2018. This item is in the category "Antiques\Linens & Textiles (Pre-1930)\Quilts\Completed Quilts". The seller is "vintageblessings" and is located in Eagle, Idaho.


Honking motorists found themselves being pulled over and either ticketed or issued warnings on Wednesday when they sounded off in support of San Francisco hotel workers embroiled in a labor dispute.
San Francisco police issued $50 citations to a dozen motorists for their sympathetic honking on behalf of picketing hotel workers at the Palace Hotel on New Montgomery. Many more were warned verbally and had their license numbers recorded.
Police Capt. Denis O'Leary said that in answer to complaints about the racket, he asked the union for the workers to stop holding signs that urged motorists to "honk for health care" -- a request they agreed to. But people honked anyway.
O'Leary said he has received 20 faxed letters from businesses along New Montgomery near Market Street. "A lot of them are consultants, therapists, they need to talk to people and they can't be heard."
Meanwhile, in another effort to lower the volume, the Fire Department banned its crews from sounding air horns in solidarity with the workers.
Fire Chief Joanne Hayes-White said the department has received six complaints this week that crews used horns and sirens in front of the picketed hotels. Workers struck four hotels two weeks ago and were then locked out of 14. Hayes-White said firefighters could be subject to discipline for violating the policy.
"Obviously we have to rely on the vehicle code -- we can't take advantage of our horns and sirens," she said. "It's not appropriate, it's not professional. It's just not conducive to our mission to take a side or to do something that may be disruptive."
A hotel worker on the picket line said Wednesday that people should have the right to honk in support of the cause.
Harris Harada, a picket captain for Local 2 of the union at the Palace Hotel, said police went "a little overboard" in citing motorists.
"I understand people are trying to do their jobs in this area, but the motorists are just trying to show support to us. They are giving citations for that? I don't understand."
O'Leary said that those who simply tapped on their horns got warnings, but those who laid on the horn for 30 to 60 seconds got ticketed.
"We have been citing blatant violators of the vehicle code," O'Leary said.
"It's a two-lane street, surrounded by older buildings -- we have the same number of picketers on Third Street, Eighth Street and Market Street, but all the noise complaints are from the unit block of New Montgomery."
He said since the picketers removed the signs and the enforcement action, the honking was "somewhat diminished."
One motorist who was given a warning about using her horn was angered at what she considered a restriction on her freedom to support the workers.
"I gave two little honks on my horn, gave them a thumbs-up in support the strikers, and as soon as I did so, a cop pulled me over in the middle of the street," said local businesswoman Laurie Muschel.
The officer demanded her license and told her she was disturbing the peace. "You must be kidding," she said, but the officer explained that businesses in the area had been complaining.
"I'm just shocked -- it feels like my rights were being violated," she said. "It just seemed like a tactic to dissuade people from supporting the strikers. I was not going by laying on my horn. It was just two little short beeps."


text:
American Factfinder
A source for population, housing, economic and geographic data from Census 2000, the 1990 Decennial Census, the 1997 Economic Census, the American Community Survey, and the Population Estimates Program
Type: Statistics
URL: http://factfinder2.census.gov/faces/nav/jsf/pages/index.xhtml All Users
CKAN Datahub
The Datahub provides free access to many of CKAN's core features, letting you search for data, register published datasets, create and manage groups of datasets, and get updates from datasets and groups you're interested in. You can use the web interface or, if you are a programmer needing to connect the Datahub with another app, the CKAN API.
Type: Open Data
URL: https://datahub.io/ All Users
COMMERCE DATA HUB
This site is a first-release of the Commerce Data Hub, a platform to connect data customers with the data they need. Search over 40,000 datasets.
Type: Open Data, Statistics
URL: https://data.commerce.gov/ All Users
Federal Reserve Economic Data (FRED)
A database of 24,619 U.S. economic time series. With FRED® you can download data in Excel and text formats and view charts of data series.
URL: https://fred.stlouisfed.org/ All Users
FedStats
The gateway to statistics from over 100 U.S. Federal agencies.
URL: https://www.cs.umd.edu/hcil/govstat/fedstats/fedstats3.htm All Users
Gapminder World
Gapminder is a non-profit venture promoting sustainable global development and achievement of the United Nations Millennium Development Goals by increased use and understanding of statistics and other information about social, economic and environmental development at local, national and global levels.
URL: http://www.gapminder.org/data/ All Users
Google Public Data Explorer
The Google Public Data Explorer makes large, public-interest datasets easy to explore, visualize and communicate. As the charts and maps animate over time, the changes in the world become easier to understand. You don't have to be a data expert to navigate between different views, make your own comparisons, and share your findings.
Students, journalists, policy makers and everyone else can play with the tool to create visualizations of public data, link to them, or embed them in their own webpages. Embedded charts and links can update automatically so you're always sharing the latest available data.
URL: http://www.google.com/publicdata/directory All Users
A project of the Annie E. Casey Foundation, KIDS COUNT is the premier source for data on child and family well-being in the United States. Access hundreds of indicators, download data and create reports and graphics on the KIDS COUNT Data Center that support smart decisions about children and families.
URL: http://datacenter.kidscount.org/ All Users
The National Center for Education Statistics (NCES) is the primary federal entity for collecting and analyzing data related to education.
The Common Core of Data (CCD) is the Department of Education's primary database on public elementary and secondary education in the United States. CCD is a comprehensive, annual, national database of all public elementary and secondary schools and school districts.
URL: https://nces.ed.gov/ccd/ All Users
Odesi Data Portal
A jointly funded project between the Ontario Council of University Libraries (OCUL) and OntarioBuys provides university researchers with access to datasets in a web-based data extraction system delivered through the Scholars Portal model. The project targets Statistics Canada datasets, datafiles from Gallup Canada and other polling companies, public-domain files such as the Canadian National Election Surveys and selected files from the Inter-University Consortium for Political and Social Research (ICPSR). The files are marked-up using DDI, an international, XML-based metadata tagging system which allows data resource discovery, distributed access, extraction and analysis ... researchers working with opinion polls will be able to search across hundreds of datasets and collections to see trends and historical patterns over time"--summarized from the project page.
Data Access: McMaster Users
Country: Canada, US
URL: http://libaccess.mcmaster.ca/login?url=http://odesi2.scholarsportal.info/ McMaster Users
The Organisation for Economic Co-Operation and Development (OECD) online library of books, reports, working papers, periodicals and statistical data covering a wide range of subjects including agriculture & food, development, economics, education, employment, energy, environment, finance & investment, governance, industry & services, social issues, migration & health, taxation and transport. Search by keyword(s) or browse by theme or by country name.
URL: http://libaccess.mcmaster.ca/login?url=http://www.oecdilibrary.org McMaster Users
Passport (formerly named Passport GMID)
Passport is a global market research database providing statistics, analysis, reports, surveys and breaking news on industries, countries and consumers worldwide.
The Library subscribes to the following modules in Passport:
Countries & Consumers - Provides in-depth analysis on trends impacting consumers and countries around the world. It delivers research and analysis on the evolving economy, business environment, population, and income and expenditure patterns in 210 countries worldwide.
Industries - Includes global statistics and analysis for 27 major consumer industries worldwide. Contains historic and forecast market sizes, distribution channel analysis, company and brand share data, company profiles, global industry reports, expert and breaking news & articles and more.
Cities - Provides socioeconomic data and analysis on 850 of the world's largest cities.
Survey - Consists of online consumer survey data from 16 countries covering consumer habits, attitudes, opinions, values, behaviours and motivations on a variety of topics.
Industrials (Canada) - Breaks down the Canadian economy into 177 different industry sectors from a B2B perspective. Data and analysis is provided for Agriculture, Forestry, Mining, Alcoholic Beverages and many other industries.
URL: http://libaccess.mcmaster.ca/login?url=http://www.portal.euromonitor.com/portal/server.pt McMaster Users
Pew Research Center: Numbers, Facts and Trends Shaping Your World
Pew Research Center is a nonpartisan fact tank that informs the public about the issues, attitudes and trends shaping America and the world. We conduct public opinion polling, demographic research, media content analysis and other data-driven social science research. We do not take policy positions.
URL: http://www.pewresearch.org/ All Users
PEW Research Internet Project
This site features select infographics from past reports, presentations, and commentaries of the Pew Research Center's Internet & American Life Project.
Population Reference Bureau
The U.S. data in PRB's DataFinder are from the U.S. Census Bureau's decennial census, American Community Survey, and population estimates.
The international data in PRB's DataFinder are from several Population Reference Bureau data sheets. Additional international indicators were compiled by PRB staff, primarily using national surveys.
Sources for each indicator appear as footnotes for that indicator. More detailed sources are available from PRB.
URL: http://www.prb.org/DataFinder.aspx All Users
The SOCDS provides data for individual Metropolitan Areas, Central Cities, and Suburbs.
URL: https://www.huduser.gov/portal/datasets/socds.html All Users
Survey of Current Business Online
The monthly Survey of Current Business is BEA's (Bureau of Economic Analysis) definitive source of information about its economic accounts. Articles in the Survey present the latest national, international, regional, and industry estimates; describe the methodologies used to prepare the estimates; provide information about major revisions; discuss on-going innovations; and generally keep users up to date on relevant BEA issues and initiatives. Each issue includes numerous tables and charts of various economic estimates.
URL: http://www.bea.gov/scb/index.htm All Users
The World Factbook by CIA
The World Factbook, produced for US policymakers and coordinated throughout the US Intelligence Community, marshals facts on every country, dependency, and geographic entity in the world.
The Factbook provides information on the history, people, government, economy, energy, geography, communications, transportation, military, and transnational issues for 267 world entities.
URL: https://www.cia.gov/library/publications/resources/the-world-factbook/ All Users
Provides demographic information and analysis through on-line access to data, publications, products, and programs
URL: http://www.census.gov/ All Users
U.S. Department of Agriculture, Economic Research Service
The Economic Research Service is a primary source of economic information and research in the U.S. Department of Agriculture.
URL: http://www.ers.usda.gov/ All Users
U.S. Government's Open Data
Here you will find data, tools, and resources to conduct research, develop web and mobile applications, design data visualizations, and more.
URL: http://www.data.gov/ All Users
UNdata Explorer
The United Nations Statistics Division (UNSD) of the Department of Economic and Social Affairs (DESA) launched a new internet based data service for the global user community. It brings UN statistical databases within easy reach of users through a single entry point (http://data.un.org/). Users can now search and download a variety of statistical resources of the UN system.
Useful features like Country Profiles, Advanced Search and Glossaries are also provided to aid research. The numerous databases, tables and glossaries containing over 60 million data points cover a wide range of themes including Agriculture, Crime, Education, Employment, Energy, Environment, Health, HIV/AIDS, Human Development, Industry, Information and Communication Technology, National Accounts, Population, Refugees, Tourism, Trade, as well as the Millennium Development Goals indicators.
URL: http://data.un.org/Explorer.aspx All Users
United States Historical Census Data Browser (1790- 2015)
Access to extensive collections of numeric and geospatial data files and computing facilities and software for data manipulation, research, and instruction; and a suite of Internet-accessible data extraction tools
URL: https://www.nhgis.org/ All Users
Business/Financial (38)
(-) Census (14)
(-) Education (32)
International Trade (19)
Public Opinion (10)
All Users (30)
(-) US (33)
Microdata (7)

redpajama_set_name: RedPajamaCommonCrawl