zbMATH — the first resource for mathematics

Inverse morphic equivalence on languages. (English) Zbl 0571.68061
The authors introduce the notion of inverse morphic equivalence of two morphisms g and h on a language L. Two variants are considered, the universal version, that is \(h^{-1}(x)=g^{-1}(x)\), for all x in L, and the existential version that is \(h^{-1}(x)\cap g^{-1}(x)\neq \emptyset\), for all x in L with \(h^{-1}(x)\cup g^{-1}(x)\neq \emptyset\). A finite subset F of a language L over \(\Delta\) is an inverse morphic equivalence test of L in the universal (respectively existential) sense if for all morphisms h and \(g:\Sigma^*\to \Delta^*\) the relation \(h^{-1}(x)=g^{-1}(x)\) for all x in \(F\cap (h(\Sigma^*)\cup g(\Sigma^*))\) implies the relation \(h^{-1}(x)=g^{-1}(x)\) for all x in \(L\cap (h(\Sigma^*)\cup g(\Sigma^*))\) [respectively the relation \(h^{-1}(x)\cap g^{-1}(x)\neq \emptyset\) for all x in \(F\cap (h(\Sigma^*)\cup g(\Sigma^*))\) implies the relation \(h^{-1}(x)\cap g^{-1}(x)\neq \emptyset\) for all x in \(L\cap (h(\Sigma^*)\cup g(\Sigma^*))]\). The paper discusses the existence of such test sets. Another section of the paper is dedicated to the decidability problem of whether or not two given inverse morphisms agree existentially or universally on a given language.
Reviewer: R.Andonie

68Q45 Formal languages and automata
Full Text: DOI
[1] Albert, J.; Culik, K.; Karhumäki, J., Test sets for context free languages and algebraic systems of equations over a free monoid, Inform. control, 52, 172-186, (1983) · Zbl 0522.68064
[2] Albert, J.; Wood, D., Checking sets, test sets, rich languages and commutatively closed languages, J. comput. system sci., 26, 82-91, (1983) · Zbl 0507.68049
[3] Choffrut, C.; Karhumäki, J., Test sets for bounded delay morphisms, (), 118-127
[4] Culik, K., Some decidability results about regular and pushdown translations, Inform. process. lett., 8, 5-8, (1979) · Zbl 0397.68083
[5] Culik, K., Homomorphisms: decidability, equality and test sets, (), 167-194
[6] Culik, K.; Fitch, F.; Salomaa, A., A homomorphic characterization of regular languages, Discr. appl. math., 4, 149-152, (1982) · Zbl 0481.68069
[7] Culik, K.; Karhumäki, J., On the equality sets for homomorphisms on free monoids with two generators, R.A.I.R.O. inform. theor., 14, 349-369, (1980) · Zbl 0454.20048
[8] Culik, K.; Karhumäki, J., Systems of equations over a free monoid and Ehrenfeucht’s conjecture, Discr. math., 43, 109-153, (1983) · Zbl 0528.68057
[9] Culik, K.; Salomaa, A., On the decidability of homomorphism equivalence for languages, J. comput. system sci., 17, 163-175, (1978) · Zbl 0389.68042
[10] Culik, K.; Salomaa, A., Test sets and checking words for homomorphism equivalence, J. comput. system sci., 20, 279-295, (1970)
[11] Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G., On binary equality sets and a solution to the test set conjecture in the binary case, J. algebra, 85, 76-85, (1983) · Zbl 0523.68066
[12] Eilenberg, S.; Schützenberger, M.P., Rational sets in commutative monoids, J. algebra, 13, 173-191, (1969) · Zbl 0206.02703
[13] Huet, G., An algorithm to generate the basics of solutions to homogeneous linear Diophantine equations, Inform. process. lett., 7, 144-147, (1978) · Zbl 0377.10011
[14] Karhumäki, J.; Kleijn, H.C.M., On the equivalence of compositions of morphisms and inverse morphisms on regular languages, (1983), Unpublished manuscript · Zbl 0601.68049
[15] Karhumäki, J.; Linna, M., A note on morphic characterization of languages, Discr. appl. math., 5, 243-246, (1983) · Zbl 0499.68031
[16] Karhumäki, J.; Maon, Y., A simple undecidable problem: existential inverse morphic equivalence on regular languages, (1983), Unpublished manuscript
[17] Latteux, M.; Leguy, J., On the composition of morphisms and inverse morphisms, (), 420-432 · Zbl 0523.68067
[18] Rozenberg, G.; Salomaa, A., The mathematical theory of L systems, (1980), Academic Press New York · Zbl 0365.68072
[19] Turakainen, P., On homomorphic characterization of principal semi AFL’s without using intersection with regular sets, Inform. sci., 27, 141-149, (1982) · Zbl 0506.68063
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.