On computational complexity of set automata
We consider a computational model which is known as set automata. The set automata are one-way finite automata with additional storage-the set. There are two kinds of set automata-deterministic (DSA's) and nondeterministic (NSA's). The model was introduced by Kutrib, Malcher, Wendlandt in 2014. It was shown that DSA-recognizable languages look similar to DCFL's and NSA-recognizable languages look similar to CFL's.
In this paper, we extend this similarity and prove that languages recognizable by NSA's form a rational cone, as do CFL's.
The main topic of this paper is computational complexity: we prove that
languages recognizable by DSA's belong to P and there are P-complete languages among them;
languages recognizable by NSA's are in NP and there are NP-complete languages among them;
the word membership problem is P-complete for DSA's without epsilon-loops and PSPACE-complete for general DSA's;
the emptiness problem is PSPACE-complete for DSA's.