Finite automata, definable sets, and regular expressions over ωn-tapes

摘要

The theory of finite automata and regular expressions over a finite alphabet Σ is here generalized to infinite tapes X = X1 … Xk , where Xi, are themselves tapes of length ωn, for some n ⩾ 0. Closure under the usual set-theoretical operations is established, and the equivalence of deterministic and nondeterministic automata is proved. A Kleene-type characterization of the definable sets is given and finite-length generalized regular expressions are developed for finitely denoting these sets. Decision problems are treated; a characterization Of regular tapes by multiperiodic sets is specified. Characterization by equivalence relations is discussed while stressing dissimilarities with the finite case.