← All problems
Unverified

Completing Partial DFAs to Synchronizing DFAs

Problem Definition: Let A=(Q,Σ,δ)A = (Q, \Sigma, \delta) be a (complete) deterministic finite automaton (DFA) where QQ is a finite set of states, Σ\Sigma is a finite alphabet and δ ⁣:Q×Σ→Q\delta \colon Q \times \Sigma \to Q is a (totally defined) transition function (we neglect start and final states). We generalize δ\delta to words w=w1w2…wnw= w_1w_2 \dots w_n, wi∈Σw_i \in \Sigma by setting δ(q,w)=δ(δ(q,w1)w2…wn)\delta(q, w) = \delta(\delta(q, w_1)w_2\dots w_n). We further generalize it to sets SS of states by δ(S,w)=∪q∈S{δ(q,w)}\delta(S, w) = \cup_{q\in S}\{\delta(q, w)\}. We say that a word w∈Σ∗w\in \Sigma^* is synchronizing for AA if ∣δ(Q,w)∣=1|\delta(Q, w)| = 1, i.e., regardless from which state we read ww, we end up in the same state. We call a DFA partial , if δ\delta is a partial function. For a partial DFA AA, we call a word w∈Σ∗w\in \Sigma^* carefully synchronizing, if ∣δ(Q,w)∣=1|\delta(Q, w)|=1 and δ(q,w)\delta(q, w) is defined fore each q∈Qq\in Q, i.e., we never try to use an undefined transition when reading ww from any state. The problem of DFASyncCompletion asks, given a partial DFA A=(Q,Σ,δ)A=(Q, \Sigma, \delta), is there a complete DFA A′=(Q,Σ,δ′)A'=(Q, \Sigma, \delta') such that A′A' is synchronizing and δ⊆δ′\delta \subseteq \delta'? 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.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu