The Termination of Nielsen Transformations Applied to Word Equations with Length Constraints
Abstract
Abstract 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.
Fields of Study & Subjects
Natural Language Processing Techniques
Publication details
- Journal / source
- Lecture notes in computer science
- Publisher
- Springer Nature Switzerland
- Pages
- 234–250
- Publication date
- 1 January 2026
- Language
- EN