Strict Language Inequalities and Their Decision Problems

摘要

Systems of language equations of the form { φ(X_1,..., X_n) = Φ, ψ(X_1,..., X_n) ≠ Φ} are studied, where φ, ψ may contain set-theoretic operations and concatenation; they can be equivalently represented as strict inequalities ξ(X_1,...,X_n) is contained in L_0. It is proved that the problem whether such an inequality has a solution is Σ_2-complete, the problem whether it has a unique solution is in (Σ_3 ∩ Π_3) (Σ_2 ∪ Π_2), the existence of a regular solution is a Σ_1-complete problem, while testing whether there are finitely many solutions is Σ_3-complete. The class of languages representable by their unique solutions is exactly the class of recursive sets, though a decision procedure cannot be algorithmically constructed out of an inequality, even if a proof of solution uniqueness is attached.