The complexity of properties of transformation semigroups

DOI10.1142/S0218196720500125MaRDI QIDQ4960463zbMATH OpenOpenAlexWikidataFDO

Authors Lukas Fleischer, Trevor Jack

Publication date 16 April 2020

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.00060

zbMATH Keywords

\(\mathsf{NL}\)-completeness\(\mathsf{PSPACE}\)-completenessalgorithmscomputational complexityregular elementssemigroup identitiestransformation semigroups

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: We investigate the computational complexity for determining various properties of a finite transformation semigroup given by generators. We introduce a simple framework to describe transformation semigroup properties that are decidable in $mathsfA{C}^0$. This framework is then used to show that the problems of deciding whether a transformation semigroup is a group, commutative or a semilattice are in $mathsfA{C}^0$. Deciding whether a semigroup has a left (resp.right) zero is shown to be $mathsfNL$-complete, as are the problems of testing whether a transformation semigroup is nilpotent, $mathcalR$-trivial or has central idempotents. We also give $mathsfNL$ algorithms for testing whether a transformation semigroup is idempotent, orthodox, completely regular, Clifford or has commuting idempotents. Some of these algorithms are direct consequences of the more general result that arbitrary fixed semigroup equations can be tested in~$mathsfNL$. Moreover, we show how to compute left and right identities of a transformation semigroup in polynomial time. Finally, we show that checking whether an element is regular is $mathsfPSPACE$-complete.

Recommendations

• Complexity of the identity checking problem for finite semigroups.
• Complexity of identity checking in transformation semigroups of rank 2.
• scientific article; zbMATH DE number 4068272
• RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
• The subpower membership problem for semigroups

Cites work

• Complexity Analysis: Transformation Monoids of Finite Automata
• Computing finite semigroups
• Finite-automaton aperiodicity is PSPACE-complete
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• scientific article; zbMATH DE number 3341276 (Why is no real title available?)
• Space-bounded reducibility among combinatorial problems
• Undirected connectivity in log-space

Cited in

(21)

• Characterization of idempotent transformation monoids
• Another semigroup of complexity \(n-1\)
• Transformation completeness properties of SVPC transformation sets
• Checking quasi-identities in a finite semigroup may be computationally hard.
• Effective dimension of finite semigroups.
• Complexity of shift spaces on semigroups
• Green's relations in finite transformation semigroups
• Complexity of identity checking in transformation semigroups of rank 2.
• SOME RESULTS ON ČERNÝ TYPE PROBLEMS FOR TRANSFORMATION SEMIGROUPS
• scientific article; zbMATH DE number 4041312 (Why is no real title available?)
• scientific article; zbMATH DE number 4068272 (Why is no real title available?)
• The membership problem in aperiodic transformation monoids
• Identity checking problem for transformation monoids
• RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
• The Cayley semigroup membership problem
• scientific article; zbMATH DE number 7250165 (Why is no real title available?)
• The intersection problem for finite semigroups
• Degree 2 transformation semigroups as continuous maps on graphs: Complexity and examples
• On the complexity of inverse semigroup conjugacy
• Complexity of the identity checking problem for finite semigroups.
• Bitranslations of completely simple semigroups.

Describes a project that uses

Uses Software

• Semigroups

This page was built for publication: The complexity of properties of transformation semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4960463)