Geodesic
Decision algorithms for Fibonacci-automatic Words, I: Basic results
Mousavi, Hamoon1 ; Schaeffer, Luke2 ; Shallit, Jeffrey1 
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
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

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 
@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},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     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
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

Cité par Sources :