Document Open Access Logo

Equations over Sets of Natural Numbers with Addition Only

Authors Artur Jez, Alexander Okhotin

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2009.1806.pdf
  • Filesize: 193 kB
  • 12 pages

Document Identifiers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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.

Cite As Get BibTex

Artur Jez and Alexander Okhotin. Equations over Sets of Natural Numbers with Addition Only. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 577-588, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.STACS.2009.1806

Author Details

Artur Jez
Alexander Okhotin
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact