2026-07-22T16:58:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1806 2024-03-06T10:33:13Z ddc:004 open_access

Equations over Sets of Natural Numbers with Addition Only Jez, Artur Okhotin, Alexander 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=\ensuremath{ \{ m+n \: | \: m \in S, \; n \in 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 \subseteq \mathbb{N}$ there exists a system with a unique (least, greatest) solution containing a component $T$ with $S=\ensuremath{ \{ n \: | \: 16n+13 \in 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Artur Jez and Alexander Okhotin 2009 Is Part Of LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2009.1806 urn:nbn:de:0030-drops-18061 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1806 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode