Search results for "Number"
showing 10 items of 3939 documents
Irredundant tandem motifs
2014
Eliminating the possible redundancy from a set of candidate motifs occurring in an input string is fundamental in many applications. The existing techniques proposed to extract irredundant motifs are not suitable when the motifs to search for are structured, i.e., they are made of two (or several) subwords that co-occur in a text string s of length n. The main effort of this work is studying and characterizing a compact class of tandem motifs, that is, pairs of substrings {m1, m2} occurring in tandem within a maximum distance of d symbols in s, where d is an integer constant given in input. To this aim, we first introduce the concept of maximality, related to four specific conditions that h…
A simple proof of the polylog counting ability of first-order logic
2007
The counting ability of weak formalisms (e.g., determining the number of 1's in a string of length N ) is of interest as a measure of their expressive power, and also resorts to complexity-theoretic motivations: the more we can count the closer we get to real computing power. The question was investigated in several papers in complexity theory and in weak arithmetic around 1985. In each case, the considered formalism (AC 0 -circuits, first-order logic, Δ 0 ) was shown to be able to count up to a polylogarithmic number. An essential part of the proofs is the construction of a 1-1 mapping from a small subset of {0, ..., N - 1} into a small initial segment. In each case the expressibility of …
A partition of characters associated to nilpotent subgroups
1999
IfG is a finite solvable group andH is a maximal nilpotent subgroup ofG containingF(G), we show that there is a canonical basisP(G|H) of the space of class functions onG vanishing off anyG-conjugate ofH which consists of characters. ViaP(G|H) it is possible to partition the irreducible characters ofG into “blocks”. These behave like Brauerp-blocks and a Fong theory for them can be developed.
On partial CAP-subgroups of finite groups
2015
Abstract Given a chief factor H / K of a finite group G, we say that a subgroup A of G avoids H / K if H ∩ A = K ∩ A ; if H A = K A , then we say that A covers H / K . If A either covers or avoids the chief factors of some given chief series of G, we say that A is a partial CAP-subgroup of G. Assume that G has a Sylow p-subgroup of order exceeding p k . If every subgroup of order p k , where k ≥ 1 , and every subgroup of order 4 (when p k = 2 and the Sylow 2-subgroups are non-abelian) are partial CAP-subgroups of G, then G is p-soluble of p-length at most 1.
A note on lower bounds of norms of averaging operators
2000
For any natural number n we obtain some examples of continuous onto maps $\phi : S\,\,\longrightarrow\, \,T$ for which Ditor's set $\Delta _\phi ^2(2, 2)$ is empty but every averaging operator for $\phi $ has norm greater or equal to 2n + 1.
STURMIAN WORDS AND AMBIGUOUS CONTEXT-FREE LANGUAGES
1990
If x is a rational number, 0<x≤1, then A(x)c is a context-free language, where A(x) is the set of factors of the infinite Sturmian words with asymptotic density of 1’s smaller than or equal to x. We also prove a “gap” theorem i.e. A(x) can never be an unambiguous co-context-free language. The “gap” theorem is established by proving that the counting generating function of A(x) is transcendental. We show some links between Sturmian words, combinatorics and number theory.
On the consequences of the standard polynomial
1998
The purpose of this paper is to shed some light on the polynomial identities of low degree for the n × n matrix algebra over a field of characteristic 0.Our main result is that we have found all the consequences of degree n + 2 of the standard polynomial have calculated the S n+2-character of the T-ideal generated by this polynomial.
Polynomial Identities of Algebras of Small Dimension
2009
It is well known that given an associative algebra or a Lie algebra A, its codimension sequence c n (A) is either polynomially bounded or grows at least as fast as 2 n . In [2] we proved that for a finite dimensional (in general nonassociative) algebra A, dim A = d, the sequence c n (A) is also polynomially bounded or c n (A) ≥ a n asymptotically, for some real number a > 1 which might be less than 2. Nevertheless, for d = 2, we may take a = 2. Here we prove that for d = 3 the same conclusion holds. We also construct a five-dimensional algebra A with c n (A) < 2 n .
Asymptotics for Graded Capelli Polynomials
2014
The finite dimensional simple superalgebras play an important role in the theory of PI-algebras in characteristic zero. The main goal of this paper is to characterize the T 2-ideal of graded identities of any such algebra by considering the growth of the corresponding supervariety. We consider the T 2-ideal Γ M+1,L+1 generated by the graded Capelli polynomials C a p M+1[Y,X] and C a p L+1[Z,X] alternanting on M+1 even variables and L+1 odd variables, respectively. We prove that the graded codimensions of a simple finite dimensional superalgebra are asymptotically equal to the graded codimensions of the T 2-ideal Γ M+1,L+1, for some fixed natural numbers M and L. In particular csupn(Γk2+l2+1…
Embeddings of Danielewski surfaces
2003
A Danielewski surface is defined by a polynomial of the form P=x nz −p(y). Define also the polynomial P ′ =x nz −r(x)p(y) where r(x) is a non-constant polynomial of degree ≤n−1 and r(0)=1. We show that, when n≥2 and deg p(y)≥2, the general fibers of P and P ′ are not isomorphic as algebraic surfaces, but that the zero fibers are isomorphic. Consequently, for every non-special Danielewski surface S, there exist non-equivalent algebraic embeddings of S in ℂ3. Using different methods, we also give non-equivalent embeddings of the surfaces xz=(y d n >−1) for an infinite sequence of integers d n . We then consider a certain algebraic action of the orthogonal group $\mathcal O(2)$ on ℂ4 which was…