Decision Version of the Road Coloring Problem Is NP-Complete

被引：0

作者：

Roman, Adam ^{[1
]}

机构：

[1] Jagiellonian Univ, Inst Comp Sci, Krakow, Poland

来源：

FUNDAMENTALS OF COMPUTATION THEORY, PROCEEDINGS | 2009年 / 5699卷

关键词：

AUTOMATA;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

After Trahtman in his brilliant paper [10] solved the Road Coloring Problem, a couple of new problems have arisen in the field of synchronizing automata. Some of them naturally extends questions related to the 'classical' version of synchronization. Particulary, it is known that the problem of finding the synchronizing word of a given length for a given automaton is NP-complete. Volkov [11] asked, what is the complexity of the following problem: given a constant out-degree digraph (possibly with multiple edges) and a natural number m, does there exist a synchronizing word of length in for some synchronizing labeling of G. In this paper we show that this decision version of the Road Coloring Problem is NP-complete.

引用

页码：287 / 297

页数：11