2021/07/30 by Stefan Hoffmann, Hoffmann, Stefan
Computer Science · #68Q45 (Primary) 68Q19 (Secondary) #Computational Complexity (cs.CC) #Distributed systems and fault tolerance #F.1.3 #F.4.3 #FOS: Computer and information sciences #FOS: Electrical engineering #Formal Languages and Automata Theory (cs.FL) #Petri Nets in System Modeling #Systems and Control (eess.SY) #electronic engineering #information engineering #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2108.00081
openalex publication_date 2021/07/30 · openalex created_date 2022/09/20 · openalex updated_date 2026/07/28
The constrained synchronization problem (CSP) asks for a synchronizing word\nof a given input automaton contained in a regular set of constraints. It could\nbe viewed as a special case of synchronization of a discrete event system under\nsupervisory control. Here, we study the computational complexity of this\nproblem for the class of sparse regular constraint languages. We give a new\ncharacterization of sparse regular sets, which equal the bounded regular sets,\nand derive a full classification of the computational complexity of CSP for\nletter-bounded regular constraint languages, which properly contain the\nstrictly bounded regular languages. Then, we introduce strongly\nself-synchronizing codes and investigate CSP for bounded languages induced by\nthese codes. With our previous result, we deduce a full classification for\nthese languages as well. In both cases, depending on the constraint language,\nour problem becomes NP-complete or polynomial time solvable.\n