On equations over sets of integers

Computer Science – Formal Languages and Automata Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

12 apges, 0 figures

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On equations over sets of integers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On equations over sets of integers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On equations over sets of integers will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-659452

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.