Homomorphic correspondences of relational systems. (English) Zbl 0589.20050

In this paper the concept of a homomorphism of a language is generalized. Our considerations are motivated by the theorems on the homomorphisms of languages which have appeared in the algebraic linguistics [see M. Novotný, Probl. Kibern. 15, 235-244 (1965; Zbl 0296.68073)]. But there occur certain asymmetries in these theorems. If two languages and a homomorphism of one of them onto the other are given, then the situation of both languages is asymmetric, because in general there exists no homomorphism of the second language onto the first one. Symmetric formulations of the theorems on languages can be attained in such a way that instead of homomorphisms we take correspondences between the languages which in a certain sense preserve the correctness of the theorems.


20M35 Semigroups in automata theory, linguistics, etc.
08A35 Automorphisms and endomorphisms of algebraic structures
68Q45 Formal languages and automata


Zbl 0296.68073
Full Text: EuDML


[1] Novotný M.: Ob algebraizacii teoretiko-množestvennoj modeli jazyka. Problemy kibernetiki, vyp. 15, str. 235-245, Moskva 1965.
[2] Malcev A. I.: Algebraičeskije systemy. Moskva 1979, izd. Nauka.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.