# WORD PROBLEMS FOR BIDIRECTIONAL, SINGLE-PREMISE POST SYSTEMS

Original Publication Date: 1978-Dec-31

Included in the Prior Art Database: 2005-Sep-16

## Publishing Venue

Software Patent Institute

## Related People

Charles E. Hughes: AUTHOR [+4]

## Abstract

A bidireetionaZ, single-premise Post system is a Post canonical form F where, if [Equation ommitted] is a rule, then [Equation ommitted] is also a rule. One class of bidirectional Post systems, the T hue systems first defined in [71, have been extensively studied. Thue systems with unsolvable word problems were shown to exist by Post [51 and, more recently, Overbeek 14] demonstrated that this class of problems represents every recursively enumerable (r. e.) many-one degree of unsolvability. In this paper we extend Overbeek's result to include bidirectional extensions of Post. normal systems, tag systems and the one-letter systems introduced by Hosken [1].

**This text was extracted from a PDF file.**

**This is the abbreviated version, containing approximately 17% of the total text.**

__Page 1 of 12__THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

**WORD PROBLEMS FOR BIDIRECTIONAL, SINGLE-PREMISE POST
SYSTEMS **

Charles E. Hughes David W. Straight

CS-78-32 October 1978 >

**Introduction **

A bidireetionaZ, single-premise Post system is a Post canonical form F where, if

(Equation Omitted)

is a rule, then

(Equation Omitted)

is also a rule. One class of bidirectional Post systems, the T hue systems first defined in [71, have been extensively studied. Thue systems with unsolvable word problems were shown to exist by Post [51 and, more recently, Overbeek 14] demonstrated that this class of problems represents every recursively enumerable (r. e.) many-one degree of unsolvability. In this paper we extend Overbeek's result to include bidirectional extensions of Post. normal systems, tag systems and the one-letter systems introduced by Hosken [1].

Post Systems. Let E be ,a finite set of symbols and let

(Equation Omitted)

On be new symbols called operational variables. A word over

(Equation Omitted)

containing at least one operational variable, is called a word form. An identification of the operational variables

(Equation Omitted)

Qn is a set of pairs

(Equation Omitted)

where each Wi is a word over E. Let

(Equation Omitted)

be a word form where

(Equation Omitted)

University of Tennessee Page 1 Dec 31, 1978

__Page 2 of 12__WORD PROBLEMS FOR BIDIRECTIONAL, SINGLE-PREMISE POST SYSTEMS

are words over

(Equation Omitted)

are operational variables. Then Y' is the result of

applying the identification

(Equation Omitted)

denoted Y~, if

(Equation Omitted)

A single-premise Post system

(Equation Omitted)

is such that E is a finite alphabet, V is a finite set of operational variables and P is a finite set of rules, each of the form

(Equation Omitted)

where

(Equation Omitted)

are word forms. Let

(Equation Omitted)

be words over E. Then W2 is said to be an immediate successor of

(Equation Omitted)

if there exists some rule of

(Equation Omitted)

, and some identification ~D of V such that

(Equation Omitted)

is said to be derivable from W1 in F, denoted

(Equation Omitted)

, whenever F is understood from context), if there exists a sequence

(Equation Omitted)

University of Tennessee Page 2 Dec 31, 1978

__Page 3 of 12__WORD PROBLEMS FOR BIDIRECTIONAL, SINGLE-PREMISE POST SYSTEMS

where k > 1, of words over E such that

(Equation Omitted)

and for each

(Equation Omitted)

The Zength of the above derivation is k-1 and each Yi is said to be in the derivation of W2 from W1. A Post normal system

(Equation Omitted)

is a Post system where each rule is of the form a Q:+ Q~, for a and s words over E. Let

(Equation Omitted)

be a Post normal system where

(Equation Omitted)

Then N is called a tag system if there exist a constant positive integer d, called the deZetzon number of N, and for each i, 1 < i < n, a word Wig uniquely corresponded with a,, such that

(Equation Omitted)

is a word over

(Equation Omitted)

A restricted Post canonical formeee is a system where each r...