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

Abstract

In this note we propose a new algorithm for checking whether two counting functions on a free monoid $M_r$ of rank $r$ are equivalent modulo a bounded function. The previously known algorithm has time complexity $O(n)$ for all ranks $r>2$, but for $r=2$ it was estimated only to be $O(n^2)$. 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 $O(n)$ for any $r\ge 2$. We work in the multi-tape Turing machine model with non-constant-time arithmetic operations.

16 pages