Opacity is a property asking whether a system may reveal its secret to a passive observer who knows the structure of the system but has only limited observations of its behavior. Several notions of opacity have been studied. Similarities among the opacity notions have been investigated via transformations, which have many potential applications. We investigate K-step opacity (K-SO), a notion that generalizes both current-state opacity and infinite-step opacity, and asks whether the intruder cannot decide, at any instant, whether or when the system was in a secret state during the last K observable steps. We provide new polynomial-time transformations among K-SO and other opacity notions. Our results lead, among others, to the general solution of an open problem concerning the computational complexity of the verification of K-SO.

Partially ordered nondeterminsitic finite automata (poNFAs) are NFAs whose transition relation induces a partial order on states, i.e., 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 R-trivial languages, and we establish the complexity of deciding if the language of an NFA is 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. Our results also prove the complexity of the inclusion and equivalence problems, since universality provides the lower bound, while the upper bound is mostly known or proved in the paper.

A regular language is k-piecewise testable if it is a finite boolean combination of languages of the form Sigma^* a_1 Sigma^* ... Sigma^* a_n Sigma^*, where a_i in Sigma and 0 <= n <= k. Given a DFA A and k >= 0, it is an NL-complete problem to decide whether the language L(A) is piecewise testable and, for k >= 4, it is coNP-complete to decide whether the language L(A) is k-piecewise testable. It is known that the depth of the minimal DFA serves as an upper bound on k. Namely, if L(A) is piecewise testable, then it is k-piecewise testable for k equal to the depth of A. In this paper, we show that some form of nondeterminism does not violate this upper bound result. Specifically, we define a class of NFAs, called ptNFAs, that recognize piecewise testable languages and show that the depth of a ptNFA provides an (up to exponentially better) upper bound on k than the minimal DFA. We provide an application of our result, discuss the relationship between k-piecewise testability and the depth of NFAs, and study the complexity of k-piecewise testability for ptNFAs.

We introduce and investigate blackhole pushdown automata, variants of pushdown automata, where a string can always be pushed to the pushdown, but only a given depth of the pushdown content is remembered (the rest of the pushdown content is either canceled or becomes inaccessible). We also study blackhole variants of regulated pushdown automata, where the automaton in some distinguished states checks the form of its pushdown content against a given control language. We present characterizations of several language families in terms of these constructs.

Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals.

We continue the investigation of pushdown automata which are allowed to make a non-deterministic decision if and only if their pushdown content forms a string belonging to a given control language. We prove that if the control language is linear and