# Publications on Degrees

## 2020

- Transducer Degrees: Atoms, Infima and SupremaJörg Endrullis, Jan Willem Klop, and Rena BakhshiActa Informatica , 57 (3-5) , pp. 727–758 (2020)paper
# Summary

Although finite state transducers are very natural and simple devices, surprisingly little is known about the transducibility relation they induce on streams (infinite words). We collect some intriguing problems that have been unsolved since several years. The transducibility relation arising from finite state transduction induces a partial order of stream degrees, which we call Transducer degrees, analogous to the well-known Turing degrees or degrees of unsolvability.

We show that there are pairs of degrees without supremum and without infimum. The former result is somewhat surprising since every finite set of degrees has a supremum if we strengthen the machine model to Turing machines, but also if we weaken it to Mealy machines.

# Bibtex

@article{streams:degrees:suprema:2020, author = {Endrullis, J{\"{o}}rg and Klop, Jan Willem and Bakhshi, Rena}, title = {{Transducer Degrees: Atoms, Infima and Suprema}}, journal = {Acta Informatica}, volume = {57}, number = {3-5}, pages = {727--758}, year = {2020}, doi = {10.1007/s00236-019-00353-7}, keywords = {streams, degrees, automata}, type = {journal} }

# Digital Object Identifier

10.1007/s00236-019-00353-7

## 2018

- Degrees of Infinite Words, Polynomials and AtomsJörg Endrullis, Juhani Karhumäki, Jan Willem Klop, and Aleksi SaarelaInternational Journal of Foundations of Computer Science , 29 (5) , pp. 825–843 (2018)paper
# Summary

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

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

This paper is an extended version of

*Degrees of Infinite Words, Polynomials and Atoms*presented at the Conference on Developments in Language Theory (DLT), 2016.See research for an introduction to finite state transducers, an overview of my research and many open questions.

# Bibtex

@article{streams:degrees:polynomials:2018, 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}}, journal = {International Journal of Foundations of Computer Science}, volume = {29}, number = {5}, pages = {825--843}, year = {2018}, doi = {10.1142/S0129054118420066}, keywords = {streams, degrees, automata}, type = {journal} }

# Digital Object Identifier

10.1142/S0129054118420066

## 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)paper
# Summary

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

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

We have published an extended journal version of this paper in the

*International Journal of Foundations of Computer Science*, 2018.See research for an introduction to finite state transducers, an overview of my research and many open questions.

# Bibtex

@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} }

# Digital Object Identifier

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

## 2015

- Degrees of TransducibilityJörg Endrullis, Jan Willem Klop, Aleksi Saarela, and Markus A. WhitelandIn: Proc. Conf. on Combinatorics on Words (WORDS 2015), pp. 1–13, Springer (2015)paper
# Summary

In this survey paper we compare different hierarchies of degrees of infinite words (streams) arising from transformation (transduction) of these words. As transformational devices we consider

- Turing machines,
- finite state transducers, and
- Mealy machines.

**degrees**, and a partial order on these degrees. We refer to these hierarchies as**Turing degrees, Transducer degrees and Mealy degrees**, respectively.While Turing degrees have been extensively studied in the 60th and 70th, hardly anything is known about Transducer and Mealy degrees. In this paper, we compare central properties of these hierarchies and mention many open problems.

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

# Bibtex

@inproceedings{streams:degrees:transducibility:2015, author = {Endrullis, J\"{o}rg and Klop, Jan Willem and Saarela, Aleksi and Whiteland, Markus A.}, title = {{Degrees of Transducibility}}, booktitle = {Proc.\ Conf.\ on Combinatorics on Words (WORDS~2015)}, volume = {9304}, pages = {1--13}, publisher = {Springer}, series = {LNCS}, year = {2015}, doi = {10.1007/978-3-319-23660-5\_1}, keywords = {streams, degrees, automata}, type = {conference} }

# Digital Object Identifier

10.1007/978-3-319-23660-5_1

- The Degree of Squares Is an AtomJörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, and Hans ZantemaIn: Proc. Conf. on Combinatorics on Words (WORDS 2015), pp. 109–121, Springer (2015)paper
# Summary

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 the degree of the stream \[ \prod_{i = 0}^\infty 1\, 0^{i^2} = 1 \, 0^0 \, 1 \, 0^1 \, 1 \, 0^4 \, 1 \, 0^9 \, 1 \, 0^{16} \, \cdots = 1101000010000000001 \cdots \] is an atom in the hierarchy of streams arising from finite state transduction.

In the paper Degrees of Infinite Words, Polynomials and Atoms we vastly generalise this result by showing that there is precisely one atom for each polynomial degree. See research for an introduction to finite state transducers, an overview of my research and many open questions.

# Bibtex

@inproceedings{streams:degrees:squares:2015, author = {Endrullis, J\"{o}rg and Grabmayer, Clemens and Hendriks, Dimitri and Zantema, Hans}, title = {{The Degree of Squares is an Atom}}, booktitle = {Proc.\ Conf.\ on Combinatorics on Words (WORDS~2015)}, volume = {9304}, pages = {109--121}, publisher = {Springer}, series = {LNCS}, year = {2015}, doi = {10.1007/978-3-319-23660-5\_10}, keywords = {streams, degrees, automata}, type = {conference} }

# Digital Object Identifier

10.1007/978-3-319-23660-5_10

## 2013

- Streams Are ForeverJörg Endrullis, Dimitri Hendriks, and Jan Willem KlopBulletin of the EATCS , 109 , pp. 70–106 (2013)paper
# Bibtex

@article{streams:forever:2013, author = {Endrullis, J\"{o}rg and Hendriks, Dimitri and Klop, Jan Willem}, title = {{Streams are Forever}}, journal = {Bulletin of the {EATCS}}, volume = {109}, pages = {70--106}, year = {2013}, keywords = {streams, degrees, automata}, type = {journal} }

## 2011

- Degrees of StreamsJörg Endrullis, Dimitri Hendriks, and Jan Willem KlopJournal of Integers , 11B (A6) , pp. 1–40 (2011)paper
# Bibtex

@article{streams:degrees:2011, author = {Endrullis, J\"{o}rg and Hendriks, Dimitri and Klop, Jan Willem}, title = {{Degrees of Streams}}, journal = {Journal of Integers}, volume = {11B}, number = {A6}, pages = {1--40}, year = {2011}, note = {Proceedings of the Leiden Numeration Conference 2010}, keywords = {streams, degrees, automata}, type = {journal} }