Complexity of solutions of equations over sets of natural numbers

Alexander Okhotin & Artur Jez
Systems of equations over sets of natural numbers (or, equivalently, language equations over a one-letter alphabet) of the form $X_i=varphi_i(X_1, ldots, X_n)$ ($1 leqslant i leqslant n$) are considered. Expressions $varphi_i$ may contain the operations of union, intersection and pairwise sum $A plus B = {x + y mid x in A, y in B$. A system with an EXPTIME-complete least solution is constructed, and it is established that least solutions of all such systems...