Beaudry, Martin Characterization of idempotent transformation monoids. (English) Zbl 0671.68025 Inf. Process. Lett. 31, No. 3, 163-166 (1989). Let \(\mathcal A\) be the transformation monoid of an automaton \((S,A)\), \(| S|=m\), \(| A|=n\). The following upper bounds for the sequential complexity (in terms of \(n,m\)) and for parallel complexity (in terms of log-space type uniform families of Boolean circuits) are given:1) whether \(\mathcal A\) is idempotent can be decided in \(NC^2/O(m^4n)\) (above the slash parallel, below it sequential complexity);2) whether \(\mathcal A\) belongs to \(R\) or \(L\) (\(R\) is defined by identities \(g^2=g\), \(ghg=gh\), \(L\) is dual to \(R\)) can be tested in \(NC^1/O(mn^2)\);3) whether \(\mathcal A\) belongs to \(R\vee L\) (defined by \(g^2=g\), \(ghgkg=ghkg\)) can be tested in \(NC^2/O(m^4 n^2)\). Reviewer: Jaak Henno (Tallinn) Cited in 2 Documents MSC: 68Q70 Algebraic theory of languages and automata 68Q25 Analysis of algorithms and problem complexity 20M20 Semigroups of transformations, relations, partitions, etc. Keywords:semigroup of automaton; computational complexity × Cite Format Result Cite Review PDF Full Text: DOI References: [1] Babai, L.; Luks, E.; Seress, A., Permutation groups in NC, Proc. 19th ACM Symp. on the Theory of Computing, 409-420 (1987) [2] Beaudry, M.; McKenzie, P.; Thérien, D., Testing membership: Beyond permutation groups, Proc. 6th Symp. on Theoretical Aspects of Computer Science (1989), to appear · Zbl 1492.68059 [3] Cook, S. A., The taxonomy of problems with fast parallel algorithms, Inform. and Control, 64, 2-22 (1985) · Zbl 0575.68045 [4] Eilenberg, S., Automata, Languages and Machines, Vol. B (1976), Academic Press: Academic Press New York · Zbl 0359.94067 [5] Fennemore, C., All varieties of bands I, Math. Nachr., 48, 253-262 (1971) · Zbl 0194.02801 [6] Jones, N. D., Space-bounded reducibility among combinatorial problems, J. Comput. System Sci., 11, 68-75 (1975) · Zbl 0317.02039 [7] Lallement, G., Semigroups and Combinatorial Applications (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0421.20025 [8] Stern, J., Complexity of some problems from the theory of automata, Inform. and Control, 66, 163-176 (1985) · Zbl 0603.68059 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.