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 coloring

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.

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]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1412.0799
Source : ScholeXplorer IsRelatedTo DOI 10.1007/978-3-319-15579-1_12
Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.jcss.2016.05.009
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1412.0799
  • 1412.0799
  • 10.1007/978-3-319-15579-1_12
  • 10.1007/978-3-319-15579-1_12
  • 10.1016/j.jcss.2016.05.009
  • 10.1016/j.jcss.2016.05.009
  • 10.48550/arxiv.1412.0799
Complexity of Road Coloring with Prescribed Reset Words

2 Documents citing this article

Consultation statistics

This page has been seen 279 times.
This article's PDF has been downloaded 456 times.