TY - GEN

T1 - Strict language inequalities and their decision problems

AU - Okhotin, Alexander

PY - 2005/10/24

Y1 - 2005/10/24

N2 - Systems of language equations of the form {φ(X1, . . . , Xn) = ∅, ψ(X1, . . . , Xn) ≠ ∅} are studied, where φ, ψ may contain set-theoretic operations and concatenation; they can be equivalently represented as strict inequalities ξ(X1, . . . , Xn) ⊂ L0. 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.

AB - Systems of language equations of the form {φ(X1, . . . , Xn) = ∅, ψ(X1, . . . , Xn) ≠ ∅} are studied, where φ, ψ may contain set-theoretic operations and concatenation; they can be equivalently represented as strict inequalities ξ(X1, . . . , Xn) ⊂ L0. 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.

UR - http://www.scopus.com/inward/record.url?scp=26844554961&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:26844554961

VL - 3618

T3 - Lecture Notes in Computer Science

SP - 708

EP - 719

BT - MFCS 2005: Mathematical Foundations of Computer Science 2005

T2 - 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005

Y2 - 29 August 2005 through 2 September 2005

ER -