2021/11/12 by Noah Kaufmann, Kaufmann, Noah
Computer Science · #semigroups and automata theory #Computability, Logic, AI Algorithms #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.2111.06505
We answer an open question in the theory of transducer degrees initially posed in [3], on the structure of polynomial transducer degrees, in particular the question of what degrees, if any, lie below the degree of n3. Transducer degrees are the equivalence classes formed by word transformations which can be realized by a finite-state transducer. While there are no general techniques to tell if a word w1 can be transformed into w2 via an FST, the work of Endrullis et al. in [2] provides a test for the class of spiralling functions, which includes all polynomials. We classify fully the degrees of all cubic polynomials which are below n3, and many of the methods can also be used to classify the degrees of polynomials of higher orders.