Extended letterplace correspondence for nongraded noncommutative ideals and related algorithms

Let K<x_i> be the free associative algebra generated by a finite or a countable number of variables x_i . The notion of “letterplace correspondence” introduced in [R. La Scala and V. Levandovskyy, Letterplace ideals and non-commutative Grobner bases, J. Symbolic Comput. 44 (2009) 1374–1393; R. La Scala and V. Levandovskyy, Skew polynomial rings, Grobner bases and the letterplace embedding of the free associative algebra, J. Symbolic Comput. 48 (2013) 110–131] for the graded (two-sided) ideals of K<x_i> is extended in this paper also to the nongraded case. This amounts to the possibility of modelizing nongraded noncommutative presented algebras by means of a class of graded commutative algebras that are invariant under the action of the monoid N of natural numbers. For such purpose we develop the notion of saturation for the graded ideals of K<x_i, t>, where t is an extra variable and for their letterplace analogues in the commutative polynomial algebra K[x_ij , t_j ], where j ranges in N. In particular, one obtains an alternative algorithm for computing inhomogeneous noncommutative Grobner bases using just homogeneous commutative polynomials. The feasibility of the proposed methods is shown by an experimental implementation developed in the computer algebra system Maple and by using standard routines for the Buchberger algorithm contained in Singular.