On the Decidability of Iterated Semidirect Products with Applications to Complexity
DOI10.1112/S0024611500012144zbMATH Open1027.20033OpenAlexW1996281160MaRDI QIDQ4487602FDOQ4487602
Authors: 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
Recommendations
- On the hyperdecidability of semidirect products of pseudovarieties
- Semidirect products of pseudovarieties from the universal algebraist's point of view
- UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
- On aperiodic relational morphisms.
- HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
semidirect productspseudovarieties of semigroupsdecidability of membershipcomplexity of finite semigroups
Algebraic theory of languages and automata (68Q70) Decidability of theories and sets of sentences (03B25) Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35) Products, amalgamated products, and other kinds of limits and colimits (08B25) Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35)
Cited In (53)
- The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
- Iterated periodicity over finite aperiodic semigroups
- Improved lower bounds for the complexity of finite semigroups
- On the equation \({\mathbf V}*{\mathbf G}={\mathcal E}{\mathbf V}\)
- PROFINITE METHODS IN SEMIGROUP THEORY
- Pointlike sets and separation: a personal perspective
- ON HYPERDECIDABLE PSEUDOVARIETIES OF SIMPLE SEMIGROUPS
- Towards a pseudoequational proof theory
- The geometry of profinite graphs with applications to free groups and finite monoids
- On \(\kappa\)-reducibility of pseudovarieties of the form \(V \ast D\)
- Every decidable pseudovariety of abelian groups is completely tame
- INEVITABLE GRAPHS AND PROFINITE TOPOLOGIES: SOME SOLUTIONS TO ALGORITHMIC PROBLEMS IN MONOID AND AUTOMATA THEORY, STEMMING FROM GROUP THEORY
- On the hyperdecidability of semidirect products of pseudovarieties
- COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1
- Reducibility of pointlike problems
- The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages
- On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties.
- Tameness of joins involving the pseudovariety of local semilattices.
- TAMENESS OF THE PSEUDOVARIETY LS1
- ON THE HYPERDECIDABILITY OF PSEUDOVARIETIES OF GROUPS
- UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
- The pseudoidentity problem and reducibility for completely regular semigroups
- The pseudovariety of all nilpotent groups is tame
- Some reducibility properties for pseudovarieties of the form \(DRH\)
- NORMAL FORMS FOR FREE APERIODIC SEMIGROUPS
- Dynamics of implicit operations and tameness of pseudovarieties of groups
- SOLVABLE MONOIDS WITH COMMUTING IDEMPOTENTS
- Relative Abelian kernels of some classes of transformation monoids
- Reducibility of Joins Involving Some Locally Trivial Pseudovarieties
- Pointlike sets for varieties determined by groups
- Free profinite locally idempotent and locally commutative semigroups
- Algebraic tools for the concatenation product.
- Tameness of Some Locally Trivial Pseudovarieties
- Closures of regular languages for profinite topologies.
- An automata-theoretic approach to the word problem for \(\omega\)-terms over R
- Complete κ-reducibility of pseudovarieties of the form DRH
- HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
- Irreducibility of certain pseudovarieties1
- On a problem of Brzozowski and Fich
- McCammond’s normal forms for free aperiodic semigroups revisited
- COMBINATORIAL GROUP THEORY, INVERSE MONOIDS, AUTOMATA, AND GLOBAL SEMIGROUP THEORY
- The word problem for \(\kappa \)-terms over the pseudovariety of local groups
- Recognizing pro-\(\mathrm{R}\) closures of regular languages
- PROFINITE SEMIGROUPS, VARIETIES, EXPANSIONS AND THE STRUCTURE OF RELATIVELY FREE PROFINITE SEMIGROUPS
- Profinite topologies
- An effective lower bound for group complexity of finite semigroups and automata
- Finite state automata: a geometric approach
- STABLE PAIRS
- TAMENESS OF THE PSEUDOVARIETY OF ABELIAN GROUPS
- On aperiodic relational morphisms.
- SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS
- Semidirect product with an order-computable pseudovariety and tameness.
- Tameness of pseudovariety joins involving R.
This page was built for publication: On the Decidability of Iterated Semidirect Products with Applications to Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4487602)
