You are here: TUCS > PUBLICATIONS > Publication Search > Complexity of Solutions of Equ...
- TUCS Publication Series
- How to Publish in TUCS Series
- Publication Search
- Publication Graph
- Publication Input
- Publication Input Guide
- JuFo Browser
Complexity of Solutions of Equations Over Sets of Numbers
Artur Jez, Alexander Okhotin, Complexity of Solutions of Equations Over Sets of Numbers. TUCS Technical Reports 847, Turku Centre for Computer Science, 2007.
Abstract:
Systems of equations of the form
X<sub><i>i</i></sub>=φ<sub><i>i</i></sub>(X<sub>1</sub>, ..., X<sub><i>n</i></sub>)
(1 ≤ <i>i</i> ≤ <i>n</i>) are considered,
in which the unknowns are sets of natural numbers.
Expressions φ<sub><i>i</i></sub> may contain the operations
of union, intersection and pairwise sum
Y+Z = {<i>y</i>+<i>z</i> | <i>y</i> ∈ Y, <i>z</i> ∈ Z}.
These equations can be regarded
as language equations or conjunctive grammars
over a one-letter alphabet.
A system with an EXPTIME-complete least solution
is constructed in the paper,
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.
Files:
Full publication in PDF-format
BibTeX entry:
@TECHREPORT{tJeOk07b,
title = {Complexity of Solutions of Equations Over Sets of Numbers},
author = {Jez, Artur and Okhotin, Alexander},
number = {847},
series = {TUCS Technical Reports},
publisher = {Turku Centre for Computer Science},
year = {2007},
keywords = {Language equations, integer expressions, conjunctive grammars, computational complexity},
ISBN = {978-952-12-1966-5},
}
Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics