Transducers order infinite sequences into natural classes, but permutation transducers provide a finer classification, respecting certain changes to finite segments. We investigate this hierarchy for non-periodic sequences over {0, 1} in which the groups of 0s and 1s grow according to simple functions like polynomials. In this hierarchy we find infinite strictly ascending chains of sequences, all being equivalent with respect to ordinary transducers.

Additional Metadata
Persistent URL
Conference International Conference on Developments in Language Theory
Zantema, H, & Bosma, W. (2017). Classifying non-periodic sequences by permutation transducers. In Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence (pp. 365–377). doi:10.1007/978-3-319-62809-7_28