Abstract :
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.
Keywords :
Closed regular sets, convex languages, definite and ultimately definite sets, finite automata, languages with finite signatures, minimal regular sets, open regular sets, structure automata.; Automata; Mathematics; Topology; Closed regular sets, convex languages, definite and ultimately definite sets, finite automata, languages with finite signatures, minimal regular sets, open regular sets, structure automata.;
