Document Type

Technical Report

Publication Date

Summer 8-1-1979

Abstract

A DOS system is like a DOL system except that at each derivation step the underlying homomorphism is applied to one occurrence in a word only. It is shown that given two arbitrary DOS systems having the same “rewriting mapping” it is undecidable whether or not their languages intersect. Since the analogous problem is decidable for DOL systems, and a DOS system is a “sequential analogue” of a DOL system, this result points out an essential difference between parallel and sequential rewriting systems.

Share

COinS