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...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.