### ?

## 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.