Document Type

Technical Report

Publication Date

Fall 9-1-1977

Abstract

The notion of a simplification of a homomorphism is introduced and investigated. Its usefulness is demonstrated in providing rather short proofs of the following results: (i) Given an arbitrary homomorphism h and arbitrary words x, y it is decidable whether or not there exists an integer n such that h^n(x) = h^n(y). (ii) Given an arbitrary homomorphism h and arbitrary words x, y it is decidable whether or not there exists integers n and r such that h^n(x) = h^r(y) (iii) Given an arbitrary DOL system G and an arbitrary integer d it is decidable whether or not G is locally caternative of depth not larger than d. (iv) The equivalence problem for elementary polynomially bounded DOL systems is decidable.

Share

COinS