2024/07/02 by Ignacio Mollo Cunningham, Cunningham, Ignacio Mollo
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2407.02660
openalex publication_date 2024/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a class of finite state three-tape transducers which models the operation of shuffling and splitting words. We present them as automata over the so-called Shuffling Monoid. These automata can be seen as either shufflers or splitters interchangeably. We prove that functionality is decidable for splitters, and we also show that the equivalence between functional splitters is decidable. Moreover, in the deterministic case, the algorithm for equivalence is polynomial on the number of states of the splitter.