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.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.577-588, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00360196
Contributeur : Publications Loria <>
Soumis le : mardi 10 février 2009 - 16:06:10
Dernière modification le : mercredi 29 novembre 2017 - 10:27:37
Document(s) archivé(s) le : mardi 8 juin 2010 - 20:37:50

Fichier

48-jez.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00360196, version 1

Collections

Citation

Artur Jez, Alexander Okhotin. Equations over Sets of Natural Numbers with Addition Only. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.577-588, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00360196〉

Partager

Métriques

Consultations de la notice

153

Téléchargements de fichiers

93