Jens Bruchertseifer

dblp:244/4752 · DBLP profile ↗
← Back
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
YearPublicationVenuePosition
2022 Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
abstract
Abstract 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
TAMC1