Search

In this paper, we deal with the problem of computing the sum of the [Formula: see text]th powers of all the elements of the matrix ring [Formula: see text] with [Formula: see text] and [Formula: see text] a finite commutative ring. We completely solve the problem in the case [Formula: see text] and give some results that compute the value of this sum if [Formula: see text] is an arbitrary finite commutative ring for many values of [Formula: see text] and [Formula: see text]. Finally, based on computational evidence and using some technical results proved in this paper, we conjecture that the sum of the [Formula: see text]th powers of all the elements of the matrix ring [Formula: see text] is always [Formula: see text] unless [Formula: see text], [Formula: see text], [Formula: see text] and the only element [Formula: see text] such that [Formula: see text] is idempotent, in which case the sum is [Formula: see text].

The growth of a finitely generated group is an important geometric invariant which has been studied for decades. It can be either polynomial, for a well-understood class of groups, or exponential, for most groups studied by geometers, or intermediate, that is between polynomial and exponential. Despite recent spectacular progresses, the class of groups with intermediate growth remains largely mysterious. Many examples of such groups are constructed using Mealy automata. The aim of this paper is to give an algorithmic procedure to study the growth of such automaton groups, and more precisely to provide numerical upper bounds on their exponents. Our functions retrieve known optimal bounds on the famous first Grigorchuk group. They also improve known upper bounds on other automaton groups and permitted us to discover several new examples of automaton groups of intermediate growth. All the algorithms described are implemented in GAP, a language dedicated to computational group theory.

L systems generalise context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L that are strictly contained in the class of indexed languages. In this paper we show that many of the languages naturally appearing in group theory, and that were known to be indexed or context-sensitive, are in fact ET0L and in many cases EDT0L. For instance, the language of primitives in the free group on two generators, the Bridson-Gilman normal forms for the fundamental groups of 3-manifolds or orbifolds, and the co-word problem of Grigorchuk's group can be generated by L systems. To complement the result on primitives in free groups, we show that the language of primitives, and primitive sets, in free groups of rank higher than two is context-sensitive. We also show the existence of EDT0L and ET0L languages of intermediate growth., Revised following referees suggestions. 21 pages, 2 figures

We study some properties of the generalized local cohomology modules [Formula: see text] of [Formula: see text] with respect to a pair of ideals [Formula: see text] in Serre subcategories. Some results concerning to [Formula: see text]-cofinite modules are also given in this paper.

We show that, given an equation over a finitely generated free group, the set of all solutions in reduced words forms an effectively constructible EDT0L language. In particular, the set of all solutions in reduced words is an indexed language in the sense of Aho. The language characterization we give, as well as further questions about the existence or finiteness of solutions, follow from our explicit construction of a finite directed graph which encodes all the solutions. Our result incorporates the recently invented recompression technique of Je\.z, and a new way to integrate solutions of linear Diophantine equations into the process. As a byproduct of our techniques, we improve the complexity from quadratic nondeterministic space in previous works to $\mathsf{NSPACE}(n\log n)$ here., Comment: 38 pages, 3 figures. A conference version of this paper was presented at ICALP 2015, Kyoto (Japan), July 4-10, 2015, see http://arxiv.org/abs/1502.03426

Let [Formula: see text] be a nondegenerate projective integral curve of degree [Formula: see text] which is not linearly normal. In this paper, we continues the study begun in [E. Park, Projective curves of degree=codimension+2, Math. Z. 256 (2007) 685–697] for the minimal free resolution of [Formula: see text]. It is well-known that [Formula: see text] is an isomorphic projection of a rational normal curve [Formula: see text] from a point [Formula: see text]. Our main result is about how the graded Betti numbers of [Formula: see text] are determined by the rank of [Formula: see text] with respect to [Formula: see text], which is a measure of the relative location of [Formula: see text] from [Formula: see text].

Given a collection [Formula: see text] of k2 commutative polynomials in 2k2 variables, the objective is to find a condensed representation for these polynomials in terms of a single non-commutative (nc) polynomial p(X, Y) in two k × k matrix variables X and Y. In this paper, we develop algorithms that will generically determine whether the given family [Formula: see text] has a nc representation and will produce such a representation if it exists. In particular, we determine an open, dense subset of the space of nc polynomials in two variables that satisfies the following property: if a family [Formula: see text] of polynomials admits a nc representation in this subset, then our algorithms will determine this representation.

The main purpose of this paper is to improve the bound of complexity of the well-known algorithms on polynomial ideals having complexities polynomial in dn, where d is the maximal degree of input polynomials and n is the number of variables. Instead of this bound, we present the more accurate bound max {S, Dn} where S is the size of the input polynomials in dense representation, and D is the arithmetic mean value of the degrees of input polynomials.

This paper is concerned with the structure of semigroups of implicit operations on various subpseudovarieties V of [Formula: see text] ∩ [Formula: see text], where [Formula: see text] and [Formula: see text] are the pseudovarieties of all semigroups S in which each regular [Formula: see text] -class is, respectively, a rectangular group and a group, and where [Formula: see text] is the pseudovariety of semigroups locally in [Formula: see text] As an application, we give a characterization of the variety of languages recognized by semigroups in V and derive some join decompositions of pseudovarieties.

J. Rhodes asked during the Chico Conference in 1986 for the calculation of joins of semigroup pseudovarieties. This paper proves that the join J∨H of the pseudovariety J of [Formula: see text]-trivial semigroups and of any 2-strongly decidable pseudovariety V of of completely regular semigroups is decidable. This problem was proposed by the first author for V=G, the pseudovariety of finite groups.

In this paper we prove that, if V is a kappa-tame pseudovariety which satisfies the pseudoidentity xy^{\omega+1}z=xyz, then the pseudovariety join LSl v V is also kappa-tame. Here, LSl denotes the pseudovariety of local semilattices and kappa denotes the implicit signature consisting of the multiplication and the (omega-1)-power. As a consequence, we deduce that LSl v V is decidable. In particular the joins LSl v Ab, LSl v G, LSl v OCR and LSl v CR are decidable., European Science Foundation (ESF) through the programme ``Automata: from Mathematics to Applications (AutoMathA)'', Fundação para a Ciência e a Tecnologia (FCT) under the project PEst-C/MAT/UI0013/2011., FCT through the project PTDC/MAT/65481/2006, which was partly funded by the European Community Fund FEDER, European Regional Development Fund, through the programme COMPETE