Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDeciding the existence of quasi weak near unanimity terms in finite algebras
86
0
0.0
(
0
)
Added by
Alexandr Kazda
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Alexandr Kazda
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation $m$ that satisfies the minority equations $m(y,x,x) approx m(x,y,x) approx m(x,x,y) approx y$. We show that a common polynomial-time approach to testing for this type of condition will not work in this case and that this decision problem lies in the class NP.
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.
For some Maltsev conditions $Sigma$ it is enough to check if a finite algebra $mathbf A$ satisfies $Sigma$ locally on subsets of bounded size, in order to decide, whether $mathbf A$ satisfies $Sigma$ (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 leq$ 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
