problem for NFA over singleton alphabets is already -hard [@MS1973], a lower bound which trivially carries over to all problems considered here[^1].

For simplicity, we identify languages $L\subseteq\{a\}^*$ with their Parikh image, so that the universality problems ask if the (bounded) language of a given OCN equals $\N$. Throughout this section, fix an OCN $\?A=\ocntuple$.

We start by sketching our approach. Observe that the language of an OCN is not universal iff the OCN does not accept some word $w$. To show that such $w$ exists, we distinguish between two cases: either $w$ is “relatively short”, in which case we use a guess-and-check approach to find it, or it is long, in which case we deduce its existence by analyzing some cyclic behaviour of the OCN. The details of both the guess-and-check elements and the cyclic behaviour depend on the encoding of the weights and the variant of universality.

Universality {#subsec: singleton universality}
------------

We start by describing a procedure to decide the ordinary universality problem for OCN over singleton alphabets – with fixed initial configuration and no bounds on the counter. Consider a cycle $\gamma=s_1,s_2,\ldots,s_k$ (with $s_1=s_k$). Recall that $\effect{\gamma}$ is the sum of weights along $\gamma$ and $\depth{\gamma}$ 