Search results for " Algebra"
showing 10 items of 2082 documents
Periodic Groups Covered by Transitive Subgroups of Finitary Permutations or by Irreducible Subgroups of Finitary Transformations
1999
Let X be either the class of all transitive groups of finitary permutations, or the class of all periodic irreducible finitary linear groups. We show that almost primitive X-groups are countably recognizable, while totally imprimitive X-groups are in general not countably recognizable. In addition we derive a structure theorem for groups all of whose countable subsets are contained in totally imprimitive X-subgroups. It turns out that totally imprimitive p-groups in the class X are countably recognizable.
Querying the Guarded Fragment with Transitivity
2016
We study the problem of answering a union of Boolean conjunctive queries q against a database Δ, and a logical theory φ which falls in the guarded fragment with transitive guards (GF + TG). We trace the frontier between decidability and undecidability of the problem under consideration. Surprisingly, we show that query answering under GF2 + TG, i.e., the two-variable fragment of GF + TG, is already undecidable (even without equality), whereas its monadic fragment is decidable; in fact, it is 2exptime-complete in combined complexity and coNP-complete in data complexity. We also show that for a restricted class of queries, query answering under GF+TG is decidable. © 2013 Springer-Verlag.
Varieties of Codes and Kraft Inequality
2005
Decipherability conditions for codes are investigated by using the approach of Guzman, who introduced in [7] the notion of variety of codes and established a connection between classes of codes and varieties of monoids. The class of Uniquely Decipherable (UD) codes is a special case of variety of codes, corresponding to the variety of all monoids. It is well known that the Kraft inequality is a necessary condition for UD codes, but it is not sufficient, in the sense that there exist codes that are not UD and that satisfy the Kraft inequality. The main result of the present paper states that, given a variety $\mathcal{V}$ of codes, if all the elements of $\mathcal{V}$ satisfy the Kraft inequ…
Thin bases of order h
2003
Abstract A subset A⊆ N 0 is called a basis of order h if every positive integer can be represented as a sum of h members of A . Thin bases of order h will be constructed in this paper, for each h ⩾2, where the value of lim sup A(n)/ n h is smaller than that of thin bases known so far. In the most important case h =2 it is shown that for the considered class of bases (which generalizes an ansatz of Stohr) the result is best possible up to an e >0.
On positive P
2002
Continuing a line of research opened up by Grigni and Sipser (1992) and further pursued by Stewart (1994), we show that a wide variety of equivalent characterizations of P still remain equivalent when restricted to be positive. All these restrictions thus define the same class posP, a proper subclass of monP, the class of monotone problems in P. We also exhibit complete problems for posP under very weak reductions.
Subvarieties of the Varieties Generated by the SuperalgebraM1, 1(E) orM2(𝒦)
2003
Abstract Let 𝒦 be a field of characteristic zero, and let us consider the matrix algebra M 2(𝒦) endowed with the ℤ2-grading (𝒦e 11 ⊕ 𝒦e 22) ⊕ (𝒦e 12 ⊕ 𝒦e 21). We define two superalgebras, ℛ p and 𝒮 q , where p and q are positive integers. We show that if 𝒰 is a proper subvariety of the variety generated by the superalgebra M 2(𝒦), then the even-proper part of the T 2-ideal of graded polynomial identities of 𝒰 asymptotically coincides with the even-proper part of the graded polynomial identities of the variety generated by the superalgebra ℛ p ⊕ 𝒮 q . This description also affords an even-asymptotic desc…
Basis-set completeness profiles in two dimensions
2002
A two-electron basis-set completeness profile is proposed by analogy with the one-electron profile introduced by D. P. Chong (Can J Chem 1995, 73, 79). It is defined as Y(alpha, beta) = sigmam sigman (Galpha(1)Gbeta(2)/(1/r12)/ psim(1)psin(2)) (psim(1)psin(2)/r12/Galpha(1)Gp(2)) and motivated by the expression for the basis-set truncation correction that occurs in the framework of explicitly correlated methods (Galpha is a scanning Gaussian-type orbital of exponent alpha and [psim] is the orthonormalized one-electron basis under study). The two-electron basis-set profiles provide a visual assessment of the suitability of basis sets to describe electron-correlation effects. Furthermore, they…
On symmetric nonlocal games
2013
Abstract Nonlocal games are used to display differences between the classical and quantum world. In this paper, we study symmetric XOR games, which form an important subset of nonlocal games. We give simple methods for calculating the classical and the quantum values for symmetric XOR games with one-bit input per player. We illustrate those methods with two examples. One example is an N -player game (due to Ardehali (1992) [3] ) that provides the maximum quantum-over-classical advantage. The second example comes from generalization of CHSH game by letting the referee to choose arbitrary symmetric distribution of players’ inputs.
Defining relations of minimal degree of the trace algebra of 3×3 matrices
2008
Abstract The trace algebra C n d over a field of characteristic 0 is generated by all traces of products of d generic n × n matrices, n , d ⩾ 2 . Minimal sets of generators of C n d are known for n = 2 and n = 3 for any d as well as for n = 4 and n = 5 and d = 2 . The defining relations between the generators are found for n = 2 and any d and for n = 3 , d = 2 only. Starting with the generating set of C 3 d given by Abeasis and Pittaluga in 1989, we have shown that the minimal degree of the set of defining relations of C 3 d is equal to 7 for any d ⩾ 3 . We have determined all relations of minimal degree. For d = 3 we have also found the defining relations of degree 8. The proofs are based …
Complete, Exact and Efficient Implementation for Computing the Adjacency Graph of an Arrangement of Quadrics
2007
The original publication is available at www.springerlink.com ; ISBN 978-3-540-75519-7 ; ISSN 0302-9743 (Print) 1611-3349 (Online); International audience; We present a complete, exact and efficient implementation to compute the adjacency graph of an arrangement of quadrics, \ie surfaces of algebraic degree~2. This is a major step towards the computation of the full 3D arrangement. We enhanced an implementation for an exact parameterization of the intersection curves of two quadrics, such that we can compute the exact parameter value for intersection points and from that the adjacency graph of the arrangement. Our implementation is {\em complete} in the sense that it can handle all kinds of…