International Journal of Algebra and Computation

We determine many of the atoms of the algebraic lattices arising in $𝔮$-theory of finite semigroups.

We denote by $\kappa$ the implicit signature that contains the multiplication and the $(\omega -1)$-power. It is proved that for any completely $\kappa$-reducible pseudovariety of groups $H$, the pseudovariety $\mathrm{DRH}$ of all finite semigroups whose regular $ℛ$-classes are groups in $H$ is completely $\kappa$-reducible as well. The converse also holds. The tools used by Almeida, Costa, and Zeitoun for proving that the pseudovariety of all finite $ℛ$-trivial monoids is completely $\kappa$-reducible are adapted for the general setting of a pseudovariety of the form $\mathrm{DRH}$.

For a given finitely generated group $G$, the type of languages that are accepted by $G$-automata is determined by the word problem of $G$ for most of the classical types of languages. We observe that the only exceptions are the families of context-sensitive and recursive languages. Thus, in general, to ensure that the language accepted by a $G$-automaton is in the same classical family of languages as the word problem of $G$, some restriction must be imposed on the $G$-automaton. We show that restricting to $G$-automata without $ϵ$-transitions is sufficient for this purpose. We then define the pullback of two $G$-automata and use this construction to study the closure properties of the family of languages accepted by $G$-automata without $ϵ$-transitions. As a further consequence, when $G=G_1\times G_2$ is the product of two groups, we give a characterization of the family of languages accepted by $G$-automata in terms of the families of languages accepted by $G_1$- and $G_2$-automata. We also give a construction of a grammar for the language accepted by an arbitrary $G$-automaton and show how to get a context-sensitive grammar when $G$ is finitely generated with a context-sensitive word problem and the $G$-automaton is without $ϵ$-transitions.

For a Lie ring $L$ over the ring of integers, we compare its lower central series ${\{{\gamma }_n(L)\}}_{n\ge 1}$ and its dimension series ${\{{\delta }_n(L)\}}_{n\ge 1}$ defined by setting ${\delta }_n(L)=L\cap {\varpi }^n(L)$, where $\varpi (L)$ is the augmentation ideal of the universal enveloping algebra of $L$. While ${\gamma }_n(L)\subseteq {\delta }_n(L)$ for all $n\ge 1$, the two series can differ. In this paper, it is proved that if $L$ is a metabelian Lie ring, then $2{\delta }_n(L)\subseteq {\gamma }_n(L)$, and $[{\delta }_n(L),L]={\gamma }_{n+1}(L)$, for all $n\ge 1$.

The complexity of the equation solvability problem is known for nilpotent groups, for not solvable groups and for some semidirect products of Abelian groups. We provide a new polynomial time algorithm for deciding the equation solvability problem over certain semidirect products, where the first factor is not necessarily Abelian. Our main idea is to represent such groups as matrix groups, and reduce the original problem to equation solvability over the underlying field. Further, we apply this new method to give a much more efficient algorithm for equation solvability over nilpotent rings than previously existed.