Computational complexity of problems for deterministic presentations of sofic shifts

The paper proves that seven natural decision problems for sofic shifts given by deterministic presentations are PSPACE-complete, with explicit polynomial-time reductions (from DFAUNION for EQUALITY, SUBSHIFT, IRREDUCIBILITY, ∃SDP, SFT, and MINIMALITY; and from DFAINT for SYNCWORD) and detailed PSPACE-membership arguments via the relational “action of a word” apparatus in Appendix A. These results are stated as Theorem 4.1 and supported throughout Section 4 and Appendix A . By contrast, the candidate solution, while matching the headline claims, relies on several incorrect or missing logical steps. Most notably: (i) it asserts that a shift has a synchronizing deterministic presentation iff there exists an intrinsically synchronizing word, which contradicts the paper’s precise criterion (Theorem 2.3 requires the intrinsically synchronizing word to arise after every context u) ; (ii) it characterizes SFT via cycles avoiding “singleton follower sets” in a powerset/follower automaton, which is not generally correct and is replaced in the paper by a PSPACE method based on actions and a general step bound (Proposition A.1) ; and (iii) its sketched “barbell” reduction for IRREDUCIBILITY confuses irreducibility (existence of some bridge uwv in the language) with a requirement that multiple exits synchronize simultaneously. The paper’s reductions and proofs for IRREDUCIBILITY, EQUALITY, SUBSHIFT, ∃SDP, SFT, and MINIMALITY avoid these pitfalls and are consistent and complete .