Classifying non-periodic sequences by permutation transducers

H. Zantema, W. Bosma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)


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.
Original languageEnglish
Title of host publicationDevelopments in Langauge Theory"21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings
EditorsEmilie Charlier, Julien Leroy, Michel Rigo
Place of PublicationCham
Number of pages13
ISBN (Electronic)978-3-319-62809-7
ISBN (Print)978-3-319-62808-0
Publication statusPublished - 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10396 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Classifying non-periodic sequences by permutation transducers'. Together they form a unique fingerprint.

Cite this