Complexity of Equations over Sets of Natural Numbers

Результат исследований: Научные публикации в периодических изданияхстатья

22 Цитирования (Scopus)

Аннотация

Systems of equations of the form Xii(X1,...,Xn) (1≤i≤n) are considered, in which the unknowns are sets of natural numbers. Expressions φi may contain the operations of union, intersection and elementwise addition S + T = {m + n {pipe} m ε S, n ε T}. A system with an EXPTIME-complete least solution is constructed in the paper through a complete arithmetization of EXPTIME-completeness. At the same time, 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. Among the consequences of the result is EXPTIME-completeness of the compressed membership problem for conjunctive grammars.

Язык оригиналаанглийский
Страницы (с-по)319-342
Число страниц24
ЖурналTheory of Computing Systems
Том48
Номер выпуска2
DOI
СостояниеОпубликовано - 1 янв 2011

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

  • Теоретические компьютерные науки
  • Математика и теория расчета

Fingerprint Подробные сведения о темах исследования «Complexity of Equations over Sets of Natural Numbers». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать