• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On Equations Over Sets of Integers

Artur Jez, Alexander Okhotin, On Equations Over Sets of Integers. TUCS Technical Reports 954, Turku Centre for Computer Science, 2010.

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, defined as $S+T=\{m+n \mid 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=\{m-n \mid 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.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tJeOk09a,
  title = {On Equations Over Sets of Integers},
  author = {Jez, Artur and Okhotin, Alexander},
  number = {954},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2010},
  keywords = {Language equations, computability, arithmetical hierarchy, hyper-arithmetical hierarchy},
  ISBN = {978-952-12-2331-0},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication