You are here: TUCS > PUBLICATIONS > Publication Search > On the Computational Completen...
- TUCS Publication Series
- How to Publish in TUCS Series
- Publication Search
- Publication Graph
- Publication Input
- Publication Input Guide
- JuFo Browser
On the Computational Completeness of Equations Over Sets of Natural Numbers
Artur Jez, Alexander Okhotin, On the Computational Completeness of Equations Over Sets of Natural Numbers. TUCS Technical Reports 910, Turku Centre for Computer Science, 2008.
Abstract:
Systems of equations of the form φ<sub><i>j</i></sub>(<i>X</i><sub>1</sub>, …, <i>X</i><sub><i>n</i></sub>)=ψ<sub><i>j</i></sub>(<i>X</i><sub>1</sub>, …, <i>X</i><sub><i>n</i></sub>) with 1 ≤ <i>i</i> ≤ <i>n</i> are considered, in which the unknowns <i>X</i><i><sub>i</sub></i> are sets of natural numbers, while the expressions φ<i><sub>j</sub></i>, ψ<i><sub>j</sub></i> may contain singleton constants and the operations of union (possibly replaced by intersection) and pairwise addition <i>S</i> + <i>T</i> = {<i>m</i>+<i>n</i> | <i>m</i>∈<i>S</i>, <i>n</i>∈<i>T</i>}. It is shown that the family of sets representable by unique (least, greatest) solutions of such systems is exactly the family of recursive (r.e., co-r.e., respectively) sets of numbers. Basic decision problems for these systems are located in the arithmetical hierarchy.
Files:
Full publication in PDF-format
BibTeX entry:
@TECHREPORT{tJeOk08a,
title = {On the Computational Completeness of Equations Over Sets of Natural Numbers},
author = {Jez, Artur and Okhotin, Alexander},
number = {910},
series = {TUCS Technical Reports},
publisher = {Turku Centre for Computer Science},
year = {2008},
keywords = {Language equations, unary languages, computability},
ISBN = {978-952-12-2146-0},
}
Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics