Search

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. [ABSTRACT FROM AUTHOR]

This paper shows an algorithm which computes the law of the Lie algebra associated with the complex Lie group of n × n upper-triangular matrices with exponential elements in their main diagonal. For its implementation two procedures are used, respectively, to define a basis of the Lie algebra and the nonzero brackets in its law with respect to that basis. These brackets constitute the final output of the algorithm, whose unique input is the matrix order n. Besides, its complexity is proved to be polynomial and some complementary computational data relative to its implementation are also shown. [ABSTRACT FROM AUTHOR]

In this paper we survey recent developments in the theory of groups acting on A-trees. We are trying to unify all significant methods and techniques, both classical and recently developed, in an attempt to present various faces of the theory and to show how these methods can be used to solve major problems about finitely presented A-free groups. Besides surveying results known up to date we draw many new corollaries concerning structural and algorithmic properties of such groups. [ABSTRACT FROM AUTHOR]

In this paper we introduce the notion of m-irreducibility that extends the standard concept of irreducibility of a numerical semigroup when the multiplicity is fixed. We analyze the structure of the set of m-irreducible numerical semigroups, we give some properties of these numerical semigroups and we present algorithms to compute the decomposition of a numerical semigroup with multiplicity m into m-irreducible numerical semigroups. [ABSTRACT FROM AUTHOR]

We introduce the peak normal form for elements of the Baumslag-Solitar groups BS(p,q). This normal form is very close to the length-lexicographical normal form, but more symmetric. Both normal forms are geodesic. This means the normal form of an element u-1v yields the shortest path between u and v in the Cayley graph. For horocyclic elements the peak normal form and the length-lexicographical normal form coincide. The main result of this paper is that we can compute the peak normal form in polynomial time if p divides q. As consequence we can compute geodesic lengths in this case. In particular, this gives a partial answer to Question 1 in [4] For arbitrary p and q it is possible to compute the peak normal form (length-lexicographical normal form resp.) also the for elements in the horocyclic subgroup and, more generally, for elements which we call hills. This approach leads to a linear time reduction of the problem of computing geodesics to the problem of computing geodesics for Britton-reduced words where the t-sequence starts with t-1 and ends with t. [ABSTRACT FROM AUTHOR]

In this paper we produce a finite algebra which generates a variety with a PSPACE-complete membership problem. We produce another finite algebra with a γ function that grows exponentially. The results are obtained via a modification of a construction of the algebra A(T) that was introduced by McKenzie in 1996. [ABSTRACT FROM AUTHOR]

We describe an algorithm for deciding whether or not a given finitely generated torsion-free nilpotent group is decomposable as the direct product of nontrivial subgroups. [ABSTRACT FROM AUTHOR]

A curve on a projective variety is called movable if it belongs to an algebraic family of curves covering the variety. We consider when the cone of movable curves can be characterized without existence statements of covering families by studying the complete intersection cone on a family of blow-ups of complex projective space, including the moduli space of stable six-pointed rational curves and the permutohedral or Losev-Manin moduli space of four-pointed rational curves. Our main result is that the movable and complete intersection cones coincide for the toric members of this family, but differ for the non-toric member, the moduli space of six-pointed rational curves. The proof is via an algorithm that applies in greater generality. We also give an example of a projective toric threefold for which these two cones differ. [ABSTRACT FROM AUTHOR]

Infinite words over a finite special confluent rewriting system R are considered and endowed with natural algebraic and topological structures. Their geometric significance is explored in the context of Gromov hyperbolic spaces. Given an endomorphism φ of the monoid generated by R, existence and uniqueness of several types of extensions of φ to infinite words (endomorphism extensions, weak endomorphism extensions, continuous extensions) are discussed. Characterization theorems and positive decidability results are proved for most cases. [ABSTRACT FROM AUTHOR]

We introduce some new types of "small" subsets of a group: sparse, k-sparse, thin, k-thin, almost thin subsets. We study the interrelations between these types and apply the obtained results to the Stone–Čech compactification βG of a discrete group G. [ABSTRACT FROM AUTHOR]

We describe irreducible representations and character formulas of the Renner monoids for reductive monoids, which generalize the Munn–Solomon representation theory of rook monoids to any Renner monoids. The type map and polytope associated with reductive monoids play a crucial role in our work. It turns out that the irreducible representations of certain parabolic subgroups of the Weyl groups determine the complete set of irreducible representations of the Renner monoids. An analogue of the Munn–Solomon formula for calculating the character of the Renner monoids, in terms of the characters of the parabolic subgroups, is shown. [ABSTRACT FROM AUTHOR]

We use the algorithms Bottomup and Topdown to study the finitistic dimensions of a class of extension algebras: the trivially twisted extensions of monomial algebras. A hybrid algorithm for determination of the finitistic dimension of the aforementioned extension is presented, and in particular, conditions for construction of such extensions that have relatively larger finitistic dimension are investigated. [ABSTRACT FROM AUTHOR]

The trace algebra Cnd over a field of characteristic 0 is generated by all traces of products of d generic n × n matrices, n, d ≥ 2. Minimal sets of generators of Cnd are known for n = 2 and 3 for any d and for n = 4 and 5 and d = 2. The explicit defining relations between the generators are found for n = 2 and any d and for n = 3, d = 2 only. Defining relations of minimal degree for n = 3 and any d are also known. The minimal degree of the defining relations of any homogeneous minimal generating set of C42 is equal to 12. Starting with the generating set given recently by Drensky and Sadikova, we have determined all relations of degree ≤ 14. For this purpose we have developed further algorithms based on representation theory of the general linear group and easy computer calculations with standard functions of Maple. [ABSTRACT FROM AUTHOR]

We discuss time complexity of the Conjugacy Problem in HNN-extensions of groups, in particular, in Miller's groups. We show that for "almost all", in some explicit sense, elements, the Conjugacy Problem is decidable in cubic time. It is worth noting that the Conjugacy Problem in a Miller group may be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group. [ABSTRACT FROM AUTHOR]

The members of the class C6 in Aschbacher's structure theorem for subgroups of the general linear group GL(d,q) are the normalizers of certain absolutely irreducible, symplectic-type r-groups, where r is a prime, d a power of r and q ≡ 1 (mod r). For a prime r > 2 and d = r, we present a constructive one-sided Monte Carlo algorithm to recognize whether or not a given subgroup G of GL(r,q) contains a normal extra-special r-group of order r3 and exponent r. In the former case the algorithm returns a homomorphism from G into SL(2,r) with kernel being the extra-special r-group times the center. [ABSTRACT FROM AUTHOR]