40 citations · 129 across the 35 of their papers we have counts for
5 papers · 1 filter
Degrees of Infinite Words, Polynomials, and Atoms (Extended Version)
Jörg Endrullis, Juhani Karhumäki Jan Willem Klop, Aleksi Saarela
We study 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…
Undecidability and Finite Automata
Jörg Endrullis, Jeffrey Shallit, Tim Smith
Using a novel rewriting problem, we show that several natural decision problems about finite automata are undecidable (i.e., recursively unsolvable). In contrast, we also prove thr…
The Degree of Squares is an Atom (Extended Version)
Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks +1
We answer an open question in the theory of degrees of infinite sequences with respect to transducibility by finite-state transducers. An initial study of this partial order of deg…
Eigenvalues and Transduction of Morphic Sequences: Extended Version
David Sprunger, William Tune, Jörg Endrullis +1
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 pres…
On Periodically Iterated Morphisms
Joerg Endrullis, Dimitri Hendriks
We investigate the computational power of periodically iterated morphisms, also known as D0L systems with periodic control, PD0L systems for short. These systems give rise to a cla…