On Solving String Equations via Powers and Parikh Images
Clemens Eisenhofer (✉), Theodor Seiser, Nikolaj Bjørner, Laura Kovács · 2026
Read On Solving String Equations via Powers and Parikh Images by Clemens Eisenhofer (✉), Theodor Seiser, Nikolaj Bjørner, Laura Kovács (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05273.txt.
Introduction
Clemens Eisenhofer and team offer a new way to solve string equations, building on Nielsen changes as extensions of them. Three ways combine in the approach: a power operator for strings, generalizations of Parikh images, and equality decomposition. As one these methods solve complex string equations, including the less commonly encountered SMT inputs over strings.
Catalog record
| CREATOR | Clemens Eisenhofer (✉), Theodor Seiser, Nikolaj Bjørner, Laura Kovács |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48583 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.05273
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Solving String Equations via Powers and Parikh Images Clemens Eisenhofer (✉), Theodor Seiser, Nikolaj Bjørner, Laura Kovács Abstract We present a new approach for solving string equations as extensions of Nielsen transformations. Key to our work are the combination of three techniques: a power operator for strings; generalisations of Parikh images; and equality decomposition. Using these methods allows us to solve complex string equations, including less commonly encountered SMT inputs over strings. 1 Introduction String solving is used in a wide range of applications, including formal verification [ 1 , 9 ] , security analysis [ 15 , 16 , 33 , 34 ] , and automated reasoning [ 2 , 18 ] . Modern Satisfiability Modulo Theories (SMT) solvers [ 5 ] , such as Z3 [ 14 ] , cvc5 [ 3 ] , or Princess [ 29 ] , support string constraints via specialised solving techniques for handling length constraints [ 26 ] , regular expressions [ 7 , 30 ] , containment predicates [ 27 ] , and many others. However, solving string (word) equations that involve long repeated subsequences or contain mutually dependent string variables remains very challenging for state-of-the-art solvers [ 1 , 9 , 10 , 12 , 21 , 24 , 14 , 33 ] . Example 1 (Motivating Example) Consider the conjunction of the following two string equations: \displaystyle x_{3}x_{3}x_{4}bx_{5}b \displaystyle\simeq \displaystyle x_{5}x_{5}x_{5}x_{5}x_{4}bb, ( E_{1} ) \displaystyle x_{1}x_{1}acx_{2}x_{4}x_{2}x_{5}x_{3}bax_{5}x_{3}x_{4}x_{3} \displaystyle\simeq \displaystyle x_{2}x_{2}abcx_{1}x_{1}x_{3}x_{3}x_{3}x_{4}x_{4}ax_{4} ( E_{2} ) where \simeq denotes (first-order) equality, x_{1},x_{2},x_{3},x_{4},x_{5} are string variables and a,b,c are constant characters. Solving such equations requires reasoning about string variables depending on themselves or mutually on each other needs, which is mostly out of scope of current techniques. Our work addresses challenges similar to solving equations ( E 1 )–( E 2 ). Our approach uses rewriting and generating rules over string equations (Table 1 ) as Nielsen transformations (Section 3 ) over Nielsen graphs [ 18 , 23 , 26 ] . We extend Nielsen transformation rules with: Equality decomposition – to decompose string equations during reasoning into subequations. Using equality decomposition greatly increases the applicability of string power reasoning and Parikh images. Explicit power representation – to solve string equations in which string variables depend on themselves. Furthermore, it allows us to compactly reason on long, but repetitive, strings (Section 5 ). Generalized Parikh images – to detect unsatisfiability when both Nielsen rules and string power reasoning fail (Section 6 ). We adjust generalised forms of Parikh images [ 25 ] to string solving. We implemented our framework as a prototype called ZIPT using the user-propagation framework [ 8 ] of the SMT solver Z3 [ 14 ] . Our experiments demonstrate the practical potential of our method (Section 7 ) on SMT-LIB2 benchmarks [ 4 ] containing equations only. 2 Preliminaries Strings. For our purposes, we will use an extended definition of a string term. Definition 1 (Token & String Terms) We fix a set \mathcal{K} of tokens and denote by \mathcal{T} the set of string terms. A string term u\in\mathcal{T} is a finite sequence of tokens t\in\mathcal{K} and we distinguish between • concrete character tokens, denoted as a,b,c,d , whose set is denoted by \Sigma ; • symbolic characters tokens, written as o , whose set is \mathcal{V}_{C} . • (string) variable tokens, denoted as x,y,z , whose set is \mathcal{V}_{S} ; • power tokens of the form u^{m} , where u\in\mathcal{T} does not contain string variables and m is an arbitrary integer term potentially containing integer variables. We call u the base and m the exponent of a power token. Our token notation might use indices, and we write @\in\Sigma\cup\mathcal{V}_{C} to denote (concrete or symbolic) character tokens and t\in\mathcal{T} for a token of any kind. The sets \Sigma , \mathcal{V}_{C} , and \mathcal{V}_{S} are mutually disjoint and \Sigma is additionally finite and non-empty. The set \mathcal{T} of string terms is the set of all finite sequences of tokens. Using regular expression notation, we have \mathcal{T}:=\mathcal{K}^{*} and reserve \varepsilon for the empty sequence of tokens. \varepsilon represents the neutral element of concatenation, and we denote concatenation by juxtaposing tokens. The power token u^{m} expresses that the token u is repeated m times; that is, u^{0}=\varepsilon and u^{m}=uu^{m-1} if m>0 where m is some integer term. Given how power terms are introduced, negative values for the exponents can be excluded. We denote by |u| the length with u\in\mathcal{T} ; clearly, |u| represents a natural number. We write u^{R} to denote the reverse string term of u . For example, (ax(ab)^{m})^{R}=(ba)^{m}x^{R}a . Finally, we note that a symbolic character o is equivalent to a string variable x with |x|=1 . We nonetheless use symbolic characters to have simpler definitions later on. String equations and substitutions. A string equation is u_{1}\simeq u_{2} over string terms u_{1},u_{2}\in\mathcal{T} ; here, we refer to u_{1} as the left-hand-side (LHS) of the equation, whereas u_{2} is the right-hand-side (RHS) of the equation. String equations that only contain string variables and concrete characters are called plain ; string equations that might also contain symbolic characters and powers are called extended . We use 2^{u} to denote the set of consecutive tokens within u . ||u|| denotes the number of tokens in u , where power tokens in u are considered atomic; we call this the symbolic length of u : ||\varepsilon||:=0 and ||tv||:=1+||v|| . For example, in u=(abc)^{m}xb we have 2^{u}=\left\{~\varepsilon,a,b,c,(abc)^{m},x,ab,bc,(abc)^{m}x,xb,abc,(abc)^{m}xb~\right\} and ||u||=3 . String terms u\in\mathcal{T} containing no string variables are called ground . For ground terms u we thus have 2^{u}\cap\mathcal{V}_{S}=\emptyset . Nonetheless, ground terms might contain power and symbolic character tokens. A substitution \sigma maps (i) string variables x\in\mathcal{V}_{S} to string terms u\in\mathcal{T} ; and (ii) symbolic characters o\in\mathcal{V}_{C} to characters @\in\Sigma\cup\mathcal{V}_{C} . The set of variables \left\{x\in\mathcal{V}_{S}\mid\sigma(x)\neq x\right\} is finite. Similarly, for symbolic characters. We write (x/u)\in\sigma to denote \sigma(x)=u . A substitution \sigma is eliminating a string variable x if (x/u)\in\sigma and u is ground. The application of a substitution \sigma to an expression C is denoted by C[\sigma] , where C is a string term or a (set of) string/integer (in)equations. Substitutions \sigma are assumed to be acyclic and fully extended: For any non-identity (x/u)\in\sigma and y\in 2^{u} we have (y/y)\in\sigma . We write m_{1}\simeq m_{2} and m_{1}\leq m_{2} for integer (in)equations over integer terms m_{1},m_{2} . Interpretations and models. Given a string equation u\simeq v , an interpretation \mathcal{M} of this equation is a substitution together with an assignment of integer variables to integer values. For every x\in\mathcal{V}_{S}\cap(2^{u}\cup 2^{v}) we have (x/w)\in\mathcal{M} , where w\in\Sigma^{*} ; further, for every o\in\mathcal{V}_{C}\cap(2^{u}\cup 2^{v}) we have (o/a)\in\sigma with a\in\Sigma . An interpretation \mathcal{M} is called a plain model of a set S of plain string equations if the application of \mathcal{M} to S results in a simplified set of equations of the form u\simeq u with u\in\Sigma^{*} . If S has a model \mathcal{M} , then S is satisfiable ; otherwise S is unsatisfiable . Similarly, an extended model of a set of extended string equations and integer (in)equalities simplifies every extended string equation to u\simeq u with u\in\mathcal{T}^{*} and satisfies all integer constraints. All string variables and symbolic characters in u are implicitly