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 Mᵣ of rank r are equivalent modulo a bounded function. The previously known algorithm has time complexity O (n) for all ranks r>2, however in case r=2 it was estimated only as O (n²). Here we apply a new approach, based on explicit basis expansion and weighted rectangles summation, which allows us to construct a much simpler algorithm with time complexity O (n) for any r 2.