Characterization of idempotent transformation monoids (Q1119394): Difference between revisions

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)\).