Efficient algorithm solves twisted group equations and palindrome length
Twisted Equations and Palindrome Length
Formal Languages and Automata Theory
Summary
Some problems in math and computer science involve solving complex equations with symmetries and constraints. The authors created a simpler method to solve a special class of these equations that include twists like reversals and inversions. Using this, they studied how to write words as products of palindromes and discovered a clear pattern describing such words. This also means they can quickly figure out the minimum number of palindromes needed to make a word, answering a long-standing question.
What this means in practice
- •For algorithm designers: Use the new algorithm to efficiently decide solvability of twisted equations with constraints in free groups.
- •For formal language engineers: Implement context-free language recognition to compute palindrome length of words in free groups in cubic time.
Authors
Volker Diekert, Anna E. Frid, Silas Natterer, Alexander Thumm
Abstract
Twisted equations in free groups are equations in which a finite group of symmetries acts on the free group by automorphisms and anti-automorphisms, such as inversion and reversal; moreover, the variables may be subject to rational constraints. Algorithms from the theory of equations in virtually free groups solve such equations in PSPACE, but they are intricate. Our main result is an elementary algorithm for quadratic twisted equations, which extends the algorithm of Comerford and Edmunds (1981) for quadratic equations in free groups to the twisted setting and to rational constraints. Besides deciding solvability in PSPACE and yielding EDT0L descriptions of solution sets, our algorithm computes, for every quadratic expression, finitely many parametric forms describing its values as freely reduced words. As an application, we study the palindrome length of elements of free groups, that is, the least number of palindromes whose product they are. Guided by the parametric forms that our algorithm computes for products of palindromes, we found, and then proved directly, a characterization of the freely reduced words of palindrome length at most $n$ in terms of patterns describing how palindromes are nested by twisted conjugations, thereby confirming a Catalan structure conjectured by the second author. Consequently, these words form a context-free language, and palindrome length is computable in cubic time as well as in LOGCFL, answering a question of Bardakov, Shpilrain, and Tolstykh (2005).