zbMATH — the first resource for mathematics

The intersection problem for alphabetic vector monoids. (English) Zbl 0883.68077
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.
68Q45 Formal languages and automata
Full Text: DOI EuDML
[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
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.