2020

Transducer Degrees: Atoms, Infima and Suprema
Jörg Endrullis, Jan Willem Klop, and Rena Bakhshi
Acta Informatica , 57 (3-5) , pp. 727–758 (2020)
summary paper bib doi

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 Atoms
Jörg Endrullis, Juhani Karhumäki, Jan Willem Klop, and Aleksi Saarela
International Journal of Foundations of Computer Science , 29 (5) , pp. 825–843 (2018)
summary paper bib doi
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.
We employ these techniques to obtain both positive and negative results on transducibility.

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 Atoms
Jörg Endrullis, Juhani Karhumäki, Jan Willem Klop, and Aleksi Saarela
In: Proc. Conf. on Developments in Language Theory (DLT 2016), pp. 164–176, Springer (2016)
summary paper bib doi
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.
We employ these techniques to obtain both positive and negative results on transducibility.

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 Transducibility
Jörg Endrullis, Jan Willem Klop, Aleksi Saarela, and Markus A. Whiteland
In: Proc. Conf. on Combinatorics on Words (WORDS 2015), pp. 1–13, Springer (2015)
summary paper bib doi
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.
The stream transformation realised by these machine models induces equivalence classes of streams, called 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 Atom
Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, and Hans Zantema
In: Proc. Conf. on Combinatorics on Words (WORDS 2015), pp. 109–121, Springer (2015)
summary paper bib doi

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 Forever

Jörg Endrullis, Dimitri Hendriks, and Jan Willem Klop

Bulletin of the EATCS , 109 , pp. 70–106 (2013)

paper bib

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

Digital Object Identifier

2011

Degrees of Streams

Jörg Endrullis, Dimitri Hendriks, and Jan Willem Klop

Journal of Integers , 11B (A6) , pp. 1–40 (2011)

paper bib

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

2020

Summary

Bibtex

Digital Object Identifier

2018

Summary

Bibtex

Digital Object Identifier

2016

Summary

Bibtex

Digital Object Identifier

2015

Summary

Bibtex

Digital Object Identifier

Summary

Bibtex

Digital Object Identifier

2013

Bibtex

Digital Object Identifier

2011

Bibtex

Digital Object Identifier