A simple algorithm for checking equivalence of counting functions on free monoids
<|reference_start|>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_r$ 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^2)$. 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\geq 2$.<|reference_end|>
@article{kiyashko2024a,
    title={A simple algorithm for checking equivalence of counting functions on
  free monoids},
    author={Petr Kiyashko, Alexey Talambutsa},
    journal={arXiv preprint arXiv:2407.10569},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.10569},
    primaryClass={cs.DM math.CO math.GR}
}