Degrees of Transducibility




Endrullis J, Klop JW, Saarela A, Whiteland M

Manea, F, Nowotka, D.

PublisherSPRINGER-VERLAG NEW YORK, MS INGRID CUNNINGHAM, 175 FIFTH AVE, NEW YORK, NY 10010 USA

Heidelberg New York Dordrecht London

2015

Lecture Notes in Computer Science

Combinatorics on Words

COMBINATORICS ON WORDS, WORDS 2015

LECT NOTES COMPUT SC

Lecture Notes in Computer Science

9304

1

13

13

978-3-319-23659-9

0302-9743

DOIhttps://doi.org/10.1007/978-3-319-23660-5



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.




Last updated on 2024-26-11 at 19:13