A simple algorithm for checking equivalence of counting functions on free monoids

In this note we propose a new algorithm for checking whether two counting functions on a free monoid [Formula: see text] of rank [Formula: see text] are equivalent modulo a bounded function. The previously known algorithm has time complexity [Formula: see text] for all ranks [Formula: see text], but for [Formula: see text] it was estimated only to be [Formula: see text]. We apply a new approach based on the explicit basis expansion and summation of weighted rectangles, which allows us to construct a much simpler algorithm with time complexity [Formula: see text] for any [Formula: see text]. We work in the multi-tape Turing machine model with nonconstant-time arithmetic operations.