Ordering sequences by permutation transducers

W. Bosma, H. Zantema

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
1 Downloads (Pure)


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 languageEnglish
Pages (from-to)38-54
Number of pages17
JournalIndagationes Mathematicae
Issue number1
Publication statusPublished - 1 Feb 2017


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

Cite this