×

Equivalence problems for regular sets of word morphisms. (English) Zbl 0612.68052

The book of L, dedic. A. Lindenmayer Occas. 60th Birthday, 393-401 (1986).
[For the entire collection see Zbl 0575.00023.]
Let R be a regular language over \(\Sigma\) and \(E_{\Delta}\) be the monoid of endomorphisms on \(\Delta^*\), \(\Sigma\) and \(\Delta\) arbitrary finite alphabets. The strong morphical equivalence problem is decidable for R if there exists an algorithm which of any two given morphisms \(\mu_ 1,\mu_ 2:\Sigma^*\to E_{\Delta}\) decides whether or not \(\mu_ 1(w)=\mu_ 2(w)\), \(\forall w\in R\). The first part of the paper is dedicated to a new proof of the strong morphical equivalence problem based on certain concepts of metabelian groups. The second part is a survey on eleven known cases of the morphical equivalence problem. This problem is decidable for regular languages \(R_ 1\), \(R_ 2\) if there exists an algorithm which of any two given morphisms \(\mu_ 1,\mu_ 2:\Sigma^*\to E_{\Delta}\) decides whether or not \(\mu_ 1(R_ 1)=\mu_ 2(R_ 2)\).
Reviewer: G.Grigoras

MSC:

68Q70 Algebraic theory of languages and automata
68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems

Citations:

Zbl 0575.00023