Adherence equivalence is decidable for DOL languages. (English) Zbl 0543.68060

Theoretical aspects of computer science, Symp., Paris 1984, Lect. Notes Comput. Sci. 166, 241-249 (1984).
[For the entire collection see Zbl 0533.00025.]
Let L be a language consisting of strings of finite length over a finite alphabet A. The adherence of L consists of all those infinite sequences s over A for which every finite initial segment of s is an initial segment of a string in L. The adherence of L is non-empty if and only if L is infinite. A DOL system \(G=(A,h,w)\) consists of a finite alphabet A, a homomorphism \(h:A^*\to A^*,\) and a non-empty string w in \(A^*\) called the start string of G. Such a system G generates a language \(L(G)=\{h^ n(w):\quad n\geq 0\}.\) A language L is a DOL language if \(L=L(G)\) for some DOL system G. The adherence of every DOL language is finite as was noted by K. Culik and A. Salomaa [Theor. Comput. Sci. 19, 29-38 (1982; Zbl 0492.68059)]. The title of the present paper gives its fundamental result. It is proved by reducing it to three problems: [I] Decide whether two arbitrarily given sequences of form (1) are equal; [II] Decide whether an arbitrarily given sequence of form (1) and an arbitrarily given sequence of form (2) are equal; [III] Decide whether two arbitrarily given sequences of fom (2) are equal; where (1) means that the sequence has the form \(uv^{\omega}\) for finite strings u,v over A and the form (2) is: \(wsh(s)h^ 2(s)...h^ n(s)...\) for finite strings w,s over A and a homomorphism \(h:A^*\to A^*\) for which \(h(w)=ws\). Problem [I] is easily handled by observing that v can be taken primitive with the property that its right-most symbol differs from the right-most symbol of u. When this is done u and v are unique. Problem [II] is handled by an algorithm provided in the paper especially for this purpose. Problem [III] is the most difficult, but it has previously been solved by K. Culik and T. Harju in ’The \(\omega\)-sequence equivalence problem for DOL systems is decidable’ [Proc. 13th ACM Symp. Theory of Computing, 1-6 (1981)].
In his oral presentation of the paper being reviewed the author also pointed out that it can be decided whether a context free language has a finite adherence. Moreover, when such an adherence is finite, each sequence in the adherence has the form (1) above. Consequently it is decidable whether the language given by an arbitrary context free grammar and an arbitrary DOL system have the same adherence.


68Q45 Formal languages and automata