 |
 |
|
|
| HAL : hal-00151512, version 1 |
| arXiv : 0706.0431 |
| Fiche détaillée |  Récupérer au format |
 |
| Versions disponibles : | v1 (04-06-2007) | v2 (16-09-2008) |
|
|
|
|
| Abstract numeration systems on bounded languages and multiplication by a constant |
|
|
| Emilie Charlier 1Michel Rigo 1 |
|
|
| (04/06/2007) |
|
|
|
| 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. |
|
|
|
|
|
|
|
|
|
|
|
| 1 : | Département de Mathématique |
|
|
|
Université de Liège |
|
|
| 2 : | Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) |
|
|
|
CNRS : UMR7089 – Université Paris VII - Paris Diderot |
|
|
|
|
|
|
|
|
|
| Domaine | : | Informatique/Mathématique discrète Mathématiques/Combinatoire |
|
|
| Liste des fichiers attachés à ce document : | ||||||||||
|
||||||||||
|
|
|
| hal-00151512, version 1 | |
| http://hal.archives-ouvertes.fr/hal-00151512 | |
| oai:hal.archives-ouvertes.fr:hal-00151512 | |
| Contributeur : Wolfgang Steiner | |
| Soumis le : Lundi 4 Juin 2007, 15:11:12 | |
| Dernière modification le : Lundi 4 Juin 2007, 15:12:50 | |
