Transducer degrees: atoms, infima and suprema (Q2182680)

The contribution investigates finite-state transducers on infinite words and utilizes their computed functions in the spirit known from reductions in the area of computability and complexity theory. More precisely, an infinite sequence \(v\) reduces to another infinite sequence \(w\) if and only if there exists a finite state transducer that transforms \(v\) into \(w\). As usual this introduces a preorder on infinite sequences with two streams equivalent if they interreduce. The equivalence classes of this equivalence relation are called transducer degrees. The preorder naturally induces a partial order on the transducer degrees and the contribution investigates the structure of this partial order in detail. The paper surveys the existing results and techniques, identifies the smallest transducer degree and the atomic degrees, which are the degrees just above the smallest degree. It also investigates whether infima and surprema exist and in which cases they exist, because in general the authors demonstrate that they do not exist. Finally, they are also interested in infinite chains of ascending and descending degrees. Actually, when restricted to computable transducer degrees it is also demonstrated that a largest degree exists. Many questions remain open and the general questions are often only solved for very special classes and instances. The paper is well written and exposes the general topic and research question succinctly. The development becomes technical rather quickly and assumes some familiarity with finite-state transducers but otherwise remains understandable to any computer-science graduate.