On the role of complementation in implicit language equations and relations

We solve systems of implicit equations and relations with union and complementation.If the languages are regular, we determine whether the system has solutions.If there is a solution, we provide an effective construction of a regular solution.We give complete representations for maximal and minimal solutions.We determine whether the solution is unique or infinitely many solutions exist.

We solve systems of boolean implicit equations and relations with union and complementation. If the languages are regular, we determine whether a system of implicit boolean equations or relations has solutions. If there is a solution, we provide an effective construction of a (regular) solution. We give representations for maximal and minimal solutions. Moreover, we also solve the problem of uniqueness of solutions as well as whether infinitely many solutions exist.