Geodesic
Decision algorithms for Fibonacci-automatic Words, I: Basic results
Mousavi, Hamoon1 ; Schaeffer, Luke2 ; Shallit, Jeffrey1 idref
1School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada
2Computer Science and Artificial Intelligence Laboratory, The Stata Center, MIT Building 32, 32 Vassar Street, Cambridge, MA 02139, USA
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 15th "Journées Montoises d'Informatique Théorique", Tome 50 (2016) no. 1, pp. 39-66

Voir la notice de l'article provenant de la source Numdam

MR Zbl

We implement a decision procedure for answering questions about a class of infinite words that might be called (for lack of a better name) “Fibonacci-automatic”. This class includes, for example, the famous Fibonacci word 𝐟=f 0 f 1 f 2 ···=01001010···, the fixed point of the morphism 0→01 and 1→0. We then recover many results about the Fibonacci word from the literature (and improve some of them), such as assertions about the occurrences in 𝐟 of squares, cubes, palindromes, and so forth.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016010
Classification : 11B85, 68R15, 11A67, 11B39, 03D05, 68Q45
Keywords: Decision procedure, infinite word, Fibonacci-automatic – square, cube, palindrome, first-order logic, Fibonacci representation – quasiperiod, unbordered word, Lyndon word, uniform recurrence – linear recurrence, critical exponent

Mousavi, Hamoon  1   ; Schaeffer, Luke  2   ; Shallit, Jeffrey  1

1 School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada
2 Computer Science and Artificial Intelligence Laboratory, The Stata Center, MIT Building 32, 32 Vassar Street, Cambridge, MA 02139, USA 
Mousavi, Hamoon; Schaeffer, Luke; Shallit, Jeffrey. Decision algorithms for Fibonacci-automatic Words, I: Basic results. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 15th "Journées Montoises d'Informatique Théorique", Tome 50 (2016) no. 1, pp. 39-66. doi: 10.1051/ita/2016010
@article{ITA_2016__50_1_39_0,
     author = {Mousavi, Hamoon and Schaeffer, Luke and Shallit, Jeffrey},
     title = {Decision algorithms for {Fibonacci-automatic} {Words,} {I:} {Basic} results},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {39--66},
     year = {2016},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     doi = {10.1051/ita/2016010},
     mrnumber = {3518158},
     zbl = {1366.68226},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2016010/}
}
TY  - JOUR
AU  - Mousavi, Hamoon
AU  - Schaeffer, Luke
AU  - Shallit, Jeffrey
TI  - Decision algorithms for Fibonacci-automatic Words, I: Basic results
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 39
EP  - 66
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2016010/
DO  - 10.1051/ita/2016010
LA  - en
ID  - ITA_2016__50_1_39_0
ER  - 
%0 Journal Article
%A Mousavi, Hamoon
%A Schaeffer, Luke
%A Shallit, Jeffrey
%T Decision algorithms for Fibonacci-automatic Words, I: Basic results
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 39-66
%V 50
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2016010/
%R 10.1051/ita/2016010
%G en
%F ITA_2016__50_1_39_0

Cité par Sources :