TY - GEN

T1 - Degrees of transducibility

AU - Endrullis, Jörg

AU - Klop, Jan Willem

AU - Saarela, Aleksi

AU - Whiteland, Markus

PY - 2015

Y1 - 2015

N2 - Our objects of study are infinite sequences and how they can be transformed into each other. As transformational devices, we focus here on Turing Machines, sequential finite state transducers and Mealy Machines. For each of these choices, the resulting transducibility relation ≥ is a preorder on the set of infinite sequences. This preorder induces equivalence classes, called degrees, and a partial order on the degrees. For Turing Machines, this structure of degrees is well-studied and known as degrees of unsolvability. However, in this hierarchy, all the computable streams are identified in the bottom degree. It is therefore interesting to study transducibility with respect to weaker computational models, giving rise to more fine-grained structures of degrees. In contrast with the degrees of unsolvability, very little is known about the structure of degrees obtained from finite state transducers or Mealy Machines.

AB - Our objects of study are infinite sequences and how they can be transformed into each other. As transformational devices, we focus here on Turing Machines, sequential finite state transducers and Mealy Machines. For each of these choices, the resulting transducibility relation ≥ is a preorder on the set of infinite sequences. This preorder induces equivalence classes, called degrees, and a partial order on the degrees. For Turing Machines, this structure of degrees is well-studied and known as degrees of unsolvability. However, in this hierarchy, all the computable streams are identified in the bottom degree. It is therefore interesting to study transducibility with respect to weaker computational models, giving rise to more fine-grained structures of degrees. In contrast with the degrees of unsolvability, very little is known about the structure of degrees obtained from finite state transducers or Mealy Machines.

UR - http://www.scopus.com/inward/record.url?scp=84945970478&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945970478&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-23660-5_1

DO - 10.1007/978-3-319-23660-5_1

M3 - Conference contribution

AN - SCOPUS:84945970478

SN - 9783319236599

VL - 9304

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 13

BT - Combinatorics on Words - 10th International Conference, WORDS 2015, Proceedings

PB - Springer/Verlag

T2 - 10th International Conference on Words, WORDS 2015

Y2 - 14 September 2015 through 17 September 2015

ER -