Transducer degrees: atoms, infima and suprema

Jörg Endrullis, Jan Willem Klop, Rena Bakhshi*

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

Although finite state transducers are very natural and simple devices, surprisingly little is known about the transducibility relation they induce on streams (infinite words). We collect some intriguing problems that have been unsolved since several years. The transducibility relation arising from finite state transduction induces a partial order of stream degrees, which we call Transducer degrees, analogous to the well-known Turing degrees or degrees of unsolvability. We show that there are pairs of degrees without supremum and without infimum. The former result is somewhat surprising since every finite set of degrees has a supremum if we strengthen the machine model to Turing machines, but also if we weaken it to Mealy machines.

Original languageEnglish
Pages (from-to)727-758
Number of pages32
JournalActa Informatica
Volume57
Issue number3-5
Early online date5 Dec 2019
DOIs
Publication statusPublished - 1 Oct 2020

Fingerprint Dive into the research topics of 'Transducer degrees: atoms, infima and suprema'. Together they form a unique fingerprint.

Cite this