You are here: TUCS > PUBLICATIONS > Publication Search > Equations Over Sets of Natural...
- TUCS Publication Series
- How to Publish in TUCS Series
- Publication Search
- Publication Graph
- Publication Input
- Publication Input Guide
- JuFo Browser
Equations Over Sets of Natural Numbers with Addition Only
Artur Jez, Alexander Okhotin, Equations Over Sets of Natural Numbers with Addition Only. TUCS Technical Reports 914, Turku Centre for Computer Science, 2008.
Abstract:
Systems of equations of the form
<i>X</i> <sub>1</sub> + ... + <i>X</i> <sub><i>k</i></sub> + <i>C</i>
=
<i>Y</i> <sub>1</sub> + ... + <i>Y</i> <sub><i>l</i></sub> + <i>D</i>
are considered,
in which the unknowns are sets of natural numbers,
“+” denotes
pairwise sum of sets <i>S</i> + <i>T</i> =
{<i>m</i>+<i>n</i> | <i>m</i>∈<i>S</i>, <i>n</i>∈<i>T</i>},
and each equation has <i>k</i>, <i>l</i> ≥ 0,
and contains ultimately periodic constants <i>C</i>, <i>D</i> ⊆ <b>N</b>.
It is shown that such systems are computationally universal,
in the sense that for every recursive (r.e., co-r.e.) set <i>S</i> ⊆ <b>N</b>
there exists a system with a unique (least, greatest) solution
containing a component <i>T</i> with <i>S</i> = {<i>n</i> | 16<i>n</i>+13∈<i>T</i>}.
This implies undecidability
of basic properties of these equations.
All results also apply
to language equations over a one-letter alphabet
with concatenation only.
Files:
Abstract in PDF-formatBibTeX entry:
@TECHREPORT{tJeOk08c,
title = {Equations Over Sets of Natural Numbers with Addition Only},
author = {Jez, Artur and Okhotin, Alexander},
number = {914},
series = {TUCS Technical Reports},
publisher = {Turku Centre for Computer Science},
year = {2008},
keywords = {Language equations, unary languages, universality},
ISBN = {978-952-12-2150-7},
}
Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics