Search

For some Maltsev conditions Σ it is enough to check if a finite algebra A satisfies Σ locally on subsets of bounded size in order to decide whether A satisfies Σ (globally). This local–global property is the main known source of tractability results for deciding Maltsev conditions. In this paper, we investigate the local–global property for the existence of a G-term, i.e. an n -ary term that is invariant under permuting its variables according to a permutation group G ≤ Sym (n). Our results imply in particular that all cyclic loop conditions (in the sense of Bodirsky, Starke, and Vucaj) have the local–global property (and thus can be decided in polynomial time), while symmetric terms of arity n > 2 fail to have it. [ABSTRACT FROM AUTHOR]

We characterize absorption in finite idempotent algebras by means of Jónsson absorption and cube term blockers. As an application we show that it is decidable whether a given subset is an absorbing subuniverse of an algebra given by the tables of its basic operations. [ABSTRACT FROM AUTHOR]

We study the complexity of computation in finitely generated free left, right and two-sided adequate semigroups and monoids. We present polynomial time (quadratic in the RAM model of computation) algorithms to solve the word problem and compute normal forms in each of these, and hence to test whether any given identity holds in the classes of left, right and/or two-sided adequate semigroups. [ABSTRACT FROM AUTHOR]