Degrees of infinite words, polynomials and atoms

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

*Corresponding author for this work

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

Abstract

Our objects of study are 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. We use methods from linear algebra and analysis to show that there is an infinite number of atoms in the transducer degrees, that is, minimal non-trivial degrees.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 20th International Conference, DLT 2016, Proceedings
PublisherSpringer/Verlag
Pages164-176
Number of pages13
Volume9840
ISBN (Print)9783662531310
DOIs
Publication statusPublished - 2016
Event20th International Conference on Developments in Language Theory, DLT 2016 - Montreal, Canada
Duration: 25 Jul 201628 Jul 2016

Publication series

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

Conference

Conference20th International Conference on Developments in Language Theory, DLT 2016
Country/TerritoryCanada
CityMontreal
Period25/07/1628/07/16

Fingerprint

Dive into the research topics of 'Degrees of infinite words, polynomials and atoms'. Together they form a unique fingerprint.

Cite this