A simple algorithm for checking equivalence of counting functions on free monoids
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910028315754496 |
|---|---|
| author | Kiyashko, Petr Talambutsa, Alexey |
| author_facet | Kiyashko, Petr Talambutsa, Alexey |
| contents | 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\geq 2$. We work in the multi-tape Turing machine model with non-constant-time arithmetic operations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10569 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A simple algorithm for checking equivalence of counting functions on free monoids Kiyashko, Petr Talambutsa, Alexey Discrete Mathematics Combinatorics Group Theory 68R15 G.2.1 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\geq 2$. We work in the multi-tape Turing machine model with non-constant-time arithmetic operations. |
| title | A simple algorithm for checking equivalence of counting functions on free monoids |
| topic | Discrete Mathematics Combinatorics Group Theory 68R15 G.2.1 |
| url | https://arxiv.org/abs/2407.10569 |