Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Systems of equations over sets of natural numbers (or, equivalently, language equations over a one-letter alphabet) of the form Xi = φi(X1,...,Xn) (1 ≤ i ≤ n) are considered. Expressions φi may contain the operations of union, intersection and pairwise sum A+B = {x+y | x ∈ A, y ∈ B}. A system with an EXPTIME-complete least solution is constructed, and it is established that least solutions of all such systems are in EXPTIME. The general membership problem for these equations is proved to be EXPTIME-complete.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 |
| Издатель | IBFI Schloss Dagstuhl |
| Страницы | 373-384 |
| Число страниц | 12 |
| ISBN (печатное издание) | 9783939897064 |
| Состояние | Опубликовано - 2008 |
| Опубликовано для внешнего пользования | Да |
| Событие | 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 - Bordeaux, Франция Продолжительность: 21 фев 2008 → 23 фев 2008 |
| Название | Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 |
|---|
| конференция | 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 |
|---|---|
| Страна/Tерритория | Франция |
| Город | Bordeaux |
| Период | 21/02/08 → 23/02/08 |
ID: 78926693