“The Termination of Nielsen Transformations Applied to Word Equations with Length Constraints” by Benjamin Przybocki and Clark W. Barrett. In Automated Reasoning - 13th International Joint Conference, IJCAR 2026, Lisbon, Portugal, July 26-29, 2026, Proceedings, Part II, (Armin Biere, Carsten Lutz, and Sara Negri, eds.), 2026, pp. 234-250. Lisbon, Portugal.
Nielsen transformations form the basis of a simple and widely used procedure for solving word equations. We make progress on the problem of determining when this procedure terminates in the presence of length constraints. To do this, we introduce extended word equations, a mathematical model of a word equation with partial information about length constraints. We then define extended Nielsen transformations, which adapt Nielsen transformations to the setting of extended word equations. We provide a partial characterization of when repeatedly applying extended Nielsen transformations to an extended word equation is guaranteed to terminate.
BibTeX entry:
@inproceedings{PB26,
author = {Benjamin Przybocki and Clark W. Barrett},
editor = {Armin Biere and Carsten Lutz and Sara Negri},
title = {The Termination of Nielsen Transformations Applied to Word
Equations with Length Constraints},
booktitle = {Automated Reasoning - 13th International Joint Conference,
{IJCAR} 2026, Lisbon, Portugal, July 26-29, 2026, Proceedings,
Part {II}},
series = {Lecture Notes in Computer Science},
volume = {16689},
pages = {234--250},
publisher = {Springer},
year = {2026},
doi = {10.1007/978-3-032-32592-1_14},
note = {Lisbon, Portugal},
url = {https://doi.org/10.1007/978-3-032-32592-1_14}
}
(This webpage was created with bibtex2web.)