Representations of language families by homomorphic equality operations and generalized equality sets (Q1099633)

For any word w over an alphabet \(\Sigma\), let w 1 be w and w R the mirror image of w; if \(h_ 1,..,h_ n\) are monoid homomorphisms defined on \(\Sigma\) * and if \(\rho\) maps \(\{\) 1,...,n\(\}\) into \(\{\) 1,R\(\}\), then \(<h_ 1,...,h_ n>_{\rho}(w)=h_ 1(w)^{\rho (1)}\) when \(h_ 1(w)^{\rho (1)}=...=h_ n(w)^{\rho (n)}\), otherwise \(<h_ 1,...,h_ n>_{\rho}(w)\) is undefined. Such partial functions \(<h_ 1,...,h_ n>_{\rho}\) and their inverses \(<h_ 1,...,h_ n>^{- 1}_{\rho}\) are called homomorphic equalities and inverse homomorphic equalities, respectively; the domains of homomorphic equalities are called generalized equality sets. Extensively and meticulously the author shows how these notions can be brought to bear in formal language theory, the main section headings being: Generalized equality sets and representations of the regular sets, Trios over generalized equality sets, Homomorphic representations of the recursively enumerable sets, Homomorphic and inverse homomorphic equality operations, Preset machines and equality operations. One conspicuous result is the generation of the recursively enumerable sets from a one- element set by applying an inverse homomorphism, a homomorphic equality of two nonerasing homomorphisms, and one more homomorphism.