Downloads provided by UsageCounts
arXiv: 1403.4749
Automata, Logic and Semantics 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.
road coloring problem, FOS: Computer and information sciences, Formal Languages and Automata Theory (cs.FL), Road Coloring Problem, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], F.1.1; F.2.2, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], synchronizing automata, synchronizing word, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], cerny conjecture, Cerny conjecture, QA1-939, reset word, Formal Languages and Automata Theory, Mathematics, parameterized complexity
road coloring problem, FOS: Computer and information sciences, Formal Languages and Automata Theory (cs.FL), Road Coloring Problem, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], F.1.1; F.2.2, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], synchronizing automata, synchronizing word, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], cerny conjecture, Cerny conjecture, QA1-939, reset word, Formal Languages and Automata Theory, Mathematics, parameterized complexity
| citations The total number of citations received by all articles of the researcher of interest. | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
| views | 169 | |
| downloads | 149 |

Views provided by UsageCounts
Downloads provided by UsageCounts