2021/08/16 by Stefan Hoffmann, Hoffmann, Stefan · 1 citation
Computer Science · #semigroups and automata theory #Formal Methods in Verification #Petri Nets in System Modeling
paper · pdf · doi:10.48550/arxiv.2108.06984
We investigate the constrained synchronization problem for weakly acyclic, or\npartially ordered, input automata. We show that, for input automata of this\ntype, the problem is always in NP. Furthermore, we give a full classification\nof the realizable complexities for constraint automata with at most two states\nand over a ternary alphabet. We find that most constrained problems that are\nPSPACE-complete in general become NP-complete. However, there also exist\nconstrained problems that are PSPACE-complete in the general setting but become\npolynomial time solvable when considered for weakly acyclic input automata. We\nalso investigate two problems related to subset synchronization, namely if\nthere exists a word mapping all states into a given target subset of states,\nand if there exists a word mapping one subset into another. Both problems are\nPSPACE-complete in general, but in our setting the former is polynomial time\nsolvable and the latter is NP-complete.\n