The quadratic-time word problem conjecture for special monoids with virtually free units

About 6 years old · traced to

Let MM be a finitely presented special monoid, generated by AA, with virtually free group of units. For inputs u,v∈A∗u,v\in A^*, write n=∣u∣+∣v∣n=|u|+|v|. Quadratic-time word problem conjecture. The word problem for MM is decidable in O(n2)O(n^2) time. Matrix multiplication has the lower bound O(n2)O(n^2), so this conjecture would make the current reduction-based bound optimal. It is motivated by the conjectured optimal quadratic-time algorithm for matrix multiplication.

References

Primary source

Carl-Fredrik Nyberg-Brodda, “On the Word Problem for Special Monoids”, arXiv:2011.09466 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.