For a word w in an alphabet Γ, the alternation word digraph Alt (w), a certain directed acyclic
graph associated with w, is presented as a means to analyze the free spectrum of the …

We establish necessary and sufficient conditions for a semigroup identity to hold in the
monoid of n× n upper triangular tropical matrices, in terms of equivalence of certain tropical …

In a paper published in J. ACM in 1990, Tobias Nipkow asserted that the problem of
deciding whether or not an equation over a nontrivial functionally complete algebra has a …

We provide polynomial time algorithms for deciding equation solvability and identity
checking over groups that are semidirect products of two finite Abelian groups. Our main …

It is proved that the equation solvability problem can be solved in polynomial time for finite
nilpotent rings. Ramsey's theorem is employed in the proof. Then, using the same technique …

Complexity issues of checking identities in finite monoids Page 1 Semigroup Forum (2009) 79:
435–444 DOI 10.1007/s00233-009-9180-y RESEARCH ARTICLE Complexity issues of …

It is observed in this paper that the complexities of the equivalence and the equation
solvability problems are not determined by the clone of the algebra. In particular, we prove …

Kauffman monoids K _n and Jones monoids J _n, n= 2, 3,\dots, are two families of monoids
relevant in knot theory. We prove a somewhat counterintuitive result that the Kauffman …

We provide a polynomial time algorithm for deciding the equation solvability problem over
finite groups that are semidirect products of ap-group and an Abelian group. As a …

The extended equivalence and equation solvability problems for groups Page 1 Discrete
Mathematics and Theoretical Computer Science DMTCS vol. 13:4, 2011, 23–32 The extended …