Equations over finite sets of words and equivalence problems in automata theory (Q685449)

Equations over the monoid \(FS\) of finite sets of words are studied here. In particular, it is shown that a constant-free equation \(u = v\) has a nontrivial solution in the monoid \(FS\) if and only if the equation has a nontrivial solution in the free monoid of finite words. The Ehrenfeucht conjecture is proved to hold for the (free) monoid of prefix codes: Each system of equations in a finite number of variables is equivalent to a finite subsystem. A restriction of this statement is proved for the monoid of finite multisets (or polynomials) of words. The paper contains also applications to automata theory and a list of open problems.