Towards a characterization of the star-free sets of integers
| dc.creator | Rigo, Michel | |
| dc.date | 2001-11-23 | |
| dc.date.accessioned | 2026-07-07T03:17:59Z | |
| dc.date.available | 2026-07-07T03:17:59Z | |
| dc.description | Let U be a numeration system, a set X of integers is U-star-free if the set made up of the U-representations of the elements in X is a star-free regular language. Answering a question of A. de Luca and A. Restivo, we obtain a complete logical characterization of the U-star-free sets of integers for suitable numeration systems related to a Pisot number and in particular for integer base systems. For these latter systems, we study as well the problem of the base dependence. Finally, the case of k-adic systems is also investigated. | |
| dc.description | 15 pages, 4 figures | |
| dc.identifier | https://arxiv.org/abs/cs/0111057 | |
| dc.identifier | http://arxiv.org/abs/cs/0111057 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30932 | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.subject | F.1.1;F.4.1;F.4.3 | |
| dc.title | Towards a characterization of the star-free sets of integers | |
| dc.type | text |