Parameterized complexity of synchronization and road coloring

MaRDI QIDQ5249241zbMATH OpenFDO

Authors Vojtěch Vorel, Adam Roman

Publication date 30 April 2015

Full work available at URL https://arxiv.org/abs/1403.4749, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2685/0.html

zbMATH Keywords

parameterized complexityreset wordroad coloring problemsynchronizing automatasynchronizing wordČerný conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• P-NP threshold for synchronizing road coloring
• A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
• Decision Version of the Road Coloring Problem Is NP-Complete

Cited in

(8)

• Černý's conjecture and the road colouring problem
• A multi-parameter analysis of hard problems on deterministic finite automata
• A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
• On the synchronizing probability function and the triple rendezvous time for synchronizing automata
• P-NP threshold for synchronizing road coloring
• A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
• Synchronizing series-parallel deterministic finite automata with loops and related problems
• The Ordered and Colored Products in Analytic Combinatorics: Application to the Quantitative Study of Synchronizations in Concurrent Processes

This page was built for publication: Parameterized complexity of synchronization and road coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5249241)