Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | MFCS 2005: Mathematical Foundations of Computer Science 2005 |
| Страницы | 708-719 |
| Число страниц | 12 |
| Том | 3618 |
| Состояние | Опубликовано - 24 окт 2005 |
| Опубликовано для внешнего пользования | Да |
| Событие | 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 - Gdansk, Польша Продолжительность: 29 авг 2005 → 2 сен 2005 |
| Название | Lecture Notes in Computer Science |
|---|---|
| Издатель | Springer |
| ISSN (печатное издание) | 0302-9743 |
| конференция | 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 |
|---|---|
| Страна/Tерритория | Польша |
| Город | Gdansk |
| Период | 29/08/05 → 2/09/05 |
ID: 41141085