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

dmtcs:2103 - Discrete Mathematics & Theoretical Computer Science, April 22, 2015, Vol. 17 no. 1 - https://doi.org/10.46298/dmtcs.2103
Parameterized complexity of synchronization and road coloringArticle

Authors: Vojtěch Vorel 1; Adam Roman 2

  • 1 Faculty of Mathematics and Physics [Praha/Prague]
  • 2 Institute of Computer Science [Krakow]

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.

https://doi.org/10.46298/dmtcs.2103
Source: 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]

Publications

Has review
  • 1 zbMATH Open

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 462 times.
This article's PDF has been downloaded 618 times.