A4 Article in conference proceedings

Degrees of infinite words, polynomials and atoms

List of Authors: Jörg Endrullis, Juhani Karhumäki, Jan Willem Klop, Aleksi Saarela

Conference name: International Conference on Developments in Language Theory

Publication year: 2016

Book title *: Developments in Language Theory: 20th International Conference, DLT 2016, Montréal, Canada, July 25-28, 2016, Proceedings

Title of series: Lecture Notes in Computer Science

Number in series: 9840

Volume number: 9840

Number of pages: 13

ISBN: 978-3-662-53131-0

eISBN: 978-3-662-53132-7

ISSN: 0302-9743

DOI: http://dx.doi.org/10.1007/978-3-662-53132-7_14

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.

Downloadable publication This is an electronic reprint of the original article. |