Bandwidth of Nondeterministic Finite Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916070561939456 |
|---|---|
| author | Cho, Da-Jung Fazekas, Szilárd Zsolt Ise, Daihei Seki, Shinnosuke Tamehira, Wataru Wiedenhöft, Max |
| author_facet | Cho, Da-Jung Fazekas, Szilárd Zsolt Ise, Daihei Seki, Shinnosuke Tamehira, Wataru Wiedenhöft, Max |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_00663 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Bandwidth of Nondeterministic Finite Automata Cho, Da-Jung Fazekas, Szilárd Zsolt Ise, Daihei Seki, Shinnosuke Tamehira, Wataru Wiedenhöft, Max Formal Languages and Automata Theory 68Q45, 68Q07 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$. |
| title | Bandwidth of Nondeterministic Finite Automata |
| topic | Formal Languages and Automata Theory 68Q45, 68Q07 |
| url | https://arxiv.org/abs/2606.00663 |