Structure Automata
Yaacov Choueka · IEEE Transactions on Computers · 1974
By modifying the acceptability conditions in finite automata, a new and equivalent variant—the "structure automaton"— is obtained. The collection SR(Σ) of sets of tapes on Σ definable by deterministic structure-automata forms, however, a proper subset of the collection of regular sets. The structure and closure properties of SR(Σ) are analyzed in detail, using a natural topology on Σ*, in which the closed sets are the reverse ultimately definite sets. A set of tapes V is in SR(Σ) iff it is a finite union of regular "convex" sets. SR(Σ) is closed under Boolean operations, but not-closed under product, star, or transpose operations. In fact, SR(Σ) is exactly the Boolean closure of the regular closed sets. The "sigture" of a set is also defined and it is shown that a regular V is in SR(Σ) iff it has finite signature. Decision problems are also treated.