?
A simple algorithm for checking equivalence of counting functions on free monoids
International Journal of Algebra and Computation. 2026. P. 1–22.
Talambutsa A., Petr Kiyashko
In press
In this paper we propose a new algorithm for checking whether two counting functions on a free monoid Mr 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≥2. We work in the multi-tape Turing machine model with nonconstant-time arithmetic operations.