  Partially ordered nondeterminsitic finite automata (poNFAs) are NFAs whose
transition relation induces a partial order on states, that is, for which
cycles occur only in the form of self-loops on a single state. A poNFA is
universal if it accepts all words over its input alphabet. Deciding
universality is PSPACE-complete for poNFAs, and we show that this remains true
even when restricting to a fixed alphabet. This is nontrivial since standard
encodings of alphabet symbols in, e.g., binary can turn self-loops into longer
cycles. A lower coNP-complete complexity bound can be obtained if we require
that all self-loops in the poNFA are deterministic, in the sense that the
symbol read in the loop cannot occur in any other transition from that state.
We find that such restricted poNFAs (rpoNFAs) characterise the class of
$\mathcal{R}$-trivial languages, and we establish the complexity of deciding if
the language of an NFA is $\mathcal{R}$-trivial. Nevertheless, the limitation
to fixed alphabets turns out to be essential even in the restricted case:
deciding universality of rpoNFAs with unbounded alphabets is PSPACE-complete.
Based on a close relation between universality and the problems of inclusion
and equivalence, we also obtain the complexity results for these two problems.
Finaly, we show that the languages of rpoNFAs are definable by deterministic
(one-unambiguous) regular expressions, which makes them interesting in schema
languages for XML data.
