On computational complexity of set automata

Information and Computation. 2021. Vol. 281. Article 104797.

Rubtsov A. A., Vyalyi M.

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. 

Keywords: Computational Complexity, rational cone, Formal Language, Set automaton, membership problem, emptiness problem

Publication based on the results of: Mathematical methods in studies of algorithmic complexity and formal languages (2021)