International Journal of Algebra and Computation

Let K 〈x,y〉 be the free associative algebra of rank 2 over an algebraically closed constructive field of any characteristic. We present an algorithm which decides whether or not two elements in K 〈x,y〉 are equivalent under an automorphism of K 〈x,y〉. A modification of our algorithm solves the problem whether or not an element in K 〈x,y〉 is a semiinvariant of a nontrivial automorphism. In particular, it determines whether or not the element has a nontrivial stabilizer in Aut K 〈x,y〉.

An algorithm for equivalence of polynomials under automorphisms of ℂ[x,y] was presented by Wightwick. Another, much simpler algorithm for automorphic equivalence of two polynomials in K[x,y] for any algebraically closed constructive field K was given by Makar-Limanov, Shpilrain, and Yu. In our approach we combine an idea of the latter three authors with an idea from the unpublished thesis of Lane used to describe automorphisms which stabilize elements of K 〈x,y〉. This also allows us to give a simple proof of the corresponding result for K[x,y] obtained by Makar-Limanov, Shpilrain, and Yu.

We investigate Büchi automata with weights for the transitions. Assuming that the weights are taken in a suitable ordered semiring, we show how to define the behaviors of these automata on infinite words. Our main result shows that the formal power series arising in this way are precisely the ones which can be constructed using ω-rational operations. This extends the classical Kleene–Schützenberger result for weighted finite automata to the case of infinite words and generalizes Büchi's theorem on languages of infinite words. We also derive versions of our main result for non-complete semirings and for other automata models.

Let z = (z₁, z₂,…, z_n) be noncommutative free variables and t a formal parameter which commutes with z. Let k be any unital integral domain of any characteristic and F_t(z) = z - H_t(z) with H_t(z) ∈ k[[t]]〈〈z〉〉^×n and the order o(H_t(z))≥ 2. Note that F_t(z) can be viewed as a deformation of the formal map F(z):= z - H_t=1(z) when it makes sense (for example, when H_t(z) ∈ k[t]〈〈z〉〉^×n). The inverse map G_t(z) of F_t(z) can always be written as G_t(z) = z+M_t(z) with M_t(z) ∈ k[[t]]〈〈z〉〉^×n and o(M_t(z)) ≥ 2. In this paper, we first derive the PDEs satisfied by M_t(z) and u(F_t), u(G_t) ∈ k[[t]]〈〈z〉〉 with u(z) ∈ k〈〈z〉〉 in the general case as well as in the special case when H_t(z) = tH(z) for some H(z) ∈ k〈〈z〉〉^×n. We also show that the elements above are actually characterized by certain Cauchy problems of these PDEs. Secondly, we apply the derived PDEs to prove a recurrent inversion formula for formal maps in noncommutative variables. Finally, for the case char. k = 0, we derive an expansion inversion formula by the planar binary rooted trees.

We say the endomorphism problem is solvable for an element W in a free group F if it can be decided effectively whether, given U in F, there is an endomorphism ϕ of F sending W to U. This work analyzes an approach due to Edmunds and improved by Sims. Here we prove that the approach provides an efficient algorithm for solving the endomorphism problem when W is a two-generator word. We show that when W is a two-generator word this algorithm solves the problem in time polynomial in the length of U.

This result gives a polynomial-time algorithm for solving, in free groups, two-variable equations in which all the variables occur on one side of the equality and all the constants on the other side.

In this article we show that every group with a finite presentation satisfying one or both of the small cancellation conditions C′(1/6) and C′(1/4) - T(4) has the property that the set of all geodesics (over the same generating set) is a star-free regular language. Star-free regularity of the geodesic set is shown to be dependent on the generating set chosen, even for free groups. We also show that the class of groups whose geodesic sets are star-free with respect to some generating set is closed under taking graph (and hence free and direct) products, and includes all virtually abelian groups.

We give an infinite family of finite dualizable unary algebras that are not fully κ-dualizable, for all cardinals κ.

Rotation distance measures the difference in shape between binary trees of the same size by counting the minimum number of rotations needed to transform one tree to the other. We describe several types of rotation distance where restrictions are put on the locations where rotations are permitted, and provide upper bounds on distances between trees with a fixed number of nodes with respect to several families of these restrictions. These bounds are sharp in a certain asymptotic sense and are obtained by relating each restricted rotation distance to the word length of elements of Thompson's group F with respect to different generating sets, including both finite and infinite generating sets.

We construct a finitely presented group G with non-quadratic Dehn function f majorizable by a quadratic function on arbitrary long intervals.

We give an example of a finitely presented group G with two non-π₁-equivalent asymptotic cones.