Lower bounds for complexity of finite semigroups

DOI10.1016/0022-4049(71)90012-0zbMath0259.20051MaRDI QIDQ2560324

Bret Tilson, John L. Rhodes

Publication date: 1971

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-4049(71)90012-0

Mathematics Subject Classification ID

68Q45: Formal languages and automata

20M10: General structure theory for semigroups

20M35: Semigroups in automata theory, linguistics, etc.

Related Items

Krohn-Rhodes complexity pseudovarieties are not finitely based, INEVITABLE GRAPHS AND PROFINITE TOPOLOGIES: SOME SOLUTIONS TO ALGORITHMIC PROBLEMS IN MONOID AND AUTOMATA THEORY, STEMMING FROM GROUP THEORY, PROFINITE METHODS IN SEMIGROUP THEORY, An effective lower bound for group complexity of finite semigroups and automata, The fundamental lemma of complexity for arbitrary finite semigroups, Studies in the Representation Theory of Finite Semigroups, Type-II conjecture is true for finite \(\mathcal J\)-trivial monoids, Finite binary relations have no more complexity than finite functions, Zig-zag representations and inverse semigroups, \(\pi\)-length of union of groups semigroups, Kernel systems - a global study of homomorphisms on finite semigroups, The complexity of economic decision rules, The group-theoretic complexity of subsemigroups of Boolean matrices, Lower bounds for the \(\pi\)-length of (finite) \(\pi\)-solvable semigroups, Product expansions, John Rhodes and the theory of finite semigroups., Decomposition and complexity of finite semigroups, Improved lower bounds for the complexity of finite semigroups, BRET TILSON: HIS LIFE AND WORK, A PROFINITE APPROACH TO STABLE PAIRS

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of finite semigroups
• Some results on finite semigroups
• Methods of the algebraic theory of machines. I: Decomposition theorem for generalized machines; properties preserved under series and parallel compositions of machines
• Cascade synthesis of finite-state machines
• Complexity of ideals in finite semigroups and finite-state machines
• A homomorphism theorem for finite semigroups