Szilárd Zsolt Fazekas

dblp:27/4709 · DBLP profile ↗
← Back
20ranked-venue papers
16as first author
14since 2021 · last 2026
0000-0001-5319-0395ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 15 · 13 first-author · 10 since 2021Artificial intelligence and machine learning · 3 · 2 first-author · 2 since 2021Applied, interdisciplinary, general and emerging computing · 2 · 1 first-author · 2 since 2021
YearPublicationVenuePosition
2026 Bandwidth of Nondeterministic Finite Automata
Da-Jung Cho, Szilárd Zsolt Fazekas, Daihei Ise, Shinnosuke Seki 0001, Wataru Tamehira, Max Wiedenhöft
CIAA2
2025 Programmable Co‑Transcriptional Splicing: Realizing Regular Languages via Hairpin Deletion
abstract
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.
Da-Jung Cho, Szilárd Zsolt Fazekas, Shinnosuke Seki 0001, Max Wiedenhöft
DNA2
2025 Subsequence Matching and Analysis Problems for Automata with Translucent Letters
Szilárd Zsolt Fazekas, Béla Klein, Tore Koss, Florin Manea, Robert Mercas, Timo Specht
CIAA1
2025 A formalization of co-transcriptional splicing as an operation on formal languages
Da-Jung Cho, Szilárd Zsolt Fazekas, Shinnosuke Seki 0001, Max Wiedenhöft
Nat. Comput.2
2024 Generalized Parikh Matrices for Tracking Subsequence Occurrences
Szilárd Zsolt Fazekas, Xinhao Huang
ICTAC1
2024 Jump Complexity of Deterministic Finite Automata with Translucent Letters
Szilárd Zsolt Fazekas, Victor Mitrana, Andrei Paun, Mihaela Paun
ICTAC1
2024 Subsequence Matching and Analysis Problems for Formal Languages
Szilárd Zsolt Fazekas, Tore Koss, Florin Manea, Robert Mercas, Timo Specht
ISAAC1
2024 Towards composable computations by RNA co-transcriptional folding: A proof-of-concept demonstration of nested loops in oritatami
Szilárd Zsolt Fazekas, Naoya Iwano, Yu Kihara, Ryuichi Matsuoka, Shinnosuke Seki 0001, Hinano Takeuchi
Theor. Comput. Sci.1
2023 Sweep Complexity Revisited
Szilárd Zsolt Fazekas, Robert Mercas
CIAA1
2022 On Algorithmic Self-Assembly of Squares by Co-Transcriptional Folding
Szilárd Zsolt Fazekas, Hwee Kim, Ryuichi Matsuoka, Shinnosuke Seki 0001, Hinano Takeuchi
ISAAC1
2022 The effect of jumping modes on various automata models
Szilárd Zsolt Fazekas, Kaito Hoshi, Akihiro Yamamura
Nat. Comput.1
2021 Clusters of Repetition Roots: Single Chains
Szilárd Zsolt Fazekas, Robert Mercas
SOFSEM1
2021 Two-way deterministic automata with jumping mode
Szilárd Zsolt Fazekas, Kaito Hoshi, Akihiro Yamamura
Theor. Comput. Sci.1
2021 Square network on a word
Szilárd Zsolt Fazekas, Shinnosuke Seki 0001
Theor. Comput. Sci.1
2019 On the Power of Oritatami Cotranscriptional Folding with Unary Bead Sequence
Szilárd Zsolt Fazekas, Kohei Maruyama, Reoto Morita, Shinnosuke Seki 0001
TAMC1
2014 The pseudopalindromic completion of regular languages
Szilárd Zsolt Fazekas, Florin Manea, Robert Mercas, Kayoko Shikishima-Tsuji
Inf. Comput.1
2013 On computational complexity of graph inference from counting
Szilárd Zsolt Fazekas, Hiro Ito, Yasushi Okuno, Shinnosuke Seki 0001, Kei Taneishi
Nat. Comput.1
2012 Hairpin Completion with Bounded Stem-Loop
Szilárd Zsolt Fazekas, Robert Mercas, Kayoko Shikishima-Tsuji
Developments in Language Theory1
2009 Powers of Regular Languages
Szilárd Zsolt Fazekas
Developments in Language Theory1
2008 Bounds on Powers in Strings
Maxime Crochemore, Szilárd Zsolt Fazekas, Costas S. Iliopoulos, Inuka Jayasekera
Developments in Language Theory2