The intersection problem for alphabetic vector monoids. (English) Zbl 0883.68077

Harju, T.; Keesmaat, N. W.; Kleijn, H. C. M.

RAIRO, Inform. Théor. Appl. 28, No. 3-4, 295-301 (1994).

Summary: Let \(\Sigma\) and \(\Gamma\) be two vector alphabets consisting of alphabetic vectors \((a_1,a_2)\), where \(a_1,a_2\in A\cup \{\varepsilon\}\) for an alphabet \(A\). We show that it is decidable whether or not \(\Sigma^\otimes \cap \Gamma^\otimes\) is the trivial submonoid of the direct product \(A^* \times A^*\) for the generated submonoids \(\Sigma^\otimes\) and \(\Gamma^\otimes\). On the other hand we show that a simple version, obtained from letter-to-letter homomorphisms, of the modified Post Correspondence Problem is undecidable for alphabetic vectors.

MSC:

68Q45

Formal languages and automata

Keywords:

alphabetic vectors

References:

[1]	1. A. ARNOLD, Synchronized Behaviours of Processes and Rational relations, Acta Informatica, 1982, 77, pp. 21-29. Zbl0478.68027 MR662875 · Zbl 0478.68027 · doi:10.1007/BF00262973
[2]	2. J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, Mass., 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[3]	3. N. W. KEESMAAT, H. C. M. KLEUN, The Effect of Vector Synchronization: Residue and Loss, Lectures Notes in Comput. Sci., 1992, 609, pp. 215-250. MR1253535
[4]	4. N. W. KEESMAAT, H. C. M. KLEIJN and G. ROZENBERG, Vector Controlled Concurrent Systems, Part I: Basic Classes, Fundamenta Informaticae, 1990, 13, pp. 275-316. Zbl0713.68024 MR1090690 · Zbl 0713.68024