Completing Partial DFAs to Synchronizing DFAs
Problem Definition: Let be a (complete) deterministic finite automaton (DFA) where is a finite set of states, is a finite alphabet and is a (totally defined) transition function (we neglect start and final states). We generalize to words , by setting . We further generalize it to sets of states by . We say that a word is synchronizing for if , i.e., regardless from which state we read , we end up in the same state. We call a DFA partial , if is a partial function. For a partial DFA , we call a word carefully synchronizing, if and is defined fore each , i.e., we never try to use an undefined transition when reading from any state. The problem of DFASyncCompletion asks, given a partial DFA , is there a complete DFA such that is synchronizing and ? Open Question: What is the complexity of DFASyncCompletion? Explanation & Comments: Finding a synchronizing word for a complete DFA can be done in polynomial time, but finding a carefully synchronizing word for a partial DFA is PSPACE-complete.
