UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS

DOI10.1142/S0218196799000278zbMath1027.20038OpenAlexW2041738280MaRDI QIDQ4513305

No author found.

Publication date: 7 November 2000

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218196799000278

zbMATH Keywords

pseudovarieties of finite semigroupsdecidability of membershipcomplexity of finite semigroups

Mathematics Subject Classification ID

Varieties and pseudovarieties of semigroups (20M07) Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35) Algebraic theory of languages and automata (68Q70) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35) Products, amalgamated products, and other kinds of limits and colimits (08B25)

Related Items

Reducibility of Joins Involving Some Locally Trivial Pseudovarieties, ON HYPERDECIDABLE PSEUDOVARIETIES OF SIMPLE SEMIGROUPS, INEVITABLE GRAPHS AND PROFINITE TOPOLOGIES: SOME SOLUTIONS TO ALGORITHMIC PROBLEMS IN MONOID AND AUTOMATA THEORY, STEMMING FROM GROUP THEORY, Tameness of Some Locally Trivial Pseudovarieties, Some reducibility properties for pseudovarieties of the form DRH, The \(\kappa\)-word problem over \(\mathsf{DRH}\), Unnamed Item, The uniform word problem for groups and finite Rees quotients of \(E\)-unitary inverse semigroups, On κ-reducibility of pseudovarieties of the form V ∗D, John Rhodes and the theory of finite semigroups., Complete κ-reducibility of pseudovarieties of the form DRH, The pseudoidentity problem and reducibility for completely regular semigroups, Pointlike sets with respect to R and J., TAMENESS OF JOINS INVOLVING THE PSEUDOVARIETY OF LOCAL SEMILATTICES, The word problem for \(\kappa \)-terms over the pseudovariety of local groups, ON THE DECIDABILITY OF MEMBERSHIP IN THE GLOBAL OF A MONOID PSEUDOVARIETY, Dynamics of implicit operations and tameness of pseudovarieties of groups, TAMENESS OF THE PSEUDOVARIETY LS1, Every decidable pseudovariety of abelian groups is completely tame, Semidirect product with an order-computable pseudovariety and tameness., Pointlike reducibility of pseudovarieties of the form V ∗D, Representation theory of finite semigroups, semigroup radicals and formal language theory, TAMENESS OF THE PSEUDOVARIETY OF ABELIAN GROUPS, COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1

Cites Work

• Categories as algebra: An essential ingredient in the theory of monoids
• Almost finite expansions of arbitrary semigroups
• The Birkhoff theorem for finite algebras
• Decidability of complexity one-half for finite semigroups
• Pointlike sets: the finest aperiodic cover of a finite semigroup
• Decomposition techniques for finite semigroups, using categories. I
• Decomposition techniques for finite semigroups, using categories. II
• Subsemigroups and complexity via the presentation lemma
• The word problem for cancellation semigroups with zero
• Undecidability of the identity problem for finite semigroups
• ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART I
• On Pointlike Sets and Joins of Pseudovarieties
• ALGORITHMIC PROBLEMS IN VARIETIES
• Recursive Unsolvability of a problem of Thue