Subsemigroups and complexity via the presentation lemma

DOI10.1016/0022-4049(94)00063-OMaRDI QIDQ1899162zbMATH OpenWikidataFDO

Authors Beverly Austin, Karsten Henckell, Chrystopher L. Nehaniv, John L. Rhodes

Publication date 16 April 1996

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

zbMATH Keywords

complexityidempotentsfinite semigroupsKrohn-Rhodes decomposition theoremPresentation Lemmaregular \(\mathcal J\)-classesalternating wreath product of groups and finite aperiodic semigroups

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) General structure theory for semigroups (20M10)

Recommendations

• COMPLEXITY PSEUDOVARIETIES ARE NOT LOCAL: TYPE II SUBSEMIGROUPS CAN FALL ARBITRARILY IN COMPLEXITY
• Krohn-Rhodes complexity of Brauer type semigroups.
• On aperiodic relational morphisms.
• scientific article; zbMATH DE number 1419247

Cites work

• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 3654376 (Why is no real title available?)
• scientific article; zbMATH DE number 3552814 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 1342311 (Why is no real title available?)
• scientific article; zbMATH DE number 864832 (Why is no real title available?)
• Categories as algebra: An essential ingredient in the theory of monoids
• Kernel systems - a global study of homomorphisms on finite semigroups
• Pointlike sets: the finest aperiodic cover of a finite semigroup

Cited in

(19)

• Krohn-Rhodes complexity of Brauer type semigroups.
• From relation to emulation: The covering lemma for transformation semigroups
• Improved lower bounds for the complexity of finite semigroups
• ON HYPERDECIDABLE PSEUDOVARIETIES OF SIMPLE SEMIGROUPS
• On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties.
• Degree 2 transformation semigroups as continuous maps on graphs: Complexity and examples
• COMPLEXITY PSEUDOVARIETIES ARE NOT LOCAL: TYPE II SUBSEMIGROUPS CAN FALL ARBITRARILY IN COMPLEXITY
• ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM
• HOLONOMY EMBEDDING OF ARBITRARY STABLE SEMIGROUPS
• UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
• Krohn-Rhodes complexity pseudovarieties are not finitely based
• ON THE KROHN–RHODES COMPLEXITY OF SEMIGROUPS OF UPPER TRIANGULAR MATRICES
• Another semigroup of complexity \(n-1\)
• WHAT ARE MODULES? AN OVERVIEW OF BRET TILSON'S PAPER "MODULES" FROM A GEOMETRIC VIEWPOINT
• The Rhodes semilattice of a biased graph
• On complete systems of automata
• On the Dowling and Rhodes lattices and wreath products
• An effective lower bound for group complexity of finite semigroups and automata
• On calculating the Krohn-Rhodes decomposition of automata

This page was built for publication: Subsemigroups and complexity via the presentation lemma

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