On the Decidability of Iterated Semidirect Products with Applications to Complexity
From MaRDI portal
(Redirected from Publication:4487602)
complexity of finite semigroupsdecidability of membershippseudovarieties of semigroupssemidirect products
Decidability of theories and sets of sentences (03B25) Undecidability and degrees of sets of sentences (03D35) Products, amalgamated products, and other kinds of limits and colimits (08B25) Free semigroups, generators and relations, word problems (20M05) Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35) Algebraic theory of languages and automata (68Q70)
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
Cited in
(55)- On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties.
- Towards a pseudoequational proof theory
- The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages
- Algebraic tools for the concatenation product.
- The word problem for -terms over the pseudovariety of local groups
- Every decidable pseudovariety of abelian groups is completely tame
- Profinite topologies
- Recognizing pro-\(\mathrm{R}\) closures of regular languages
- Reducibility of pointlike problems
- Iterated periodicity over finite aperiodic semigroups
- On aperiodic relational morphisms.
- Improved lower bounds for the complexity of finite semigroups
- Pointlike sets for varieties determined by groups
- On a problem of Brzozowski and Fich
- Finite state automata: a geometric approach
- The pseudoidentity problem and reducibility for completely regular semigroups
- Dynamics of implicit operations and tameness of pseudovarieties of groups
- McCammond’s normal forms for free aperiodic semigroups revisited
- On -reducibility of pseudovarieties of the form V D
- Complete κ-reducibility of pseudovarieties of the form DRH
- Reducibility of Joins Involving Some Locally Trivial Pseudovarieties
- STABLE PAIRS
- COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1
- On the hyperdecidability of semidirect products of pseudovarieties
- Irreducibility of certain pseudovarieties1
- The geometry of profinite graphs with applications to free groups and finite monoids
- HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
- UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
- Some reducibility properties for pseudovarieties of the form DRH
- TAMENESS OF THE PSEUDOVARIETY LS1
- Closures of regular languages for profinite topologies.
- 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
- Tameness of Some Locally Trivial Pseudovarieties
- Tameness of joins involving the pseudovariety of local semilattices.
- The pseudovariety of all nilpotent groups is tame
- SOLVABLE MONOIDS WITH COMMUTING IDEMPOTENTS
- An effective lower bound for group complexity of finite semigroups and automata
- TAMENESS OF THE PSEUDOVARIETY OF ABELIAN GROUPS
- Relative Abelian kernels of some classes of transformation monoids
- SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS
- 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 omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
- Pseudovarieties of semigroups
- A purely algebraic proof of the omega-reducibility of pseudovarieties representing low half levels of concatenation hierarchies
- Tameness of pseudovariety joins involving R.
- Pointlike sets and separation: a personal perspective
- An automata-theoretic approach to the word problem for \(\omega\)-terms over 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)
