On Emptiness and Membership Problems for Set Automata
We consider a computational model which is known as set automata.
The set automata are one-way finite automata with an additional storage—the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by Kutrib et al. in 2014 in [2, 3].
In this paper we characterize algorithmic complexity of the emptiness and membership problems for set automata. More definitely, we prove that both problems are PSPACEPSPACE-complete for both kinds of set automata.
The study has been funded by the Russian Academic Excellence Project ‘5-100’. Supported in part by RFBR grants 16–01–00362 and 17–51-10005.