# 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

##### MSC:
 68Q45 Formal languages and automata
##### Keywords:
equality set; test set; decidability; inverse morphisms
Full Text:
##### References:
  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  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  Choffrut, C.; Karhumäki, J., Test sets for bounded delay morphisms, (), 118-127  Culik, K., Some decidability results about regular and pushdown translations, Inform. process. lett., 8, 5-8, (1979) · Zbl 0397.68083  Culik, K., Homomorphisms: decidability, equality and test sets, (), 167-194  Culik, K.; Fitch, F.; Salomaa, A., A homomorphic characterization of regular languages, Discr. appl. math., 4, 149-152, (1982) · Zbl 0481.68069  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  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  Culik, K.; Salomaa, A., On the decidability of homomorphism equivalence for languages, J. comput. system sci., 17, 163-175, (1978) · Zbl 0389.68042  Culik, K.; Salomaa, A., Test sets and checking words for homomorphism equivalence, J. comput. system sci., 20, 279-295, (1970)  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  Eilenberg, S.; Schützenberger, M.P., Rational sets in commutative monoids, J. algebra, 13, 173-191, (1969) · Zbl 0206.02703  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  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  Karhumäki, J.; Linna, M., A note on morphic characterization of languages, Discr. appl. math., 5, 243-246, (1983) · Zbl 0499.68031  Karhumäki, J.; Maon, Y., A simple undecidable problem: existential inverse morphic equivalence on regular languages, (1983), Unpublished manuscript  Latteux, M.; Leguy, J., On the composition of morphisms and inverse morphisms, (), 420-432 · Zbl 0523.68067  Rozenberg, G.; Salomaa, A., The mathematical theory of L systems, (1980), Academic Press New York · Zbl 0365.68072  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.