The Solvability of the Derivability Problem for One-Normal Systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Solvability of the Derivability Problem for One-Normal Systems

Full text

Pdf (208 KB)

Source

Journal of the ACM (JACM) archive
Volume 13 , Issue 2 (April 1966) table of contents

Pages: 223 - 225

Year of Publication: 1966

ISSN:0004-5411

Author

Stephen A. Cook

Harvard University, Cambridge, Massachusetts

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 16, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321328.321333 What is a DOI?

ABSTRACT

A one-normal system is a Post production system on a finite alphabet {s1, s2, · · ·, s&sgr;} with productions siP → PEij, where i ranges over a subset of {1, 2, · · ·, &sgr;} and, for fixed i, j takes on the values 1, 2, · · ·, ni. 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 ni = 1).

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	John Cocke , Marvin Minsky, Universality of Tag Systems with P = 2, Journal of the ACM (JACM), v.11 n.1, p.15-20, Jan. 1964 [doi>10.1145/321203.321206]
	2	POST, E. L. Formal reduction of the general combinatorial decision problem. Amer. J. Math. 65 (1943), 197-215.
	3	WAN, HAO. Tag systems and lag systems. Math. Ann. 152 (1963), 6574.