VLDB 2026 Research / reviewers in the wild / expert
Jens Bruchertseifer
dblp:244/4752
· DBLP profile ↗
2ranked-venue papers
1as first author
1since 2021 · last 2022
0000-0003-3536-3082ORCID · verified
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 1 first-author · 1 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2022 | Synchronizing words and monoid factorization, yielding a new parameterized complexity class?abstractAbstract The concept of a synchronizing word is a very important notion in the theory of finite automata. We consider the associated decision problem to decide if a given DFA possesses a synchronizing word of length at most k, where k is the standard parameter. We show that this problem DFA-SW is equivalent to the problem Monoid Factorization introduced by Cai, Chen, Downey, and Fellows. Apart from the known $\textsf{W}[2]$ -hardness results, we show that these problems belong to $\textsf{A}[2]$ , $\textsf{W}[\textsf{P}],$ and $\textsf{WNL}$ . This indicates that DFA-SW is not complete for any of these classes, and hence, we suggest a new parameterized complexity class $\textsf{W}[\textsf{Sync}]$ as a proper home for these (and more) problems. We present quite a number of problems that belong to $\textsf{W}[\textsf{Sync}]$ or are hard or complete for this new class. Henning Fernau, Jens Bruchertseifer |
Math. Struct. Comput. Sci. | 2 |
| 2020 | Synchronizing Words and Monoid Factorization: A Parameterized Perspective
Jens Bruchertseifer, Henning Fernau |
TAMC | 1 |