Characterization of idempotent transformation monoids
type: Item
instance of: scholarly article
title: Characterization of idempotent transformation monoids
zbMATH Open document ID: 0671.68025
DOI: 10.1016/0020-0190(89)90226-3
author: Martin Beaudry
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 20M20
zbMATH DE Number: 4098727
zbMATH Keywords: semigroup of automaton
zbMATH Keywords: computational complexity
reviewed by: Jaak Henno
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90226-3
OpenAlex ID: W1964726605
cites work: Testing membership: Beyond permutation groups
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Q4132170
cites work: All Varieties of Bands I
cites work: Space-bounded reducibility among combinatorial problems
cites work: Q3853827
cites work: Complexity of some problems from the theory of automata
description: scientific article; zbMATH DE number 4098727