8 papers
Deterministic Bandwidth of Finite Languages
Da-Jung Cho, Szilárd Zsolt Fazekas, Max Wiedenhöft
Bandwidth restricts how far transitions can move under an ordering of the states in an automaton. While every finite language admits a bandwidth-2 NFA representation, the determini…
Bandwidth of Nondeterministic Finite Automata
Da-Jung Cho, Szilárd Zsolt Fazekas, Daihei Ise +3
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,…
Binary Words Containing Few Abelian Squares
Szilard Zsolt Fazekas, Adam Mammoliti, Robert Mercas +1
Fici and Saarela ([2]) conjectured that a binary word of length n contains at least abelian squares. We slightly extend this conjecture and show that it holds…
Programmable Co-Transcriptional Splicing: Realizing Regular Languages via Hairpin Deletion
Da-Jung Cho, Szilárd Zsolt Fazekas, Shinnosuke Seki +1
RNA co-transcriptionality, where RNA is spliced or folded during transcription from DNA templates, offers promising potential for molecular programming. It enables programmable fol…
Jump Complexity of Deterministic Finite Automata with Translucent Letters
Szilárd Zsolt Fazekas, Victor Mitrana, Andrei PÄun +1
We investigate a dynamical complexity measure defined for finite automata with translucent letters (FAwtl). Roughly, this measure counts the minimal number of necessary jumps for s…
A Formalization of Co-Transcriptional Splicing as an Operation on Formal Languages
Da-Jung Cho, Szilárd Zsolt Fazekas, Shinnosuke Seki +1
RNA co-transcriptionality is the process where RNA sequences are spliced while being transcribed from DNA templates. This process holds potential as a key tool for molecular progra…