Errata for the paper "Predecessor existence problems for finite discrete dynamical systems" [TCS 386 (1-2) (2007) 3-37]
We point out some minor corrections to the proof of Theorem 4.1 in the above paper. As presented, the proof of Theorem 4.1 uses a reduction from a special version of the Planar 3SAT problem (called RP3SAT) in which each clause has exactly three literals, each variable appears in at most three clauses and the factor graph corresponding to the instance is planar. It is incorrect to use a reduction from RP3SAT to prove the hardness of the predecessor existence problems for SDSs and SyDSs on grids since the RP3SAT problem is efficiently solvable even without the planarity restriction, as shown by Tovey [2]. However, the result of Theorem 4.1 can be established by a reduction from a restricted version of Planar 3SAT (henceforth referred to as Pl-B3SAT) in which each clause has two or three literals and each variable appears in at most three clauses. There is a local replacement-based ultra efficient (decision, parsimonious) reduction from 3SAT to Pl-B3SAT [1]. Thus, Pl-B3SAT is NP-complete, #Pl-B3SAT is #P-complete, Unique-Pl-B3SAT is DP -complete and Ambiguous-Pl-B3SAT is NP-complete. In the proof of Theorem 4.1, when the reduction is carried out from Pl-B3SAT, the constructions of the underlying grids for both SDSs and SyDSs remain the same. The only change is that the local transition functions for each node corresponding to a two literal clause should be the 4-simple-threshold function. (For each node corresponding to a three literal clause, the local transition function remains the 3-simple-threshold function, as in the paper.) Because of this change, some minor modifications are also needed for a few sentences in the discussion of the construction. These modifications are indicated below. (The page and line numbers used in the following discussion correspond to the corrected page proofs for the paper.)