A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems

Details A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems

2009-07-03

arxiv.org/abs/0907.0620v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over $\{0,1\}$ without two consecutive 1. Given a set $X$ of integers such that the language of their greedy representations in this system is accepted by a finite automaton, we consider the problem of deciding whether or not $X$ is a finite union of arithmetic progressions. We obtain a decision procedure for this problem, under some hypothesis about the considered numeration system. In a second part, we obtain an analogous decision result for a particular class of abstract numeration systems built on an infinite regular language.

Affiliated with

Also associated with

No associations

Rating

A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems 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 A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-705975