Source author record

Tristan Stérin

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

ResearcherUnclaimed source record

Discrete Mathematics Emerging Technologies Biomolecules Computational Complexity Formal Languages and Automata Theory math.CO

Catalog footprint

Research overview

4works

6topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The Collatz process embeds a base conversion algorithm

The Collatz process is defined on natural numbers by iterating the map $T(x) = T_0(x) = x/2$ when $x\in\mathbb{N}$ is even and $T(x)=T_1(x) =(3x+1)/2$ when $x$ is odd. In an effort to understand its dynamics, and since Generalised Collatz Maps are known to simulate Turing Machines [Conway, 1972], it seems natural to ask what kinds of algorithmic behaviours it embeds. We define a quasi-cellular automaton that exactly simulates the Collatz process on the square grid: on input $x\in\mathbb{N}$ , written horizontally in base 2, successive rows give the Collatz sequence of $x$ in base 2. We show that vertical columns simultaneously iterate the map in base 3. This leads to our main result: the Collatz process embeds an algorithm that converts any natural number from base 3 to base 2. We also find that the evolution of our automaton computes the parity of the number of 1s in any ternary input. It follows that predicting about half of the bits of the iterates $T^i(x)$ , for $i = O(\log x)$ , is in the complexity class NC $^1$ but outside AC $^0$ . Finally, we show that in the extension of the Collatz process to numbers with infinite binary expansions ( $2$ -adic integers) [Lagarias, 1985], our automaton encodes the cyclic Collatz conjecture as a natural reachability problem. These results show that the Collatz process is capable of some simple, but non-trivial, computation in bases 2 and 3, suggesting an algorithmic approach to thinking about existence, prediction and structure of cycles in the Collatz process.

preprint2020arXiv

Binary expression of ancestors in the Collatz graph

The Collatz graph is a directed graph with natural number nodes and where there is an edge from node $x$ to node $T(x)=T_0(x)=x/2$ if $x$ is even, or to node $T(x)=T_1(x)=\frac{3x+1}{2}$ if $x$ is odd. Studying the Collatz graph in binary reveals complex message passing behaviors based on carry propagation which seem to capture the essential dynamics and complexity of the Collatz process. We study the set $\mathcal{E} \text{Pred}_k(x)$ that contains the binary expression of any ancestor $y$ that reaches $x$ with a limited budget of $k$ applications of $T_1$ . The set $\mathcal{E} \text{Pred}_k(x)$ is known to be regular, Shallit and Wilson [EATCS 1992]. In this paper, we find that the geometry of the Collatz graph naturally leads to the construction of a regular expression, $\texttt{reg}_k(x)$ , which defines $\mathcal{E} \text{Pred}_k(x)$ . Our construction, is exponential in $k$ which improves upon the doubly exponentially construction of Shallit and Wilson. Furthermore, our result generalises Colussi's work on the $x = 1$ case [TCS 2011] to any natural number $x$ , and gives mathematical and algorithmic tools for further exploration of the Collatz graph in binary.

preprint2020arXiv

Limitations on counting in Boolean circuits and self-assembly

In self-assembly, a $k$ -counter is a tile set that grows a horizontal ruler from left to right, containing $k$ columns each of which encodes a distinct binary string. Counters have been fundamental objects of study in a wide range of theoretical models of tile assembly, molecular robotics and thermodynamics-based self-assembly due to their construction capabilities using few tile types, time-efficiency of growth and combinatorial structure. Here, we define a Boolean circuit model, called $n$ -wire local railway circuits, where $n$ parallel wires are straddled by Boolean gates, each with matching fanin/fanout strictly less than $n$ , and we show that such a model can not count to $2^n$ nor implement any so-called odd bijective nor quasi-bijective function. We then define a class of self-assembly systems that includes theoretically interesting and experimentally-implemented systems that compute $n$ -bit functions and count layer-by-layer. We apply our Boolean circuit result to show that those self-assembly systems can not count to $2^n$ . This explains why the experimentally implemented iterated Boolean circuit model of tile assembly can not count to $2^n$ , yet some previously studied tile system do. Our work points the way to understanding the kinds of features required from self-assembly and Boolean circuits to implement maximal counters.

preprint2020arXiv

scadnano: A browser-based, scriptable tool for designing DNA nanostructures

We introduce $\textit{scadnano}$ (https://scadnano.org) (short for "scriptable cadnano"), a computational tool for designing synthetic DNA structures. Its design is based heavily on cadnano, the most widely-used software for designing DNA origami, with three main differences: 1. scadnano runs entirely in the browser, with $\textit{no software installation}$ required. 2. scadnano designs, while they can be edited manually, can also be created and edited by a $\textit{well-documented Python scripting library}$ , to help automate tedious tasks. 3. The scadnano file format is $\textit{easily human-readable}$ . This goal is closely aligned with the scripting library, intended to be helpful when debugging scripts or interfacing with other software. The format is also somewhat more expressive than that of cadnano, able to describe a broader range of DNA structures than just DNA origami.

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.

Tristan Stérin

Research overview

Is this your work?

4 publications

The Collatz process embeds a base conversion algorithm

Binary expression of ancestors in the Collatz graph

Limitations on counting in Boolean circuits and self-assembly

scadnano: A browser-based, scriptable tool for designing DNA nanostructures

See the researcher in context

Building this map preview