Complexity of Equations over Sets of Natural Numbers

Artur Jez; Alexander Okhotin

doi:10.1007/s00224-009-9246-y

Complexity of Equations over Sets of Natural Numbers

Artur Jez, Alexander Okhotin

Research output

22 Citations (Scopus)

Abstract

Systems of equations of the form X_i=φ_i(X₁,...,X_n) (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.

Original language	English
Pages (from-to)	319-342
Number of pages	24
Journal	Theory of Computing Systems
Volume	48
Issue number	2
DOIs	https://doi.org/10.1007/s00224-009-9246-y
Publication status	Published - 1 Jan 2011

Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics

Access to Document

10.1007/s00224-009-9246-y

http://www.scopus.com/inward/record.url?scp=80051665679&partnerID=8YFLogxK

Fingerprint Dive into the research topics of 'Complexity of Equations over Sets of Natural Numbers'. Together they form a unique fingerprint.

Cite this

@article{d01332d96c624a58b36344d76faffcd5,

title = "Complexity of Equations over Sets of Natural Numbers",

abstract = "Systems of equations of the form Xi=φi(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.",

keywords = "Computational complexity, Conjunctive grammars, Integer expressions, Language equations",

author = "Artur Jez and Alexander Okhotin",

year = "2011",

month = jan,

day = "1",

doi = "10.1007/s00224-009-9246-y",

language = "English",

volume = "48",

pages = "319--342",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer Nature",

number = "2",

}

TY - JOUR

T1 - Complexity of Equations over Sets of Natural Numbers

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2011/1/1

Y1 - 2011/1/1

N2 - Systems of equations of the form Xi=φi(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.

AB - Systems of equations of the form Xi=φi(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.

KW - Computational complexity

KW - Conjunctive grammars

KW - Integer expressions

KW - Language equations

UR - http://www.scopus.com/inward/record.url?scp=80051665679&partnerID=8YFLogxK

U2 - 10.1007/s00224-009-9246-y

DO - 10.1007/s00224-009-9246-y

M3 - Article

AN - SCOPUS:80051665679

VL - 48

SP - 319

EP - 342

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 2

ER -