On equations over sets of integers

Abstract : Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition $S+T=\makeset{m+n}{m \in S, \: n \in T}$ and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction $S \dotminus T=\makeset{m-n}{m \in S, \: n \in T, \: m \geqslant n}$. Testing whether a given system has a solution is $\Sigma^1_1$-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.477-488, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00457025
Contributeur : Publications Loria <>
Soumis le : mardi 16 février 2010 - 14:14:43
Dernière modification le : mardi 16 février 2010 - 15:40:29
Document(s) archivé(s) le : vendredi 18 juin 2010 - 21:05:03

Fichier

JezArtur.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00457025, version 1

Collections

Citation

Artur Jez, Alexander Okhotin. On equations over sets of integers. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.477-488, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00457025〉

Partager

Métriques

Consultations de la notice

169

Téléchargements de fichiers

101