We explore a new graph parameter, KLX number, which quantifies the minimum edge congestion of depth-first search (DFS) traversals of a given graph. Originally motivated by a problem in RNA nanostructure design, this parameter is also of independent theoretical interest. Informally, the KLX number of a graph is defined as the minimum, over all its DFS traversals, of the maximum number of back edges that are simultaneously open during the traversal. We provide full characterisations and linear-time recognition algorithms for graphs with KLX numbers 0, 1 and 2. We also relate KLX to tree-width, proving that any graph satisfies TW ≤ KLX+1. Furthermore, we show that the property KLX ≤ k is MSO₂-expressible for every fixed k. Combined with the tree-width bound, this result implies that determining whether a graph has KLX number at most k can be achieved in linear time for any constant k.

RNA co-transcriptionality, where RNA is spliced or folded during transcription from DNA templates, offers promising potential for molecular programming. It enables programmable folding of nanoscale RNA structures and has recently been shown to be Turing universal. While post-transcriptional splicing is well studied, co-transcriptional splicing is gaining attention for its efficiency, though its unpredictability still remains a challenge. In this paper, we focus on engineering co-transcriptional splicing, not only as a natural phenomenon but as a programmable mechanism for generating specific RNA target sequences from DNA templates. The problem we address is whether we can encode a set of RNA sequences for a given system onto a DNA template word, ensuring that all the sequences are generated through co-transcriptional splicing. Given that finding the optimal encoding has been shown to be NP-complete under the various energy models considered [Da-Jung Cho et al., 2025], we propose a practical alternative approach under the logarithmic energy model. More specifically, we provide a construction that encodes an arbitrary nondeterministic finite automaton (NFA) into a circular DNA template from which co-transcriptional splicing produces all sequences accepted by the NFA. As all finite languages can be efficiently encoded as NFA, this framework solves the problem of finding small DNA templates for arbitrary target sets of RNA sequences. The quest to obtain the smallest possible such templates naturally leads us to consider the problem of minimizing NFAs and certain practically motivated variants of it, but as we show, those minimization problems are computationally intractable.

Different models have been proposed to understand natural phenomena at the molecular scale from a computational point of view. Oritatami systems are a model of molecular co-transcriptional folding: the transcript (the "molecule") folds as it is synthesized according to a local energy optimisation process, in a similar way to how actual biomolecules such as RNA fold into complex shapes and functions. We introduce a new model, called turedo, which is a self-avoiding Turing machine on the plane that evolves by marking visited positions and that can only move to unmarked positions. Any oritatami can be seen as a particular turedo. We show that any turedo with lookup radius 1 can conversely be simulated by an oritatami, using a universal bead type set. Our notion of simulation is strong enough to preserve the geometrical and dynamical features of these models up to a constant spatio-temporal rescaling (as in intrinsic simulation). As a consequence, turedo can be used as a readable oritatami "higher-level" programming language to build readily oritatami "smart robots", using our explicit simulation result as a compiler. As an application of our simulation result, we prove two new complexity results on the (infinite) limit configurations of oritatami systems (and radius-1 turedos), assembled from a finite seed configuration. First, we show that such limit configurations can embed any recursively enumerable set, and are thus exactly as complex as aTAM limit configurations. Second, we characterize the possible densities of occupied positions in such limit configurations: they are exactly the Π₂-computable numbers between 0 and 1. We also show that all such limit densities can be produced by one single oritatami system, just by changing the finite seed configuration. None of these results is implied by previous constructions of oritatami embedding tag systems or 1D cellular automata, which produce only computable limit configurations with constrained density.

We study the oritatami model for molecular co-transcriptional folding. In oritatami systems, the transcript (the "molecule") folds as it is synthesized (transcribed), according to a local energy optimisation process, which is similar to how actual biomolecules such as RNA fold into complex shapes and functions as they are transcribed. We prove that there is an oritatami system embedding universal computation in the folding process itself. Our result relies on the development of a generic toolbox, which is easily reusable for future work to design complex functions in oritatami systems. We develop "low-level" tools that allow to easily spread apart the encoding of different "functions" in the transcript, even if they are required to be applied at the same geometrical location in the folding. We build upon these low-level tools, a programming framework with increasing levels of abstraction, from encoding of instructions into the transcript to logical analysis. This framework is similar to the hardware-to-algorithm levels of abstractions in standard algorithm theory. These various levels of abstractions allow to separate the proof of correctness of the global behavior of our system, from the proof of correctness of its implementation. Thanks to this framework, we were able to computerise the proof of correctness of its implementation and produce certificates, in the form of a relatively small number of proof trees, compact and easily readable/checkable by human, while encapsulating huge case enumerations. We believe this particular type of certificates can be generalised to other discrete dynamical systems, where proofs involve large case enumerations as well.

RNA sequences start folding immediately as they are synthesized by RNA polymerase (cotranscriptional folding). The oritatami system (OS) is a novel mathematical model to study computational aspects of cotranscriptional folding. In this paper, we first provide a survey throughout existing research t opics and results on oritatami systems and offer research directions of significance. Simulation of an oritatami system in a different ratio (delay) of transcription speed to the speed of folding is one of them. We will introduce a simple notion of simulation, and prove that there is an OS of delay δ that cannot be simulated by any oritatami system at larger delay.

We study the difference between the standard seeded model of tile self-assembly, and the "seedless" two-handed model of tile self-assembly. Most of our results suggest that the two-handed model is more powerful. In particular, we show how to simulate any seeded system with a two-handed system that is essentially just a constant factor larger. We exhibit finite shapes with a busy-beaver separation in the number of distinct tiles required by seeded versus two-handed, and exhibit an infinite shape that can be constructed two-handed but not seeded. Finally, we show that verifying whether a given system uniquely assembles a desired supertile is co-NP-complete in the two-handed model, while it was known to be polynomially solvable in the seeded model.

Semilinear sets are one of the most important concepts in theoretical computer science, as illustrated by the fact that the set of nonnegative integer solutions to any system of Diophantine equations is semilinear. Parikh's theorem enables us to represent any semilinear set as a pushdown automaton (PDA). We summarize recent results on the descriptional complexity of conversions among different representations of a semilinear set: as a vector set (conventional), a finite automaton (FA), a PDA, etc.. We also discuss semilinearity-preserving operations like union, intersection, and complement. We use Parikh's theorem to enlarge the class of finite-state machines that can represent semilinear sets. In particular, we give a simpler proof of a known result that characterizes semilinear sets in terms of machines with reversal-bounded counters. We then investigate the power of such a machine with only one counter in the context of a long-standing conjecture about repetition on words.

We investigate the role of nondeterminism in Winfree's abstract tile assembly model, which was conceived to model artificial molecular self-assembling systems constructed from DNA. By nondeterminism we do not mean a magical ability such as that possessed by a nondeterministic algorithm to search an exponential-size space in polynomial time. Rather, we study realistically implementable systems that retain a different sense of determinism in that they are guaranteed to produce a unique shape but are nondeterministic in that they do not guarantee which tile types will be placed where within the shape. We show a “molecular computability” result: there is an infinite shape S that is uniquely assembled by a tile system but not by any deterministic tile system. We show a “molecular complexity” result: there is a finite shape S that is uniquely assembled by a tile system with c tile types, but every deterministic tile system that uniquely assembles S has more than c tile types. In fact we extend the technique to derive a stronger (classical complexity theoretic) result, showing that the problem of finding the minimum number of tile types that uniquely assemble a given finite shape is ΣP2-complete. In contrast, the problem of finding the minimum number of deterministic tile types that uniquely assemble a shape is NP-complete [5].

In this paper, we introduce the notion of k-comma codes - a proper generalization of the notion of comma-free codes. For a given positive integer k, a k-comma code is a set L over an alphabet Σ with the property that LΣ k L ∩ Σ + LΣ + = ∅. Informally, in a k-comma code, no codeword can be a subword of the catenation of two other codewords separated by a “comma” of length k. A k-comma code is indeed a code, that is, any sequence of codewords is uniquely decipherable. We extend this notion to that of k-spacer codes, with commas of length less than or equal to a given k. We obtain several basic properties of k-comma codes and their generalizations, k-comma intercodes, and some relationships between the families of k-comma intercodes and other classical families of codes, such as infix codes and bifix codes. Moreover, we introduce the notion of n-k-comma intercodes, and obtain, for each k ≥ 0, several hierarchical relationships among the families of n-k-comma intercodes, as well as a characterization of the family of 1-k-comma intercodes.

Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand w = xαy\bar{α}, and outputs w' = xαy\bar{α}\bar{x}, where \bar{x} denotes the Watson-Crick complement of x. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words α and \bar{α} that initiate hairpin completion and how they are scattered, we classify the set of all words w. For some basic classes of words w containing small numbers of occurrences of α and \bar{α}, we prove that the iterated hairpin completion of w is regular. For other classes with higher numbers of occurrences of α and \bar{α}, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.

Considering two DNA molecules which are Watson-Crick (WK) complementary to each other “equivalent” with respect to the information they encode enables us to extend the classical notions of repetition, period, and power. WK-complementarity has been modelled mathematically by an antimorphic involution θ, i.e., a function θ such that θ(xy) = θ(y)θ(x) for any x, y ∞ Σ*, and θ 2 is the identity. The WK-complementarity being thus modelled, any word which is a repetition of u and θ(u) such as uu, uθ(u)u, and uθ(u)θ(u)θ(u) can be regarded repetitive in this sense, and hence, called a θ-power of u. Taking the notion of θ-power into account, the Fine and Wilf’s theorem was extended as “given an antimorphic involution θ and words u, v, if a θ-power of u and a θ-power of v have a common prefix of length at least b(|u|, |v|) = 2|u| + |v| – gcd(|u|, |v|), then u and v are θ-powers of a same word.” In this paper, we obtain an improved bound b′(|u|, |v|) = b(|u|, |v|) – [gcd(|u|, |v|)/2]. Then we show all the cases when this bound is optimal by providing all the pairs of words (u, v) such that they are not θ-powers of a same word, but one can construct a θ-power of u and a θ-power of v whose maximal common prefix is of length equal to b′(|u|, |v|) − 1. Furthermore, we characterize such words in terms of Sturmian words.