### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 38-54 |

Number of pages | 17 |

Journal | Indagationes Mathematicae |

Volume | 28 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1 Feb 2017 |

## Fingerprint Dive into the research topics of 'Ordering sequences by permutation transducers'. Together they form a unique fingerprint.

## Cite this

Bosma, W., & Zantema, H. (2017). Ordering sequences by permutation transducers.

*Indagationes Mathematicae*,*28*(1), 38-54. https://doi.org/10.1016/j.indag.2016.11.004