TY - GEN

T1 - Equations over sets of natural numbers with addition only

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2009/12/1

Y1 - 2009/12/1

N2 - Systems of equations of the form X = YZ and X = C are considered, in which the unknowns are sets of natural numbers, "+" denotes pairwise sum of sets S + T = {m + n | m ∈ S, n ∈ 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.) setS⊆ ℕ there exists a system with a unique (least, greatest) solution containing a component T with S = {n | 16n + 13 ∈ 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.

AB - Systems of equations of the form X = YZ and X = C are considered, in which the unknowns are sets of natural numbers, "+" denotes pairwise sum of sets S + T = {m + n | m ∈ S, n ∈ 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.) setS⊆ ℕ there exists a system with a unique (least, greatest) solution containing a component T with S = {n | 16n + 13 ∈ 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.

UR - http://www.scopus.com/inward/record.url?scp=84880236433&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84880236433

SN - 9783939897095

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 577

EP - 588

BT - STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science

T2 - 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009

Y2 - 26 February 2009 through 28 February 2009

ER -