2020/05/12 by Stefan Hoffmann, Hoffmann, Stefan
Computer Science · #68Q45 (Primary) 68Q19 (Secondary) #Computational Complexity (cs.CC) #F.1.3 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2005.05907
openalex publication_date 2020/05/12 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
In the constrained synchronization problem we ask if a given automaton admits\na synchronizing word coming from a fixed regular constraint language. We show\nthat intersecting a given constraint language with an ideal language decreases\nthe computational complexity. Additionally, we state a theorem giving\nPSPACE-hardness that broadly generalizes previously used constructions and a\nresult on how to combine languages by concatenation to get polynomial time\nsolvable constrained synchronization problems. We use these results to give a\nclassification of the complexity landscape for small constraint automata of up\nto three states.\n