PARAMETRIZABILITY BY REGULAR EXPRESSIONS FOR EQUATIONS ON WORDS
Lidia Badura, Marek Zaionc · 2007
By well known Makanin’s result it is decidable whether or not an equation on free monoid has solution. In case of infinitely many solutions for constant-free equations the structure of the set of solutions can be described by the proces of parametrization introduced by Khmielewski. It is proved in [4] by Khmielewski that solutions of any up to three unknowns constant-free equations are parameterizable but some equations with four unknowns are not. We propose another way of parametrization of solutions based on regular expressions in which it is possible to express nested substitutions like for example x ! (x y) not expressible by standard Khmielewski’s parametrization. For example it is proved that the class of quadratic equations is parameterizable by regular expression description while it is not parameterizable by the standard one.