Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Subpower Membership Problem for Finite Algebras with Cube Terms
147
0
0.0
(
0
)
Added by
Thorsten Wissmann
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The subalgebra membership problem is the problem of deciding if a given element belongs to an algebra given by a set of generators. This is one of the best established computational problems in algebra. We consider a variant of this problem, which is motivated by recent progress in the Constraint Satisfaction Problem, and is often referred to as the Subpower Membership Problem (SMP). In the SMP we are given a set of tuples in a direct product of algebras from a fixed finite set $mathcal{K}$ of finite algebras, and are asked whether or not a given tuple belongs to the subalgebra of the direct product generated by a given set. Our main result is that the subpower membership problem SMP($mathcal{K}$) is in P if $mathcal{K}$ is a finite set of finite algebras with a cube term, provided $mathcal{K}$ is contained in a residually small variety. We also prove that for any finite set of finite algebras $mathcal{K}$ in a variety with a cube term, each one of the problems SMP($mathcal{K}$), SMP($mathbb{HS} mathcal{K}$), and finding compact representations for subpowers in $mathcal{K}$, is polynomial time reducible to any of the others, and the first two lie in NP.
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.
The theory of finite term algebras provides a natural framework to describe the semantics of functional languages. The ability to efficiently reason about term algebras is essential to automate program analysis and verification for functional or imperative programs over algebraic data types such as lists and trees. However, as the theory of finite term algebras is not finitely axiomatizable, reasoning about quantified properties over term algebras is challenging. In this paper we address full first-order reasoning about properties of programs manipulating term algebras, and describe two approaches for doing so by using first-order theorem proving. Our first method is a conservative extension of the theory of term algebras using a finite number of statements, while our second method relies on extending the superposition calculus of first-order theorem provers with additional inference rules. We implemented our work in the first-order theorem prover Vampire and evaluated it on a large number of algebraic data type benchmarks, as well as game theory constraints. Our experimental results show that our methods are able to find proofs for many hard problems previously unsolved by state-of-the-art methods. We also show that Vampire implementing our methods outperforms existing SMT solvers able to deal with algebraic data types.
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.
The main result of this paper is the decidability of the membership problem for $2times 2$ nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular $2times 2$ integer matrices $M_1,dots,M_n$ and $M$ decides whether $M$ belongs to the semigroup generated by ${M_1,dots,M_n}$. Our algorithm relies on a translation of the numerical problem on matrices into combinatorial problems on words. It also makes use of some algebraical properties of well-known subgroups of $mathrm{GL}(2,mathbb{Z})$ and various new techniques and constructions that help to limit an infinite number of possibilities by reducing them to the membership problem for regular languages.
When two spatially separated parties make measurements on an unknown entangled quantum state, what correlations can they achieve? How difficult is it to determine whether a given correlation is a quantum correlation? These questions are central to problems in quantum communication and computation. Previous work has shown that the general membership problem for quantum correlations is computationally undecidable. In the current work we show something stronger: there is a family of constant-sized correlations -- that is, correlations for which the number of measurements and number of measurement outcomes are fixed -- such that solving the quantum membership problem for this family is computationally impossible. Thus, the undecidability that arises in understanding Bell experiments is not dependent on varying the number of measurements in the experiment. This places strong constraints on the types of descriptions that can be given for quantum correlation sets. Our proof is based on a combination of techniques from quantum self-testing and from undecidability results of the third author for linear system nonlocal games.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
