Lower bounds for complexity of finite semigroups

DOI10.1016/0022-4049(71)90012-0MaRDI QIDQ2560324zbMATH OpenOpenAlexFDO

Authors 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

General structure theory for semigroups (20M10) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Cites work

• A homomorphism theorem for finite semigroups
• Cascade synthesis of finite-state machines
• Complexity of finite semigroups
• Complexity of ideals in finite semigroups and finite-state machines
• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 3287733 (Why is no real title available?)
• Methods of the algebraic theory of machines. I: Decomposition theorem for generalized machines; properties preserved under series and parallel compositions of machines
• Some results on finite semigroups

Cited in

(22)

• 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.
• The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs
• 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
• A Burnside ring for monoids

This page was built for publication: Lower bounds for complexity of finite semigroups

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