Skip to Main content Skip to Navigation
Conference papers

Equations over Sets of Natural Numbers with Addition Only

Abstract : Systems of equations of the form X = Y Z and X = C are considered, in which the unknowns are sets of natural numbers, “+” denotes pairwise sum of sets S+T = {m + n | m 2 S, n 2 T}, and C is an ultimately periodic constant. It is shown that such systems are computationally universal, in the sense that for every recursive (r.e., co-r.e.) set S N there exists a system with a unique (least, greatest) solution containing a component T with S = {n | 16n+13 2 T}. This implies undecidability of basic properties of these equations. All results also apply to language equations over a one-letter alphabet with concatenation and regular constants.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00360196
Contributor : Publications Loria <>
Submitted on : Tuesday, February 10, 2009 - 4:06:10 PM
Last modification on : Saturday, November 21, 2020 - 9:54:03 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 8:37:50 PM

File

48-jez.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00360196, version 1

Collections

Citation

Artur Jez, Alexander Okhotin. Equations over Sets of Natural Numbers with Addition Only. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.577-588. ⟨inria-00360196⟩

Share

Metrics

Record views

363

Files downloads

263