A3 Vertaisarvioitu kirjan tai muun kokoomateoksen osa
Degrees of Transducibility
Tekijät: Endrullis J, Klop JW, Saarela A, Whiteland M
Toimittaja: Manea, F, Nowotka, D.
Kustantaja: SPRINGER-VERLAG NEW YORK, MS INGRID CUNNINGHAM, 175 FIFTH AVE, NEW YORK, NY 10010 USA
Kustannuspaikka: Heidelberg New York Dordrecht London
Julkaisuvuosi: 2015
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Combinatorics on Words
Tietokannassa oleva lehden nimi: COMBINATORICS ON WORDS, WORDS 2015
Lehden akronyymi: LECT NOTES COMPUT SC
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 9304
Aloitussivu: 1
Lopetussivu: 13
Sivujen määrä: 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.
