Complexity of road coloring with prescribed reset words

作者：

Highlights：

• We consider complexity of synchronization-related decision problem.

• We parameterize the problem by set of words, alphabet size and graph classes.

• We find the complexity classes for one word sets.

• The complexity depends on the family of the considered graph types.

• The complexity depends on the word, when alphabet and graph classes are fixed.

摘要

•We consider complexity of synchronization-related decision problem.•We parameterize the problem by set of words, alphabet size and graph classes.•We find the complexity classes for one word sets.•The complexity depends on the family of the considered graph types.•The complexity depends on the word, when alphabet and graph classes are fixed.

论文关键词：Synchronizing word,Reset word,Road Coloring Problem,Synchronizing automata,Černý conjecture

论文评审过程：Received 17 June 2015, Revised 16 April 2016, Accepted 28 May 2016, Available online 14 July 2016, Version of Record 6 June 2019.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.05.009