of “pumpable” paths, akin to the so-called linear-path schemes [@LS2004; @BFGHM15]. We show that the complexity of some of the problems is $\coNP$ complete, where others range between $\coNP$ and $\SigmaTwo$ (see \[tbl:Unary,tbl:Binary\]). We then consider deterministic, and unambiguous OCNs (\[sec:deterministic,sec:unambiguous\], respectively). For such systems, deciding (bounded) universality problems mostly reduces to checking simple conditions on the cyclic structure of the control automaton underlying the OCN. Based on known (but in some cases very recent) results on unambiguous finite automata and vector-addition systems, we derive relatively low complexity upper bounds, in polynomial time (assuming unary encoding) and space (assuming binary encoding). summarize the status quo, following our results.

##### Related work. {#related-work. .unnumbered}

The undecidability of language universality for pushdown automata is textbook. In his 1973 PhD thesis [@Val1973], Valiant showed that the problem remains undecidable for the strictly weaker model of one-counter automata (OCA, with zero tests) by recognizing the complement of all accepting runs of a two-counter machine. Language inclusion is undecidable for the further restricted model of OCNs [@HLMT2016]. If one considers $\omega$-regular languages defined by OCNs with Büchi acceptance condition then the resulting universality problem is undecidable [@BGHH2017].

On the positive side, universality is decidable for 