Degrees of Infinite Words, Polynomials and Atoms

Jörg Endrullis, Juhani Karhumäki, Jan Willem Klop, Aleksi Saarela

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We study finite-state transducers and their power for transforming infinite words. Infinite sequences of symbols are of paramount importance in a wide range of fields, from formal languages to pure mathematics and physics. While finite automata for recognising and transforming languages are well-understood, very little is known about the power of automata to transform infinite words. The word transformation realised by finite-state transducers gives rise to a complexity comparison of words and thereby induces equivalence classes, called (transducer) degrees, and a partial order on these degrees. The ensuing hierarchy of degrees is analogous to the recursion-theoretic degrees of unsolvability, also known as Turing degrees, where the transformational devices are Turing machines. However, as a complexity measure, Turing machines are too strong: they trivialise the classification problem by identifying all computable words. Finite-state transducers give rise to a much more fine-grained, discriminating hierarchy. In contrast to Turing degrees, hardly anything is known about transducer degrees, in spite of their naturality. We use methods from linear algebra and analysis to show that there are infinitely many atoms in the transducer degrees, that is, minimal non-trivial degrees.

Original languageEnglish
Pages (from-to)825-843
Number of pages19
JournalInternational Journal of Foundations of Computer Science
Volume29
Issue number5
DOIs
Publication statusPublished - Aug 2018

Fingerprint

Transducers
Polynomials
Atoms
Turing machines
Equivalence classes
Linear algebra
Formal languages
Finite automata
Physics

Keywords

  • degrees of infinite words
  • finite-state transducers
  • Infinite words

Cite this

@article{96369ac00d554bfd8b9ae4221315ab94,
title = "Degrees of Infinite Words, Polynomials and Atoms",
abstract = "We study finite-state transducers and their power for transforming infinite words. Infinite sequences of symbols are of paramount importance in a wide range of fields, from formal languages to pure mathematics and physics. While finite automata for recognising and transforming languages are well-understood, very little is known about the power of automata to transform infinite words. The word transformation realised by finite-state transducers gives rise to a complexity comparison of words and thereby induces equivalence classes, called (transducer) degrees, and a partial order on these degrees. The ensuing hierarchy of degrees is analogous to the recursion-theoretic degrees of unsolvability, also known as Turing degrees, where the transformational devices are Turing machines. However, as a complexity measure, Turing machines are too strong: they trivialise the classification problem by identifying all computable words. Finite-state transducers give rise to a much more fine-grained, discriminating hierarchy. In contrast to Turing degrees, hardly anything is known about transducer degrees, in spite of their naturality. We use methods from linear algebra and analysis to show that there are infinitely many atoms in the transducer degrees, that is, minimal non-trivial degrees.",
keywords = "degrees of infinite words, finite-state transducers, Infinite words",
author = "J{\"o}rg Endrullis and Juhani Karhum{\"a}ki and Klop, {Jan Willem} and Aleksi Saarela",
year = "2018",
month = "8",
doi = "10.1142/S0129054118420066",
language = "English",
volume = "29",
pages = "825--843",
journal = "International Journal of Foundations of Computer Science",
issn = "0129-0541",
publisher = "World Scientific Publishing",
number = "5",

}

Degrees of Infinite Words, Polynomials and Atoms. / Endrullis, Jörg; Karhumäki, Juhani; Klop, Jan Willem; Saarela, Aleksi.

In: International Journal of Foundations of Computer Science, Vol. 29, No. 5, 08.2018, p. 825-843.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Degrees of Infinite Words, Polynomials and Atoms

AU - Endrullis, Jörg

AU - Karhumäki, Juhani

AU - Klop, Jan Willem

AU - Saarela, Aleksi

PY - 2018/8

Y1 - 2018/8

N2 - We study finite-state transducers and their power for transforming infinite words. Infinite sequences of symbols are of paramount importance in a wide range of fields, from formal languages to pure mathematics and physics. While finite automata for recognising and transforming languages are well-understood, very little is known about the power of automata to transform infinite words. The word transformation realised by finite-state transducers gives rise to a complexity comparison of words and thereby induces equivalence classes, called (transducer) degrees, and a partial order on these degrees. The ensuing hierarchy of degrees is analogous to the recursion-theoretic degrees of unsolvability, also known as Turing degrees, where the transformational devices are Turing machines. However, as a complexity measure, Turing machines are too strong: they trivialise the classification problem by identifying all computable words. Finite-state transducers give rise to a much more fine-grained, discriminating hierarchy. In contrast to Turing degrees, hardly anything is known about transducer degrees, in spite of their naturality. We use methods from linear algebra and analysis to show that there are infinitely many atoms in the transducer degrees, that is, minimal non-trivial degrees.

AB - We study finite-state transducers and their power for transforming infinite words. Infinite sequences of symbols are of paramount importance in a wide range of fields, from formal languages to pure mathematics and physics. While finite automata for recognising and transforming languages are well-understood, very little is known about the power of automata to transform infinite words. The word transformation realised by finite-state transducers gives rise to a complexity comparison of words and thereby induces equivalence classes, called (transducer) degrees, and a partial order on these degrees. The ensuing hierarchy of degrees is analogous to the recursion-theoretic degrees of unsolvability, also known as Turing degrees, where the transformational devices are Turing machines. However, as a complexity measure, Turing machines are too strong: they trivialise the classification problem by identifying all computable words. Finite-state transducers give rise to a much more fine-grained, discriminating hierarchy. In contrast to Turing degrees, hardly anything is known about transducer degrees, in spite of their naturality. We use methods from linear algebra and analysis to show that there are infinitely many atoms in the transducer degrees, that is, minimal non-trivial degrees.

KW - degrees of infinite words

KW - finite-state transducers

KW - Infinite words

UR - http://www.scopus.com/inward/record.url?scp=85051933899&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85051933899&partnerID=8YFLogxK

U2 - 10.1142/S0129054118420066

DO - 10.1142/S0129054118420066

M3 - Article

VL - 29

SP - 825

EP - 843

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 5

ER -