2023/11/25 by Ruszil, Jakub
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2311.15020
In this paper we investigate careful synchronization of one-cluster partial automata. First we prove that in general case the shortest carefully synchronizing word for such automata is of length 2^(n)/(2) + 1, where n is the number of states of an automaton. Additionally we prove that checking whether a given one-cluster partial automaton is carefully synchronizing is NP-hard even in the case of binary alphabet.