On the topological structure of a finitely generated semigroup of matrices. (English) Zbl 0646.20056

From the author’s introduction: The aim of this paper is to show that there is an algorithm to compute a certain homomorphic image of the topological closure of a finitely generated semigroup of matrices over \(M_ 1\), where \(M_ 1=({\mathbb{N}}\cup \{\omega,\infty \},\min.,+,\infty,0)\). Hence we obtain another proof that the limitedness problem is decidable. In addition, a faster decision algorithm can be derived. In this paper, we also extend the result to show that there is an algorithm to compute a certain homomorphic image of the topological closure of a finitely generated semigroup of matrices over \(M_ 2\) where \(M_ 2=({\mathbb{N}}\cup \{\infty \},+,.,0,1)\) and \(\omega\) is the point at infinity.
Reviewer: Ph.Das


20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
20M20 Semigroups of transformations, relations, partitions, etc.
Full Text: DOI EuDML


[1] Brown, T. C., An Interesting Combinatorial Method in the Theory of Locally Finite Semigroups, Pacific Journal of Mathematics, 36, 285-289 (1971) · Zbl 0211.33504 · doi:10.2140/pjm.1971.36.285
[2] Chan, T. H.; Ibarra, O., On the Finite-Valuedness Problem for Sequential Machines, Theoretical Computer Science, 23, 95-101 (1983) · Zbl 0503.68037 · doi:10.1016/0304-3975(88)90012-6
[3] Green, J. A., On the Structure of Semigroups, Annals of Mathematics, 54, 2, 163-172 (1951) · Zbl 0043.25601 · doi:10.2307/1969317
[4] Hashiguchi, K., Limitedness Theorem on Finite Automata with Distance Functions, Journal of Computer and System Sciences, 24, 233-244 (1982) · Zbl 0513.68051 · doi:10.1016/0022-0000(82)90051-4
[5] Hashiguchi, K.,Improved Limitedness Theorems on Finite Automata with Distance Functions, Rapport LITP Université Paris 6 86-72 (1986).
[6] Jacob, G., La finitude des representations linéaires des semi-groupes est décidable, Journal of Algebra, 52, 437-459 (1978) · Zbl 0374.20074 · doi:10.1016/0021-8693(78)90249-1
[7] Lallement, G., Semigroups and Combinatorial Applications (1979), New York: John Wiley and Sons, New York · Zbl 0421.20025
[8] Leung, H.,An Algebraic Method for Solving Decision Problems in Finite Automata Theory, Ph.D. Dissertation, Department of Computer Science, The Pennsylvania State University (1987).
[9] Mandel, A.; Simon, I., On Finite Semigroups of Matrices, Theoretical Computer Science, 5, 101-111 (1977) · Zbl 0368.20049 · doi:10.1016/0304-3975(77)90001-9
[10] McNaughton, R.; Zalcstein, Y., The Burnside Problem for Semigroups, Journal of Algebra, 34, 292-299 (1975) · Zbl 0302.20054 · doi:10.1016/0021-8693(75)90184-2
[11] Simon, I.,Limited Subsets of a Free Monid, Proc. Nineteenth Annual IEEE Symposium on Foundations of Computer Science (1978), 143-150.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.