Proof of the fundamental lemma of complexity (strong version) for arbitrary finite semigroups

DOI10.1016/0097-3165(74)90045-4zbMath0323.20069OpenAlexW4235867836WikidataQ124936987 ScholiaQ124936987MaRDI QIDQ1224177

K. Appert

Publication date: 1974

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(74)90045-4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Representation of semigroups; actions of semigroups on sets (20M30)

Related Items (8)

John Rhodes and the theory of finite semigroups. ⋮ An effective lower bound for group complexity of finite semigroups and automata ⋮ Group-complexity and reversals of finite semigroups ⋮ On the complexity of finite semigroups ⋮ Finite binary relations have no more complexity than finite functions ⋮ Kernel systems - a global study of homomorphisms on finite semigroups ⋮ Decomposition and complexity of finite semigroups ⋮ Improved lower bounds for the complexity of finite semigroups

Cites Work

• Unnamed Item
• Complexity of finite semigroups
• Proof of the fundamental lemma of complexity (weak version) for arbitrary finite semigroups
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• The fundamental lemma of complexity for arbitrary finite semigroups

This page was built for publication: Proof of the fundamental lemma of complexity (strong version) for arbitrary finite semigroups