The complexity of properties of transformation semigroups

DOI10.1142/S0218196720500125zbMath1484.20110arXiv1811.00060OpenAlexW2982659846WikidataQ114614798 ScholiaQ114614798MaRDI QIDQ4960463

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

algorithmscomputational complexityregular elementstransformation semigroupssemigroup identities\(\mathsf{NL}\)-completeness\(\mathsf{PSPACE}\)-completeness

Mathematics Subject Classification ID

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

Related Items (1)

On the complexity of inverse semigroup conjugacy

Uses Software

• Semigroups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite-automaton aperiodicity is PSPACE-complete
• Space-bounded reducibility among combinatorial problems
• Computing finite semigroups
• Complexity Analysis: Transformation Monoids of Finite Automata
• Undirected connectivity in log-space

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