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
Contributor : Publications Loria Connect in order to contact the contributor
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


Files produced by the author(s)


  • HAL Id : inria-00360196, version 1



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⟩



Record views


Files downloads