# Publications in 2016

## 2016

- Degrees of Infinite Words, Polynomials and AtomsJörg Endrullis, Juhani Karhumäki, Jan Willem Klop, and Aleksi SaarelaIn: Proc. Conf. on Developments in Language Theory (DLT 2016), pp. 164–176, Springer (2016)
# Abstract

A finite state transducer is a finite automaton that transforms input words into output words. The transducer reads the input letter by letter, in each step producing an output word and changing its state.

While finite state transducers are very simple and elegant devices, their power in transforming infinite words is hardly understood.

In this paper we show that that

**techniques from continuous mathematics can be used to reason about finite state transducers**. To be precise, we use the following methods from linear algebra and analysis:- continuity,
- Vandermonde matrices,
- invertibility of matrices, and
- the generalised mean inequality.

The main result in this paper is the existance of an infinite number of atoms in the hierarchy of streams arising from finite state transduction.

See research for an introduction to finite state transducers, an overview of my research and many open questions.

@inproceedings{streams:degrees:polynomials:2016, author = {Endrullis, J\"{o}rg and Karhum{\"{a}}ki, Juhani and Klop, Jan Willem and Saarela, Aleksi}, title = {{Degrees of Infinite Words, Polynomials and Atoms}}, booktitle = {Proc.\ Conf.\ on Developments in Language Theory (DLT~2016)}, volume = {9840}, pages = {164--176}, publisher = {Springer}, series = {LNCS}, year = {2016}, doi = {10.1007/978-3-662-53132-7\_14}, keywords = {streams, degrees, automata}, type = {conference} }