Set automata (Q2814837)

The article investigates set automata, which are finite-state automata with an attached set data structure. Roughly speaking, the automaton can copy read input onto a secondary tape and then decide to either add the secondary tape content to the set, remove it from the set, or test whether the secondary tape content is already in the set. First the deterministic variant of the model is investigated in terms of its expressive power, which is compared to queue automata (with a limited number of turns) and the context-free languages. It shows that deterministic set automata achieve an expressive power that is incomparable to the deterministic queue automata with limited turns (i.e., a limited number of changes between queueing and dequeueing) and to the context-free languages. Additionally, the common closure properties are studied, and it is demonstrated that the language class computed by deterministic set automata is closed under complementation, not closed under union, not closed under intersection, but closed under intersection and union with regular languages. Similarly, the class is not closed under length-preserving homomorphisms, reversal, concatenation and Kleene star. However, it can be decided whether a deterministic set automaton accepts a regular language, from which it follows directly that the basic questions of emptiness, finiteness and universality are decidable as well for deterministic set automata. Finally, the descriptional complexity of the transformation of a deterministic set automaton (that accepts a regular language) into a deterministic finite automaton is determined to be doubly exponential with a quadratic exponent. This is confirmed by providing both an upper bound (from the transformation) and an asymptotically matching lower bound (by presenting a specific example). The final section is devoted to the similar question of transforming a nondeterministic set automaton into either a deterministic set automaton or a deterministic pushdown automaton. However, the trade-offs encountered for transformations between those models are nonrecursive in all cases. Additionally, since nondeterministic set automata can express invalid computations of a Turing machine, the basic problems of universality, equivalence, and regularity are not even semi-decidable for nondeterministic set automata.NEWLINENEWLINEThe paper is well written and should be understandable by anyone with some background in basic automata theory. Examples illustrate all notions, and the proofs are detailed enough to provide sufficient evidence for the results. No additional literature is required to appreciate all details of this article.