| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428649 | Information Processing Letters | 2011 | 6 Pages |
Abstract
Research highlights► We present 3 different decision problems related to finite automata synchronization and the corresponding versions of these problems for the Road Coloring Problem. ► We prove the NP-completeness of one of this versions, namely: “given a constant out-degree graph G and a natural number m, check if G can be synchronized by some word of length m for some synchronizing labeling”. ► We also prove a much stronger result: if m in the above problem is constant, the problem remains NP-complete.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Adam Roman,