Noah Kaufmann - A Diamond Structure in the Transducer Hierarchy

dmtcs:8704 - Discrete Mathematics & Theoretical Computer Science, December 15, 2025, vol. 27:3 - https://doi.org/10.46298/dmtcs.8704
A Diamond Structure in the Transducer HierarchyArticle

Authors: Noah Kaufmann

    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.


    Volume: vol. 27:3
    Section: Automata, Logic and Semantics
    Published on: December 15, 2025
    Accepted on: October 26, 2025
    Submitted on: November 13, 2021
    Keywords: Formal Languages and Automata Theory, Logic

    Consultation statistics

    This page has been seen 5 times.
    This article's PDF has been downloaded 5 times.