Vorel, Vojtěch and Roman, Adam - Parameterized complexity of synchronization and road coloring

dmtcs:2103 - Discrete Mathematics & Theoretical Computer Science, April 22, 2015, Vol. 17 no. 1
Parameterized complexity of synchronization and road coloring

Authors: Vorel, Vojtěch and Roman, Adam

First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unless the polynomial hierarchy collapses. Second, we consider a related canonical problem concerning synchronizing road colorings (SRCP). Here we give a similar complete multi-parameter analysis. Namely, we show that the problem, parameterized by the number of states, admits a polynomial kernel and we close the previous research of restrictions to particular values of both the alphabet size and the maximum length of a reset word.


Source : oai:HAL:hal-01196846v1
Volume: Vol. 17 no. 1
Section: Automata, Logic and Semantics
Published on: April 22, 2015
Submitted on: July 9, 2014
Keywords: synchronizing word,reset word,Road Coloring Problem,synchronizing automata,parameterized complexity,Cerny conjecture,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 21 times.
This article's PDF has been downloaded 65 times.