Structural Properties of bounded Languages with respect to Multiplication by a Constant

Émilie Charlier

Université de Liège, Belgium

Coauthor(s): Michel Rigo, Wolfgang Steiner

Generalizations of positional number systems in which $\mathbb{N}$ is recognizable by finite automata are obtained by describing an arbitrary infinite regular language according to the genealogical ordering. More precisely, an abstract numeration system is a triple $S=(L,\Sigma,<)$ where $L$ is an infinite language over the totally ordered alphabet $(\Sigma, <).$ Enumerating the elements of $L$ genealogically with respect to $<$ leads to a one-to-one map $r_S$ from $\mathbb{N}$ onto $L.$ To any natural number $n,$ it assigns the $(n+1)$th word of $L,$ its S-representation, while the inverse map $val_S$ sends any word belonging to $L$ onto its numerical value. A subset $X$ is said to be S-recognizable if $r_S(X)$ is a regular subset of $L.$ We study the preservation of recognizability of a set of integers after multiplication by a constant for abstract numeration systems built over a bounded language.