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.
| Original language | English |
|---|---|
| Title of host publication | MFCS 2005: Mathematical Foundations of Computer Science 2005 |
| Pages | 708-719 |
| Number of pages | 12 |
| Volume | 3618 |
| State | Published - 24 Oct 2005 |
| Externally published | Yes |
| Event | 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 - Gdansk, Poland Duration: 29 Aug 2005 → 2 Sep 2005 |
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| ISSN (Print) | 0302-9743 |
| Conference | 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 |
|---|---|
| Country/Territory | Poland |
| City | Gdansk |
| Period | 29/08/05 → 2/09/05 |
ID: 41141085