zbMATH — the first resource for mathematics

Cardinality problems of compositions of morphisms and inverse morphisms. (English) Zbl 0685.68065
Summary: We show that we cannot effectively determine whether, for morphisms \(\alpha_ i\), \(\beta_ i\), \(card(u\alpha_ 0^{-1}\alpha_ 1)=card(u\beta_ 0^{-1}\beta_ 1)\) for all words u over the domain alphabets of the two given compositions. In contrast it is decidable for morphisms \(\alpha_ i\), \(\beta_ i\) and a regular set R whether \(card(u\alpha_ 0\alpha_ 1^{-1})=card(u\beta_ 0\beta_ 1^{-1})\) for all words u in R. In order to prove the latter result we give a characterization of the multiplicity functions of simple finite automata by using cardinalities of compositions of the above form. Finally, we show that the above decidability result also holds when we consider rational functions rather than morphisms.

68Q45 Formal languages and automata
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
08A50 Word problems (aspects of algebraic structures)
03D40 Word problems, etc. in computability and recursion theory
Full Text: DOI
[1] J. Berstel,Transductions and Context-Free Languages, Teubner, Stuttgart, 1979. · Zbl 0424.68040
[2] M. Blattner, T. Head, Single-valueda-transducers,J. Comput. System Sci.,15 (1977), 310–327. · Zbl 0367.94071 · doi:10.1016/S0022-0000(77)80033-0
[3] L. Boasson, M. Nivat, Sur diverses familles de languages fermées par transduction rationnelle,Acta Inform.,2 (1973), 180–188. · Zbl 0242.68037
[4] S. Eilenberg,Automata, Languages, and Machines, Vol. A, Academic Press, New York, 1974. · Zbl 0317.94045
[5] T. V. Griffiths, The unsolvability of the equivalence problem for A-free nondeterministic generalized sequential machines,J. Assoc. Comput. Mach.,15 (1968), 409–413. · Zbl 0162.02302
[6] M. A. Harrison,Introduction to Formal Language Theory, Addison-Wesley, Reading, MA, 1978. · Zbl 0411.68058
[7] J. Karhumäki, H. C. M. Kleijn, On the equivalence of compositions of morphisms and inverse morphisms on regular languages,RAIRO Inform. Théor.,19 (1985), 203–211. · Zbl 0601.68049
[8] M. Latteux, J. Leguy,On the Composition of Morphisms and Inverse Morphisms, Lecture Notes in Computer Science, Vol. 154, Springer-Verlag, Berlin, 1983, pp. 420–432. · Zbl 0523.68067
[9] M. P. Schützenberger, Sur les rélations rationnelles entre monoides libres,Theoret. Comput. Sci.,3 (1976), 243–259. · Zbl 0358.68129 · doi:10.1016/0304-3975(76)90026-8
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.