Degrees of transducibility

Jörg Endrullis, Jan Willem Klop, Aleksi Saarela, Markus Whiteland

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationCombinatorics on Words - 10th International Conference, WORDS 2015, Proceedings
PublisherSpringer/Verlag
Pages1-13
Number of pages13
Volume9304
ISBN (Print)9783319236599
DOIs
Publication statusPublished - 2015
Event10th International Conference on Words, WORDS 2015 - Kiel, Germany
Duration: 14 Sep 201517 Sep 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9304
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference10th International Conference on Words, WORDS 2015
CountryGermany
CityKiel
Period14/09/1517/09/15

Fingerprint

Dive into the research topics of 'Degrees of transducibility'. Together they form a unique fingerprint.

Cite this