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.