TY - GEN

T1 - Degrees of infinite words, polynomials and atoms

AU - Endrullis, Jörg

AU - Karhumäki, Juhani

AU - Klop, Jan Willem

AU - Saarela, Aleksi

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

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

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

U2 - 10.1007/978-3-662-53132-7_14

DO - 10.1007/978-3-662-53132-7_14

M3 - Conference contribution

AN - SCOPUS:84979210545

SN - 9783662531310

VL - 9840

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 164

EP - 176

BT - Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings

PB - Springer/Verlag

T2 - 20th International Conference on Developments in Language Theory, DLT 2016

Y2 - 25 July 2016 through 28 July 2016

ER -