Search results for "complex"
showing 10 items of 5889 documents
On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity
2005
We study the finite satisfiability problem for the guarded fragment with transitivity. We prove that in case of one transitive predicate the problem is decidable and its complexity is the same as the general satisfiability problem, i.e. 2Exptime-complete. We also show that finite models for sentences of GF with more transitive predicate letters used only in guards have essentially different properties than infinite ones.
Words and forbidden factors
2002
AbstractGiven a finite or infinite word v, we consider the set M(v) of minimal forbidden factors of v. We show that the set M(v) is of fundamental importance in determining the structure of the word v. In the case of a finite word w we consider two parameters that are related to the size of M(w): the first counts the minimal forbidden factors of w and the second gives the length of the longest minimal forbidden factor of w. We derive sharp upper and lower bounds for both parameters. We prove also that the second parameter is related to the minimal period of the word w. We are further interested to the algorithmic point of view. Indeed, we design linear time algorithm for the following two p…
Two shortest path metrics on well-formed parentheses strings
1996
We present an analysis of two transformations on well-formed parentheses strings. Using a lattice approach, the corresponding least-move distances are computable, the first in linear time and the second in quadratic time.
Exponential Codimension Growth of PI Algebras: An Exact Estimate
1999
Abstract LetAbe an associative PI-algebra over a fieldFof characteristic zero. By studying the exponential behavior of the sequence of codimensions {cn(A)} ofA, we prove thatInv(A)=limn→∞ c n ( A ) always exists and is an integer. We also give an explicit way for computing such integer: letBbe a finite dimensionalZ2-graded algebra whose Grassmann envelopeG(B) satisfies the same identities ofA; thenInv(A)=Inv(G(B))=dim C(0)+dim C(1)whereC(0)+C(1)is a suitableZ2-graded semisimple subalgebra ofB.
Asymptotics for the standard and the Capelli identities
2003
Let {c n (St k )} and {c n (C k )} be the sequences of codimensions of the T-ideals generated by the standard polynomial of degreek and by thek-th Capelli polynomial, respectively. We study the asymptotic behaviour of these two sequences over a fieldF of characteristic zero. For the standard polynomial, among other results, we show that the following asymptotic equalities hold: $$\begin{gathered} c_n \left( {St_{2k} } \right) \simeq c_n \left( {C_{k^2 + 1} } \right) \simeq c_n \left( {M_k \left( F \right)} \right), \hfill \\ c_n \left( {St_{2k + 1} } \right) \simeq c_n \left( {M_{k \times 2k} \left( F \right) \oplus M_{2k \times k} \left( F \right)} \right), \hfill \\ \end{gathered} $$ wher…
Varieties with at most quadratic growth
2010
Let V be a variety of non necessarily associative algebras over a field of characteristic zero. The growth of V is determined by the asymptotic behavior of the sequence of codimensions cn(V); n = 1; 2, … and here we study varieties of polynomial growth. Recently, for any real number a, 3 < a < 4, a variety V was constructed satisfying C1n^a < cn(V) < C2n^a; for some constants C1;C2. Motivated by this result here we try to classify all possible growth of varieties V such that cn(V) < Cn^a; with 0 < a < 2, for some constant C. We prove that if 0 < a < 1 then, for n large, cn(V) ≤ 1, whereas if V is a commutative variety and 1 < a < 2, then lim logn cn(V) = 1 o…
Quantum Query Complexity for Some Graph Problems
2004
The paper [4] by H. Buhrman and R. de Wolf contains an impressive survey of solved and open problems in quantum query complexity, including many graph problems. We use recent results by A.Ambainis [1] to prove higher lower bounds for some of these problems. Some of our new lower bounds do not close the gap between the best upper and lower bounds. We prove in these cases that it is impossible to provide a better application of Ambainis’ technique for these problems.
CHARACTERS INDUCED FROM FULLY RAMIFIED SUBGROUPS
2001
Suppose that G is a finite π-separable group, let cf(G) be the space of complex class functions of G and let Irr(G) be the set of the irreducible complex characters of G. Let K be an arbitrary Hall...
Forbidden Factors and Fragment Assembly
2001
In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word w from a given set I of substrings (fragments ) of a word w . We introduce an hypothesis involving the set of fragments I and the maximal length m(w) of the minimal forbidden factors of w . Such hypothesis allows us to reconstruct uniquely the word w from the set I in linear time. We prove also that, if w is a word randomly generated by a memoryless source with identical symbol probabilities, m(w) is logarithmic with respect to the size of w . This result shows th…
O(n 2 log n) Time On-Line Construction of Two-Dimensional Suffix Trees
2005
The two-dimensional suffix tree of an n × n square matrix A is a compacted trie that represents all square submatrices of Ai¾?[9]. For the off-line case, i.e., A is given in advance to the algorithm, it is known how to build it in optimal time, for any type of alphabet sizei¾?[9,15]. Motivated by applications in Image Compressioni¾?[18], Giancarlo and Guaianai¾?[12] considered the on-line version of the two-dimensional suffix tree and presented an On2log2n-time algorithm, which we refer to as GG. That algorithm is a non-trivial generalization of Ukkonen's on-line algorithm for standard suffix trees [19]. The main contribution in this paper is an Olog n factor improvement in the time complex…