Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
Systems of equations of the form X = YZ and X = C are considered, in which the unknowns are sets of natural numbers, "+" denotes pairwise sum of sets S + T = {m + n | m ∈ S, n ∈ T}, and C is an ultimately periodic constant. It is shown that such systems are computationally universal, in the sense that for every recursive (r.e., co-r.e.) setS⊆ ℕ there exists a system with a unique (least, greatest) solution containing a component T with S = {n | 16n + 13 ∈ T}. This implies undecidability of basic properties of these equations. All results also apply to language equations over a one-letter alphabet with concatenation and regular constants.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science |
| Страницы | 577-588 |
| Число страниц | 12 |
| Состояние | Опубликовано - 1 дек 2009 |
| Событие | 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 - Freiburg, Германия Продолжительность: 26 фев 2009 → 28 фев 2009 |
| Название | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Том | 3 |
| ISSN (печатное издание) | 1868-8969 |
| конференция | 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 |
|---|---|
| Страна/Tерритория | Германия |
| Город | Freiburg |
| Период | 26/02/09 → 28/02/09 |
ID: 41143669