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 474 times.
This article's PDF has been downloaded 132 times.