Bandwidth of Nondeterministic Finite Automata
This work provides a new structural parameter for NFAs that models constraints in co-transcriptional splicing, with implications for automata theory and computational biology.
The paper introduces k-bandwidth NFAs, where transitions span at most k states, forming a strict hierarchy of language classes. It shows that bandwidth 2 suffices for finite languages, bandwidth 1 is polynomial-time decidable, and minimizing bandwidth is NP-hard for fixed k≥2.
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$-bandwidth NFAs, in which transitions span at most $k$ states. These automata form a strict hierarchy of language classes. For finite languages, bandwidth $2$ suffices, and bandwidth $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 \geq 2$.