On the Decidability of Iterated Semidirect Products with Applications to Complexity

DOI10.1112/S0024611500012144zbMath1027.20033OpenAlexW1996281160MaRDI QIDQ4487602

Benjamin Steinberg, Jorge Almeida

Publication date: 22 June 2000

Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1112/s0024611500012144

zbMATH Keywords

semidirect productspseudovarieties of 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 ⋮ NORMAL FORMS FOR FREE APERIODIC SEMIGROUPS ⋮ PROFINITE SEMIGROUPS, VARIETIES, EXPANSIONS AND THE STRUCTURE OF RELATIVELY FREE PROFINITE SEMIGROUPS ⋮ ON THE HYPERDECIDABILITY OF PSEUDOVARIETIES OF GROUPS ⋮ PROFINITE METHODS IN SEMIGROUP THEORY ⋮ COMBINATORIAL GROUP THEORY, INVERSE MONOIDS, AUTOMATA, AND GLOBAL SEMIGROUP THEORY ⋮ Reducibility of pointlike problems ⋮ Pointlike sets and separation: a personal perspective ⋮ Tameness of Some Locally Trivial Pseudovarieties ⋮ Pointlike sets for varieties determined by groups ⋮ SOLVABLE MONOIDS WITH COMMUTING IDEMPOTENTS ⋮ An automata-theoretic approach to the word problem for \(\omega\)-terms over R ⋮ Some reducibility properties for pseudovarieties of the form DRH ⋮ Recognizing pro-\(\mathrm{R}\) closures of regular languages ⋮ McCammond’s normal forms for free aperiodic semigroups revisited ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ Iterated periodicity over finite aperiodic semigroups ⋮ On κ-reducibility of pseudovarieties of the form V ∗D ⋮ On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties. ⋮ Complete κ-reducibility of pseudovarieties of the form DRH ⋮ Closures of regular languages for profinite topologies. ⋮ Finite state automata: A geometric approach ⋮ An effective lower bound for group complexity of finite semigroups and automata ⋮ Towards a pseudoequational proof theory ⋮ The pseudoidentity problem and reducibility for completely regular semigroups ⋮ TAMENESS OF JOINS INVOLVING THE PSEUDOVARIETY OF LOCAL SEMILATTICES ⋮ The word problem for \(\kappa \)-terms over the pseudovariety of local groups ⋮ The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages ⋮ Dynamics of implicit operations and tameness of pseudovarieties of groups ⋮ TAMENESS OF THE PSEUDOVARIETY LS1 ⋮ Every decidable pseudovariety of abelian groups is completely tame ⋮ Free profinite locally idempotent and locally commutative semigroups ⋮ On the equation \({\mathbf V}*{\mathbf G}={\mathcal E}{\mathbf V}\) ⋮ Semidirect product with an order-computable pseudovariety and tameness. ⋮ The geometry of profinite graphs with applications to free groups and finite monoids ⋮ TAMENESS OF THE PSEUDOVARIETY OF ABELIAN GROUPS ⋮ COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1 ⋮ Relative Abelian kernels of some classes of transformation monoids ⋮ SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS ⋮ The pseudovariety of all nilpotent groups is tame ⋮ Profinite topologies ⋮ Algebraic tools for the concatenation product. ⋮ Tameness of pseudovariety joins involving R.