Degrees of finite-state transformability

The upper semilattice of degrees of transformability by finite-state automata is defined analogously to the upper semilattice of degrees of recursive unsolvability (which arises from transformability by Turing machines). Two infinite sequences from a finite alphabet are considered equivalent if each can be transformed into the other by a finite-state automaton, perhaps after finite initial segments (not necessarily of the same length) are deleted from each. We require the output sequence to be generated at the same rate as the input, with exactly one output character for each input character. If such a transformation is possible in only one direction, an order relation holds between the equivalence classes.We show that this partially ordered set does indeed form an upper semilattice, exhibit the (unique) minimal class, and prove there is no maximal class. In the course of the proof of the last assertion, the notion of a complete sequence, a sequence in which every block of the alphabet occurs, is introduced and shown to be significant. The richness of the partial ordering is shown by two contrasting examples: We exhibit one section of it in which the partial ordering is dense, and, on the other hand, we exhibit two classes [x] > [z] having no class properly between them