Synchronizing words and monoid factorization, yielding a new parameterized complexity class?

DOI10.1017/S0960129522000184OpenAlexW4297492870MaRDI QIDQ5048011

Jens Bruchertseifer, Henning Fernau

Publication date: 17 November 2022

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0960129522000184

zbMATH Keywords

parameterized complexitysynchronizing worddeterministic finite automaton (DFA)monoid factorization

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Parameterized complexity and approximability of the longest compatible sequence problem
• On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]]
• The complexity of finding minimum-length generator sequences
• Membership testing in commutative transformation semigroups
• An extremal problem for two families of sets
• Membership testing in threshold one transformation monoids
• On the synchronization of planar automata
• Problems on finite automata and the exponential time hypothesis
• Approximating the minimum length of synchronizing words is hard
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Polynomial complete problems in automata theory
• The Turing way to parameterized complexity
• Synchronizing words and monoid factorization: a parameterized perspective
• A multi-parameter analysis of hard problems on deterministic finite automata
• Modern aspects of complexity within formal languages
• On the space and circuit complexity of parameterized problems: classes and completeness
• Computing the shortest reset words of synchronizing automata
• Parametrized complexity theory.
• Generation problems
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• The minimum-length generator sequence problem is NP-hard
• RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
• Synchronizing series-parallel deterministic finite automata with loops and related problems
• Semicomputable points in Euclidean spaces
• An improvement to a recent upper bound for synchronizing words of finite automata
• Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
• Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata
• On the complexity of some problems on groups input as multiplication tables

This page was built for publication: Synchronizing words and monoid factorization, yielding a new parameterized complexity class?