To extend a natural concept of equivalence of sequences to two-sided infinite sequences, the notion of permutation transducer is introduced. Requiring the underlying automaton to be deterministic in two directions, it provides the means to rewrite bi-infinite sequences. The first steps in studying the ensuing hierarchy of equivalence classes of bi-infinite sequences are taken, by describing the classes of ultimately periodic two-sided infinite sequences. It is important to make a distinction between unpointed and pointed sequences, that is, whether or not sequences are considered equivalent up to shifts. While one-sided ultimately periodic sequences form a single equivalence class under ordinary transductions, which is shown to split into two under permutation transductions, in the two-sided case there are three unpointed and seven pointed equivalence classes under permutation transduction.

Additional Metadata
Keywords Automaton, Sequence, Transducer
Persistent URL dx.doi.org/10.1016/j.indag.2016.11.004
Journal Indagationes Mathematicae
Citation
Bosma, W, & Zantema, H. (2017). Ordering sequences by permutation transducers. Indagationes Mathematicae, 28(1), 38–54. doi:10.1016/j.indag.2016.11.004