Finite orbits of language operations

in Lecture Notes in Computer Science (2011), 6638

We consider a set of natural operations on languages, and prove that the orbit of any language L under the monoid generated by this set is finite and bounded, independently of L. This generalizes previous ... [more ▼]

We consider a set of natural operations on languages, and prove that the orbit of any language L under the monoid generated by this set is finite and bounded, independently of L. This generalizes previous results about complement, Kleene closure, and positive closure. [less ▲]

S-automatic sets

Scientific conference (2010, December)

In this talk, I will discuss some new properties of S-automatic sets. First I will show that a multidimensional set is S-automatic for all abstract numeration systems S if and only if it is 1-automatic ... [more ▼]

In this talk, I will discuss some new properties of S-automatic sets. First I will show that a multidimensional set is S-automatic for all abstract numeration systems S if and only if it is 1-automatic. This result is surprising in the following sense: the class of multidimensional 1-automatic sets is a strict subclass of that of semi-linear sets. Hence, this result is not a generalization of the well-known result in integer base numeration systems: a multidimensional set is b-automatic for all integer bases b ≥ 1 if and only if it is semi-linear. Second I will describe the possible behaviors of the nth -term of an S-automatic set, depending on the growth function (i.e., the number of words of length n) of the numeration language. [less ▲]

State complexity of testing divisibility

in McQuillan, Ian, Pighizzini, Giovanni (Ed.) Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (2010, August)

Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an ... [more ▼]

Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2. [less ▲]

Representing real numbers in a generalized numeration system

Conference (2010, June)

We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers ... [more ▼]

We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers using the Dyck language. We also show that our framework can be applied to the rational base numeration systems. [less ▲]

Multidimensional generalized automatic sequences and shape-symmetric morphic words

in Discrete Mathematics (2010), 310

An infinite word is S-automatic if, for all n>=0, its (n+1)st letter is the output of a deterministic automaton fed with the representation of n in the numeration system S. In this paper, we consider an ... [more ▼]

An infinite word is S-automatic if, for all n>=0, its (n+1)st letter is the output of a deterministic automaton fed with the representation of n in the numeration system S. In this paper, we consider an analogous definition in a multidimensional setting and study its relation to the shapesymmetric infinite words introduced by Arnaud Maes. More precisely, for d>1, we show that a multidimensional infinite word x over a finite alphabet is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word. [less ▲]

A characterization of multidimensional S-automatic sequences

in Actes des rencontres du CIRM, 1 (2009)

An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended ... [more ▼]

An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for d ≥ 2, we state that a multidimensional infinite word x : N^d → \Sigma over a finite alphabet \Sigma is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word. [less ▲]

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

in International Journal of Algebra & Computation (2009), 19

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 ... [more ▼]

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. [less ▲]

A decision problem for ultimately periodic sets in non-standard numeration systems

Conference (2008, May)

We consider the following decidability problem: Given a linear numeration system U and a set X ⊆ N such that rep_U(X) is recognized by a (deterministic) finite automaton. Is it decidable whether or not X ... [more ▼]

We consider the following decidability problem: Given a linear numeration system U and a set X ⊆ N such that rep_U(X) is recognized by a (deterministic) finite automaton. Is it decidable whether or not X is ultimately periodic, i.e., whether or not X is a finite union of arithmetic progressions? In this work, we give a decision procedure for this problem whenever U is a linear numeration system such that N is U -recognizable and satisfying a relation of the form U_{i+k} = a_1 U_{i+k−1} + · · · + a_k U_i with a_k = ±1 (the main reason for this assumption is that 1 and −1 are the only two integers invertible modulo n for all n ≥ 2). [less ▲]

Abstract numeration systems on bounded languages and multiplication by a constant

in INTEGERS: Electronic Journal of Combinatorial Number Theory (2008), 8(1-A35), 1-19

A set of integers is $S$-recognizable in an abstract numeration system $S$ if the language made up of the representations of its elements is accepted by a finite automaton. For abstract numeration systems ... [more ▼]

A set of integers is $S$-recognizable in an abstract numeration system $S$ if the language made up of the representations of its elements is accepted by a finite automaton. For abstract numeration systems built over bounded languages with at least three letters, we show that multiplication by an integer $\lambda\ge2$ does not preserve $S$-recognizability, meaning that there always exists a $S$-recognizable set $X$ such that $\lambda X$ is not $S$-recognizable. The main tool is a bijection between the representation of an integer over a bounded language and its decomposition as a sum of binomial coefficients with certain properties, the so-called combinatorial numeration system. [less ▲]

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

in Lecture Notes in Computer Science (2008), 5162

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 ... [more ▼]

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 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. [less ▲]