A3 Refereed book chapter or chapter in a compilation book
Degrees of Transducibility
Authors: Endrullis J, Klop JW, Saarela A, Whiteland M
Editors: Manea, F, Nowotka, D.
Publisher: SPRINGER-VERLAG NEW YORK, MS INGRID CUNNINGHAM, 175 FIFTH AVE, NEW YORK, NY 10010 USA
Publishing place: Heidelberg New York Dordrecht London
Publication year: 2015
Journal: Lecture Notes in Computer Science
Book title : Combinatorics on Words
Journal name in source: COMBINATORICS ON WORDS, WORDS 2015
Journal acronym: LECT NOTES COMPUT SC
Series title: Lecture Notes in Computer Science
Volume: 9304
First page : 1
Last page: 13
Number of pages: 13
ISBN: 978-3-319-23659-9
ISSN: 0302-9743
DOI: https://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.
