Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDeciding some Maltsev conditions in finite idempotent algebras
93
0
0.0
(
0
)
Added by
Alexandr Kazda
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper we investigate the computational complexity of deciding if a given finite algebraic structure satisfies a fixed (strong) Maltsev condition $Sigma$. Our goal in this paper is to show that $Sigma$-testing can be accomplished in polynomial time when the algebras tested are idempotent and the Maltsev condition $Sigma$ can be described using paths. Examples of such path conditions are having a Maltsev term, having a majority operation, and having a chain of Jonsson (or Gumm) terms of fixed length.
rate research
Read More
We show that for a fixed positive integer k one can efficiently decide if a finite algebra A admits a k-ary weak near unanimity operation by looking at the local behavior of the terms of A. We also observe that the problem of deciding if a given finite algebra has a quasi Taylor operation is solvable in polynomial time by looking, essentially, for local quasi Siggers operations.
We characterize absorption in finite idempotent algebras by means of Jonsson 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.
We study the problem of whether a given finite algebra with finitely many basic operations contains a cube term; we give both structural and algorithmic results. We show that if such an algebra has a cube term then it has a cube term of dimension at most $N$, where the number $N$ depends on the arities of basic operations of the algebra and the size of the basic set. For finite idempotent algebras we give a tight bound on $N$ that, in the special case of algebras with more than $binom{|A|}2$ basic operations, improves an earlier result of K. Kearnes and A. Szendrei. On the algorithmic side, we show that deciding the existence of cube terms is in P for idempotent algebras and in EXPTIME in general. Since an algebra contains a $k$-ary near unanimity operation if and only if it contains a $k$-dimensional cube term and generates a congruence distributive variety, our algorithm also lets us decide whether a given finite algebra has a near unanimity operation.
The aim of this note is to describe the structure of finite meadows. We will show that the class of finite meadows is the closure of the class of finite fields under finite products. As a corollary, we obtain a unique representation of minimal meadows in terms of prime fields.
In this paper, by using the Composition-Diamond lemma for non-associative algebras invented by A. I. Shirshov in 1962, we give Gr{o}bner-Shirshov bases for free Pre-Lie algebras and the universal enveloping non-associative algebra of an Akivis algebra, respectively. As applications, we show I.P. Shestakovs result that any Akivis algebra is linear and D. Segals result that the set of all good words in $X^{**}$ forms a linear basis of the free Pre-Lie algebra $PLie(X)$ generated by the set $X$. For completeness, we give the details of the proof of Shirshovs Composition-Diamond lemma for non-associative algebras.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
