2017/02/27 by Andrew Ryzhikov, Ryzhikov, Andrew · 2 citations
Computer Science · #68Q17 #Computational Complexity (cs.CC) #F.1.1 #F.1.3 #F.2.2 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #acm:68Q17 #cs.CC #cs.FL #msc:68Q17
paper · pdf · doi:10.48550/arxiv.1702.08144
Extended and corrected version, including arXiv:1608.00889. Conference version was published at CIAA 2017, LNCS vol. 10329, pages 188-200, 2017
arxiv created 2017/12/06 · arxiv updated 2017/12/08
We study the computational complexity of various problems related to synchronization of weakly acyclic automata, a subclass of widely studied aperiodic automata. We provide upper and lower bounds on the length of a shortest word synchronizing a weakly acyclic automaton or, more generally, a subset of its states, and show that the problem of approximating this length is hard. We investigate the complexity of finding a synchronizing set of states of maximum size. We also show inapproximability of the problem of computing the rank of a subset of states in a binary weakly acyclic automaton and prove that several problems related to recognizing a synchronizing subset of states in such automata are NP-complete.