The Solvability of the Derivability Problem for One-Normal Systems
Author:
Open Access
- 1 April 1966
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 13 (2) , 223-225
Abstract
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).Keywords
This publication has 2 references indexed in Scilit:
- Universality of Tag Systems with P = 2Journal of the ACM, 1964
- Formal Reductions of the General Combinatorial Decision ProblemAmerican Journal of Mathematics, 1943