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 фев 200823 фев 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/0823/02/08

    Предметные области Scopus

  • Компьютерные науки (все)

ID: 78926693