2021/11/10 by Noah Kaufmann, Kaufmann, Noah
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic (math.LO) #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2111.05481
openalex publication_date 2021/11/10 · openalex created_date 2022/08/06 · openalex updated_date 2026/07/28
We answer an open question in the theory of transducer degrees on the existence of a diamond structure in the transducer hierarchy. Transducer degrees are the equivalence classes formed by word transformations which can be realized by a finite state transducer, which form an order based on which words can be transformed into other words. We provide a construction which proves the existence of a diamond structure, while also introducing a new function on streams which may be useful for proving more results about the transducer hierarchy.