Bandwidth of Nondeterministic Finite Automata

Da-Jung Cho, Szilárd Zsolt Fazekas, Daihei Ise, Shinnosuke Seki, Wataru Tamehira, Max Wiedenhöft · 2026

Read Bandwidth of Nondeterministic Finite Automata by Da-Jung Cho, Szilárd Zsolt Fazekas, Daihei Ise, Shinnosuke Seki, Wataru Tamehira, Max Wiedenhöft (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00663.txt.

Introduction

Cho and co-authors link two fields in this 2026 paper: RNA splicing and automata theory. As a cell copies DNA into RNA, it can cut out chunks of the copy in more than one way. Past work showed how to encode a nondeterministic finite automaton in such a template. The catch was that the cuts had to grow long when states sat far apart.

The team defines k-bandwidth automata, where each jump spans at most k states. These form a strict ladder of language classes. For finite languages, a bandwidth of 2 is always enough. Bandwidth 1 can be checked in fast, polynomial time when the language is a list of words. But finding the smallest bandwidth is NP-hard, even for fixed k of 2 or more.

Catalog record

CREATORDa-Jung Cho, Szilárd Zsolt Fazekas, Daihei Ise, Shinnosuke Seki, Wataru Tamehira, Max Wiedenhöft
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.00663

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Bandwidth of Nondeterministic Finite Automata Da-Jung Cho, Szilárd Zsolt Fazekas, Daihei Ise, Shinnosuke Seki, Wataru Tamehira, Max Wiedenhöft Abstract Co-transcriptional splicing generates RNA sequences from a DNA template by deleting subsequences nondeterministically. Recent work showed how to encode an NFA into such a template, but the construction requires deleting subsequences whose length grows with the distance between states, which makes such deletions unlikely under the local nature of co-transcriptional splicing. We introduce k k -bandwidth NFAs, in which transitions span at most k k states. These automata form a strict hierarchy of language classes. For finite languages, bandwidth 2 2 suffices, and bandwidth 1 1 can be decided in polynomial-time when the language is presented as a list of words. Minimizing the bandwidth is NP-hard even for fixed k ≥ 2 k\geq 2 . 1 Introduction Co-transcriptional splicing (Fig. 1 ) is a process in which an RNA sequence is edited by letting its subsequences fold into a hairpin and cut from its root while being sequentially synthesized from its DNA template, or transcribed [ 6 ] . Co-transcriptional folding , by which hairpins to be spliced out form therein, has been proven programmable in vitro for self-assembly of a 2-dimensional tile-like structure [ 5 ] and in papyro for universal computation [ 4 ] . The former architecture ( RNA origami ) demonstrated how to program a chain of folding of constitutional hairpins and their interactions into an RNA sequence in such a way that the sequence co-transcriptionally folds according to the event chain. With rapid progress in experiments in mind, it is not unrealistic to envision applications of co-transcriptional splicing. Figure 1: Co-transcriptional splicing. While an RNA transcript is synthesized ( transcribed ), a hairpin forms via hybridization of its complementary subsequences (colored in red and yellow) and spliced out. For instance, artificial molecular systems generate RNA sequences from DNA templates during transcription to reduce cost, since DNA is cheaper to synthesize. As of now, many templates have to be ordered as target RNA sequences, but what if multiple targets could be accommodated on a single template? Co-transcriptional splicing can be modeled as a greedy deletion of hairpins one after another from a sequence [ 2 ] . A hairpin is represented, using two sequences x,\ell and an antimorphic involution \theta , as x\ell\theta(x) , where x hybridizes with its “Watson-Crick complement” \theta(x) into a stem, leaving \ell as a loop. Using this model, we have recently demonstrated how to encode a nondeterministic finite automaton into a circular template w in such a way that all words accepted by the NFA can be co-transcriptional spliced out of w^{*} [ 3 ] . The states q_{1},q_{2},\cdots,q_{n} of a target NFA are encoded as sequences over a 4-letter alphabet and concatenated together with a special factor s_{e} for termination into the template as w=s_{1}s_{2}\cdots s_{n}s_{e} in such a way that 1. s_{i}\cdots s_{j-1} can be decomposed as h_{1}ah_{2} for a letter a and two hairpins h_{1},h_{2} as long as the NFA can transition from state q_{i} to state q_{j} by reading a ; 2. h_{1} is a prefix of s_{i} ; 3. h_{2} does not share its start point with any other hairpin. Starting at the beginning of s_{1} , one of the outgoing transitions from q_{1} , or particularly, their prefix h_{1} ’s is chosen nondeterministically and deleted, guiding the input head to the letter to be read, and then h_{2} is deleted deterministically, guiding the head to the beginning of the encoding of destination state; the transition from q_{i} to q_{j} by a is thus implemented. A drawback of this architecture is that h_{2} can be arbitrarily long. The most serious threat is self-loop. In addition, the more outgoing transitions a state q_{i} has, the longer the corresponding encoding s_{i} becomes. From a biological perspective, such long-range interactions are unlikely to occur. Co-transcriptional splicing operates in a local and greedy manner and acts on splice sites as soon as they are transcribed. This limits interactions between distant regions of the transcript and motivates restricting transitions to nearby states along the template. This leads to a linearization problem: given an NFA, can its states be arranged along the template so that every transition spans only a bounded number of segments? \vdots \mathcal{L}_{k+1} \tb^{*}(\ta\tb^{*})^{k} \mathcal{L}_{k} \vdots \mathcal{L}_{3} \tb^{*}(\ta\tb^{*})^{2} \mathcal{L}_{2} \tb^{*}\ta\tb^{*} \mathcal{L}_{1} \mathcal{F} \ta^{*} \{\ta,\tb\tb\} \{\ta\tb,\tb\tb\} Figure 2: A relationship among \mathcal{L}_{1},\mathcal{L}_{2},\ldots and \mathcal{F} , established as Proposition 1 , Lemma 1 , and Lemma 2 . The goal of this paper is to introduce the notion of k -bandwidth NFAs , whose states can be ordered in such a way that all transitions skip at most k-1 states in-between, and investigate their properties. We first show an infinite hierarchy among the class of such NFAs with respect to the bandwidth k (Fig. 2 ). The class \mathcal{F} of finite languages is of practical interest as no molecular system involves infinitely many kinds of RNA sequences. In this line, we will show how to convert an arbitrary finite language into a bandwidth- 2 NFA that accepts it (Lemma 1 ). This result turns out to be optimal in the sense that there exists a finite language that cannot be accepted by any bandwidth-1 NFA (Lemma 2 ), but we provide a polynomial-time bandwidth-1 test for finite languages (Theorem 4.1 ). Minimizing the bandwidth turns out to be NP-hard even for fixed k\geq 2 (Theorem 4.2 ). 2 Preliminaries Let \N denote the set of positive integers. For some m\in\N , denote by [m] the set \{1,2,...,m\} . With \Sigma , we denote a finite set of symbols, called an alphabet . The elements of \Sigma are called letters . A word over \Sigma is a finite sequence of letters from \Sigma . With \varepsilon , we denote the empty word . The i -th element of a word w is denoted by w[i] . The set of all words over \Sigma is denoted by \Sigma^{*} . Additionally, set \Sigma^{+}=\Sigma^{*}\setminus\{\varepsilon\} . The length of a word w\in\Sigma^{*} , i.e., the number letters in w , is denoted by |w| ; hence, |\varepsilon|=0 . For some w\in\Sigma^{*} , if we have w=xyz for some x,y,z\in\Sigma^{*} , then we say that x is a prefix , y is a factor , and z is a suffix of w . A nondeterministic finite automaton (NFA) is a tuple A=(\Sigma,Q,q_{0},\delta,F) where \Sigma is the input alphabet, Q is the finite set of states, \delta\colon Q\times\Sigma\rightarrow 2^{Q} is the multivalued transition function, q_{0}\in Q is the initial state, and F\subseteq Q is the set of final states. In the usual way, \delta is extended as a function Q\times\Sigma^{*}\rightarrow 2^{Q} and the language accepted by A is L(A)=\{w\in\Sigma^{*}\mid\delta(q_{0},w)\cap F\neq\emptyset\} . Definition 1 ( k -bandwidth NFA) Given k\in\N , an NFA A=(Q,\Sigma,\delta,q_{0},F) is k -bandwidth ( k -BW-NFA) if the states can be indexed as Q=\{q_{0},...,q_{n-1}\} such that for all q_{i},q_{j}\in Q and \ta\in\Sigma\cup\{\varepsilon\} , q_{j}\in\delta(q_{i},\ta) implies 0<(j-i)\bmod n\leq k . This definition corresponds to the notion of distance bounded NFA from [ 3 ] , where they just have been briefly considered and not formally investigated in a lot of detail. As bandwidth is an established name

Read the complete text