2017-02-01
Ordering sequences by permutation transducers
Publication
Publication
Indagationes Mathematicae , Volume 28 - Issue 1 p. 38- 54
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 | |
|---|---|
| , , | |
| doi.org/10.1016/j.indag.2016.11.004 | |
| Indagationes Mathematicae | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Bosma, W., & Zantema, H. (2017). Ordering sequences by permutation transducers. Indagationes Mathematicae, 28(1), 38–54. doi:10.1016/j.indag.2016.11.004 |
|
