# One-variable word equations in linear time

arXiv: https://arxiv.org/abs/1302.3481 · HTML: https://mlsanity.com/paper/1302.3481/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2013.

## Built on by (most cited first, 1 of 1)

- [On the Complexity of the Matching Problem of Regular Expressions with Backreferences](https://mlsanity.com/paper/2605.07289/) (2026)

## Abstract (arXiv)

In this paper we consider word equations with one variable (and arbitrary many appearances of it). A recent technique of recompression, which is applicable to general word equations, is shown to be suitable also in this case. While in general case it is non-deterministic, it determinises in case of one variable and the obtained running time is O(n + #X log n), where #X is the number of appearances of the variable in the equation. This matches the previously-best algorithm due to Dkabrowski and Plandowski. Then, using a couple of heuristics as well as more detailed time analysis the running time is lowered to O(n) in RAM model. Unfortunately no new properties of solutions are shown.