The Solvability of the Derivability Problem for One-Normal Systems
Stephen A Cook · Journal of the ACM · 1966
A one-normal system is a Post production system on a finite alphabet { s 1 , s 2 , · · ·, s σ } with productions s i P → PE ij , where i ranges over a subset of {1, 2, · · ·, σ} and, for fixed i , j takes on the values 1, 2, · · ·, n i . The following derivability problem is shown to be solvable for each such system: Given two words P and Q , decide whether Q can be derived from P by successive applications of the production rules. The result was proved by Hao Wang for the monogenic case (i.e., when each n i = 1).