Search results for "Crete"
showing 10 items of 2495 documents
Enlarging the gap between quantum and classical query complexity of multifunctions
2013
Quantum computing aims to use quantum mechanical effects for the efficient performance of computational tasks. A popular research direction is enlarging the gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design for multivalued functions that allow to achieve a large quantum versus classical complexity separation. To compute a basic finite multifunction in a quantum model only one query is enough while classically three queries are required. Then, we present two generalizations and a modification of the original algorithm, and obtain the following complexity gaps: Q UD (M′) ≤ N versus C UD (M′) ≥ 3N,…
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.
On languages factorizing the free monoid
1996
A language X⊂A* is called factorizing if there exists a language Y⊂A* such that XY = A* This work was partially supported by ESPRIT-EBRA project ASMICS contact 6317 and project 40% MURST “Algoritmi, Modelli di Calcolo e Strutture Informative”. and the product is unambiguous. First we give a combinatorial characterization of factorizing languages. Further we prove that it is decidable whether a regular language X is factorizing and we construct an automaton recognizing the corresponding language Y. For finite languages we show that it suffices to consider words of bounded length. A complete characterization of factorizing languages with three words and explicit regular expression for the co…
The Minimum Amount of Useful Space: New Results and New Directions
2014
We consider minimal space requirements when using memory with restricted access policy (pushdown - hence giving pushdown automata (PDAs), and counter - hence giving counter automata (CAs)) in connection with two-way and realtime head motion. The main results are that: (i) loglogn is a tight space lower bound for accepting general nonregular languages on weak realtime PDAs, (ii) there exist unary nonregular languages accepted by realtime alternating CAs within weak logn space, (iii) there exist nonregular languages accepted by two-way DPADs within strong loglogn space, and, (iv) there exist unary nonregular languages accepted by two-way CAs with quantum and classical states within middle log…
On the structure of the set of equivalent norms on ℓ1 with the fixed point property
2012
Abstract Let A be the set of all equivalent norms on l 1 which satisfy the FPP. We prove that A contains rays. In fact, every renorming in l 1 which verifies condition (⁎) in Theorem 2.1 is the starting point of a (closed or open) ray composed by equivalent norms on l 1 with the FPP. The standard norm ‖ ⋅ ‖ 1 or P.K. Linʼs norm defined in Lin (2008) [12] are examples of such norms. Moreover, we study some topological properties of the set A with respect to some equivalent metrics defined on the set of all norms on l 1 equivalent to ‖ ⋅ ‖ 1 .
A Group-theoretical Finiteness Theorem
2008
We start with the universal covering space $${\*M^n}$$ of a closed n-manifold and with a tree of fundamental domains which zips it $${T\longrightarrow\*M^n}$$ . Our result is that, between T and $${\* M^n}$$ , is an intermediary object, $${T\stackrel{p} {\longrightarrow} G \stackrel{F}{\longrightarrow} \*M^n}$$ , obtained by zipping, such that each fiber of p is finite and $${T\stackrel{p}{\longrightarrow}G\stackrel{F}{\longrightarrow} \*M^n}$$ admits a section.
Ranking and unrankingk-ary trees with a 4k –4 letter alphabet
1997
Abstract The problem of the direct generation in A-order of binary trees was stated by Zaks in 1980. In 1988 Roelants van Baronaigien and Ruskey gave a solution for k-ary trees with n internal nodes using an encoding sequence of kn+1 integers between 1 and n. Vajnovszki and Pallo improved this result for binary trees in 1994 using words of length n–1 on a four letter alphabet. Recently Korsh generalized the Vajnovszki and Pallo’s generating algorithm to k-ary trees using an alphabet whose cardinality depends on k but not on n. We give in this paper ranking and unranking algorithms for k-ary trees using the Korsh’s encoding scheme.
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…