2020

  1. Transducer Degrees: Atoms, Infima and Suprema
    Jörg Endrullis, Jan Willem Klop, and Rena Bakhshi
    Acta 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

  1. 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)
    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.
    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

  1. 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)
    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.
    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

  1. 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)
    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.
    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
  2. 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)
    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

2014

  1. Eigenvalues and Transduction of Morphic Sequences
    David Sprunger, William Tune, Jörg Endrullis, and Lawrence S. Moss
    In: Proc. Conf. on Developments in Language Theory (DLT 2014), pp. 239–251, Springer (2014)
    paper

    Summary

    We study finite state transduction of automatic and morphic sequences. Dekking proved that morphic sequences are closed under transduction and in particular morphic images. We present a simple proof of this fact, and use the construction in the proof to show that non-erasing transductions preserve a condition called alpha-substitutivity. Roughly, a sequence is alpha-substitutive if the sequence can be obtained as the limit of iterating a substitution with dominant eigenvalue alpha.

    Our results culminate in the following fact: for multiplicatively independent real numbers \( \alpha \) and \( \beta \), if \( v \) is an \(\alpha\)-substitutive sequence and \( w \) is a \(\beta\)-substitutive sequence, then \( v \) and \( w \) have no common non-erasing transducts except for the ultimately periodic sequences. We rely on Cobham's theorem for substitutions, a recent result of Durand.

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

    Bibtex

    @inproceedings{streams:eigenvalues:2014,
  author = {Sprunger, David and Tune, William and Endrullis, J\"{o}rg and Moss, Lawrence S.},
  title = {{Eigenvalues and Transduction of Morphic Sequences}},
  booktitle = {Proc.\ Conf.\ on Developments in Language Theory (DLT~2014)},
  volume = {8633},
  pages = {239--251},
  publisher = {Springer},
  series = {LNCS},
  year = {2014},
  doi = {10.1007/978-3-319-09698-8\_21},
  keywords = {streams},
  type = {conference}
}

    Digital Object Identifier

    10.1007/978-3-319-09698-8_21
  2. On Periodically Iterated Morphisms
    Jörg Endrullis, and Dimitri Hendriks
    In: Joint Meeting and the Conference on Computer Science Logic (CSL) and the Symposium on Logic in Computer Science (LICS), pp. 39:1–39:10, ACM (2014)
    paper

    Bibtex

    @inproceedings{streams:periodically:iterated:morphisms:2014,
  author = {Endrullis, J\"{o}rg and Hendriks, Dimitri},
  title = {{On Periodically Iterated Morphisms}},
  booktitle = {Joint Meeting and the Conference on Computer Science Logic (CSL) and the Symposium on Logic in Computer Science (LICS)},
  pages = {39:1--39:10},
  publisher = {{ACM}},
  year = {2014},
  doi = {10.1145/2603088.2603152},
  keywords = {streams},
  type = {conference}
}

    Digital Object Identifier

    10.1145/2603088.2603152
  3. On the Complexity of Stream Equality
    Jörg Endrullis, Dimitri Hendriks, Rena Bakhshi, and Grigore Rosu
    Journal of Functional Programming , 24 (2-3) , pp. 166–217 (2014)
    paper

    Bibtex

    @article{complexity:stream:equality:2014,
  author = {Endrullis, J\"{o}rg and Hendriks, Dimitri and Bakhshi, Rena and Rosu, Grigore},
  title = {{On the Complexity of Stream Equality}},
  journal = {Journal of Functional Programming},
  volume = {24},
  number = {2-3},
  pages = {166--217},
  year = {2014},
  doi = {10.1017/S0956796813000324},
  keywords = {rewriting, undecidability, streams},
  type = {journal}
}

    Digital Object Identifier

    10.1017/S0956796813000324

2013

  1. Streams Are Forever
    Jörg Endrullis, Dimitri Hendriks, and Jan Willem Klop
    Bulletin 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}
}

    Digital Object Identifier

  2. Mix-Automatic Sequences
    Jörg Endrullis, Clemens Grabmayer, and Dimitri Hendriks
    In: Proc. Conf. on Language and Automata Theory and Applications (LATA 2013), pp. 262–274, Springer (2013)
    paper

    Bibtex

    @inproceedings{streams:mix:automatic:2013,
  author = {Endrullis, J\"{o}rg and Grabmayer, Clemens and Hendriks, Dimitri},
  title = {{Mix-Automatic Sequences}},
  booktitle = {Proc.\ Conf.\ on Language and Automata Theory and Applications (LATA~2013)},
  volume = {7810},
  pages = {262--274},
  publisher = {Springer},
  series = {LNCS},
  year = {2013},
  doi = {10.1007/978-3-642-37064-9\_24},
  keywords = {streams, automata},
  type = {conference}
}

    Digital Object Identifier

    10.1007/978-3-642-37064-9_24

2012

  1. Automatic Sequences and Zip-Specifications
    Clemens Grabmayer, Jörg Endrullis, Dimitri Hendriks, Jan Willem Klop, and Lawrence S. Moss
    In: Proc. Symp. on Logic in Computer Science (LICS 2012), pp. 335–344, IEEE Computer Society (2012)
    paper

    Bibtex

    @inproceedings{streams:zip:2012,
  author = {Grabmayer, Clemens and Endrullis, J\"{o}rg and Hendriks, Dimitri and Klop, Jan Willem and Moss, Lawrence S.},
  title = {{Automatic Sequences and Zip-Specifications}},
  booktitle = {Proc.\ Symp.\ on Logic in Computer Science (LICS~2012)},
  pages = {335--344},
  publisher = {{IEEE} Computer Society},
  year = {2012},
  doi = {10.1109/LICS.2012.44},
  keywords = {rewriting, streams, automata},
  type = {conference}
}

    Digital Object Identifier

    10.1109/LICS.2012.44
  2. On the Complexity of Equivalence of Specifications of Infinite Objects
    Jörg Endrullis, Dimitri Hendriks, and Rena Bakhshi
    In: Proc. Int. Conf. on Functional Programming (ICFP 2012), pp. 153–164, ACM (2012)
    paper

    Bibtex

    @inproceedings{complexity:stream:equality:2012,
  author = {Endrullis, J\"{o}rg and Hendriks, Dimitri and Bakhshi, Rena},
  title = {{On the Complexity of Equivalence of Specifications of Infinite Objects}},
  booktitle = {Proc.\ Int.\ Conf.\ on Functional Programming (ICFP~2012)},
  pages = {153--164},
  publisher = {{ACM}},
  year = {2012},
  doi = {10.1145/2364527.2364551},
  keywords = {rewriting, undecidability, streams},
  type = {conference}
}

    Digital Object Identifier

    10.1145/2364527.2364551

2011

  1. Degrees of Streams
    Jörg Endrullis, Dimitri Hendriks, and Jan Willem Klop
    Journal 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}
}

    Digital Object Identifier

  2. Proving Equality of Streams Automatically
    Hans Zantema, and Jörg Endrullis
    In: Proc. Conf. on Rewriting Techniques and Applications (RTA 2011), pp. 393–408, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2011)
    paper

    Bibtex

    @inproceedings{streams:equality:2011,
  author = {Zantema, Hans and Endrullis, J\"{o}rg},
  title = {{Proving Equality of Streams Automatically}},
  booktitle = {Proc.\ Conf.\ on Rewriting Techniques and Applications (RTA~2011)},
  volume = {10},
  pages = {393--408},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  series = {LIPIcs},
  year = {2011},
  doi = {10.4230/LIPIcs.RTA.2011.393},
  keywords = {rewriting, infinitary rewriting, streams},
  type = {conference}
}

    Digital Object Identifier

    10.4230/LIPIcs.RTA.2011.393