Search results for "COD"
showing 10 items of 2985 documents
On the size of transducers for bidirectional decoding of prefix codes
2012
In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [ IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this method is defined. It is proved also that this transducer is minimal. Here we consider the number of states of such a transducer, related to some features of the considered prefix code X . We find some bounds of such a number of states in relation wi…
Loop-free Gray code algorithm for the e-restricted growth functions
2011
The subject of Gray codes algorithms for the set partitions of {1,2,...,n} had been covered in several works. The first Gray code for that set was introduced by Knuth (1975) [5], later, Ruskey presented a modified version of [email protected]?s algorithm with distance two, Ehrlich (1973) [3] introduced a loop-free algorithm for the set of partitions of {1,2,...,n}, Ruskey and Savage (1994) [9] generalized [email protected]?s results and give two Gray codes for the set of partitions of {1,2,...,n}, and recently, Mansour et al. (2008) [7] gave another Gray code and loop-free generating algorithm for that set by adopting plane tree techniques. In this paper, we introduce the set of e-restricte…
A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay
2012
In this paper we generalize an encoding method due to Girod (cf. [6]) using prefix codes, that allows a bidirectional decoding of the encoded messages. In particular we generalize it to any finite alphabet A, to any operation defined on A, to any code with finite deciphering delay and to any key x ∈ A+ , on a length depending on the deciphering delay. We moreover define, as in [4], a deterministic transducer for such generalized method. We prove that, fixed a code X ∈ A* with finite deciphering delay and a key x ∈ A *, the transducers associated to different operations are isomorphic as unlabelled graphs. We also prove that, for a fixed code X with finite deciphering delay, transducers asso…
Star-polynomial identities: computing the exponential growth of the codimensions
2017
Abstract Can one compute the exponential rate of growth of the ⁎-codimensions of a PI-algebra with involution ⁎ over a field of characteristic zero? It was shown in [2] that any such algebra A has the same ⁎-identities as the Grassmann envelope of a finite dimensional superalgebra with superinvolution B. Here, by exploiting this result we are able to provide an exact estimate of the exponential rate of growth e x p ⁎ ( A ) of any PI-algebra A with involution. It turns out that e x p ⁎ ( A ) is an integer and, in case the base field is algebraically closed, it coincides with the dimension of an admissible subalgebra of maximal dimension of B.
Polynomial codimension growth of algebras with involutions and superinvolutions
2017
Abstract Let A be an associative algebra over a field F of characteristic zero endowed with a graded involution or a superinvolution ⁎ and let c n ⁎ ( A ) be its sequence of ⁎-codimensions. In [4] , [12] it was proved that if A is finite dimensional such sequence is polynomially bounded if and only if A generates a variety not containing a finite number of ⁎-algebras: the group algebra of Z 2 and a 4-dimensional subalgebra of the 4 × 4 upper triangular matrices with suitable graded involutions or superinvolutions. In this paper we focus our attention on such algebras since they are the only finite dimensional ⁎-algebras, up to T 2 ⁎ -equivalence, generating varieties of almost polynomial gr…
Codimension growth and minimal superalgebras
2003
A celebrated theorem of Kemer (1978) states that any algebra satisfying a polynomial identity over a field of characteristic zero is PI-equivalent to the Grassmann envelope G(A) of a finite dimensional superalgebra A. In this paper, by exploiting the basic properties of the exponent of a PI-algebra proved by Giambruno and Zaicev (1999), we define and classify the minimal superalgebras of a given exponent over a field of characteristic zero. In particular we prove that these algebras can be realized as block-triangular matrix algebras over the base field. The importance of such algebras is readily proved: A is a minimal superalgebra if and only if the ideal of identities of G(A) is a product…
Algebras with involution with linear codimension growth
2006
AbstractWe study the ∗-varieties of associative algebras with involution over a field of characteristic zero which are generated by a finite-dimensional algebra. In this setting we give a list of algebras classifying all such ∗-varieties whose sequence of ∗-codimensions is linearly bounded. Moreover, we exhibit a finite list of algebras to be excluded from the ∗-varieties with such property. As a consequence, we find all possible linearly bounded ∗-codimension sequences.
Finite-dimensional non-associative algebras and codimension growth
2011
AbstractLet A be a (non-necessarily associative) finite-dimensional algebra over a field of characteristic zero. A quantitative estimate of the polynomial identities satisfied by A is achieved through the study of the asymptotics of the sequence of codimensions of A. It is well known that for such an algebra this sequence is exponentially bounded.Here we capture the exponential rate of growth of the sequence of codimensions for several classes of algebras including simple algebras with a special non-degenerate form, finite-dimensional Jordan or alternative algebras and many more. In all cases such rate of growth is integer and is explicitly related to the dimension of a subalgebra of A. One…
Varieties of almost polynomial growth: classifying their subvarieties
2007
Let G be the infinite dimensional Grassmann algebra over a field F of characteristic zero and UT2 the algebra of 2 x 2 upper triangular matrices over F. The relevance of these algebras in PI-theory relies on the fact that they generate the only two varieties of almost polynomial growth, i.e., they grow exponentially but any proper subvariety grows polynomially. In this paper we completely classify, up to PI-equivalence, the associative algebras A such that A is an element of Var(G) or A is an element of Var(UT2).
Matrix algebras of polynomial codimension growth
2007
We study associative algebras with unity of polynomial codimension growth. For any fixed degree $k$ we construct associative algebras whose codimension sequence has the largest and the smallest possible polynomial growth of degree $k$. We also explicitly describe the identities and the exponential generating functions of these algebras.