Language equations with complementation: Decision problems
Systems of language equations of the form X-i = phi(i)(X-1 , . . . , X-n) (1 <= i <= n) are studied. Here every phi(i) may contain the operations of concatenation and complementation. The properties of having solutions and of having a unique solution are given mathematical characterizations. As decision problems, the former is NP-complete, while the latter is PSPACE-hard and is in co-RE, and its decidability remains, in general, open. Uniqueness becomes decidable in the case of a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete. (C) 2007 Elsevier B.V. All rights reserved.
language equations complementation decision problems negation computational complexity