A simple algorithm for checking equivalence of counting functions on free monoids
Abstract
In this paper we propose a new algorithm for checking whether two counting functions on a free monoid [Formula: see text] of rank [Formula: see text] are equivalent modulo a bounded function. The previously known algorithm has time complexity [Formula: see text] for all ranks [Formula: see text], but for [Formula: see text] it was estimated only to be [Formula: see text]. 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 [Formula: see text] for any [Formula: see text]. We work in the multi-tape Turing machine model with nonconstant-time arithmetic operations.
Fields of Study & Subjects
semigroups and automata theory
Computability
Logic
AI Algorithms
Publication details
- Journal / source
- International Journal of Algebra and Computation
- Publisher
- World Scientific Pub Co Pte Ltd
- Pages
- 1–22
- Publication date
- 31 July 2026
- Language
- EN