Source author record

Mike Müller

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Data Structures and Algorithms Formal Languages and Automata Theory math.CO

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

New Bounds on Optimal Sorting Networks

We present new parallel sorting networks for $17$ to $20$ inputs. For $17, 19,$ and $20$ inputs these new networks are faster (i.e., they require less computation steps) than the previously known best networks. Therefore, we improve upon the known upper bounds for minimal depth sorting networks on $17, 19,$ and $20$ channels. Furthermore, we show that our sorting network for $17$ inputs is optimal in the sense that no sorting network using less layers exists. This solves the main open problem of [D. Bundala & J. Zavodný. Optimal sorting networks, Proc. LATA 2014].

preprint2014arXiv

Faster Sorting Networks for $17$ , $19$ and $20$ Inputs

We present new parallel sorting networks for $17$ to $20$ inputs. For $17, 19,$ and $20$ inputs these new networks are faster (i.e., they require less computation steps) than the previously known best networks. Therefore, we improve upon the known upper bounds for minimal depth sorting networks on $17, 19,$ and $20$ channels. The networks were obtained using a combination of hand-crafted first layers and a SAT encoding of sorting networks.

preprint2014arXiv

Infinite square-free self-shuffling words

In this paper we answer two recent questions from Charlier et al. and Harju about self-shuffling words. An infinite word $w$ is called self-shuffling, if $w=\prod_{i=0}^\infty U_iV_i=\prod_{i=0}^\infty U_i=\prod_{i=0}^\infty V_i$ for some finite words $U_i$ , $V_i$ . Harju recently asked whether square-free self-shuffling words exist. We answer this question affirmatively. Besides that, we build an infinite word such that no word in its shift orbit closure is self-shuffling, answering positively a question from Charlier et al.

preprint2013arXiv

Square-Free Shuffles of Words

Let $u \shuffle v$ denote the set of all shuffles of the words $u$ and $v$ . It is shown that for each integer $n \geq 3$ there exists a square-free ternary word $u$ of length $n$ such that $u\shuffle u$ contains a square-free word. This property is then shown to also hold for infinite words, i.e., there exists an infinite square-free word $u$ on three letters such that $u$ can be shuffled with itself to produce an infinite square-free word $w \in u \shuffle u$.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Mike Müller

Research overview

Is this your work?

4 publications

New Bounds on Optimal Sorting Networks

Faster Sorting Networks for $17$ , $19$ and $20$ Inputs

Infinite square-free self-shuffling words

Square-Free Shuffles of Words

See the researcher in context

Building this map preview

Mike Müller

Research overview

Is this your work?

4 publications

New Bounds on Optimal Sorting Networks

Faster Sorting Networks for 171717, 191919 and 202020 Inputs

Infinite square-free self-shuffling words

Square-Free Shuffles of Words

See the researcher in context

Building this map preview

Faster Sorting Networks for $17$ , $19$ and $20$ Inputs