Complexity of infinite words generated by countable q -automata

Marion Le Gonidec[1]

  • [1] IML Campus de Luminy, case 907 13288 Marseille Cedex 09 (France)

Annales de l’institut Fourier (2006)

  • Volume: 56, Issue: 7, page 2463-2491
  • ISSN: 0373-0956

Abstract

top
This article deals with combinatorial properties of infinite words generated by countable and deterministic q -automata of bounded degree. Those words can also be viewed as projections of fixed point of some substitutions of constant length on countable alphabet. We show that complexity function of such words is at most polynomial and, on some examples, the order of growth of this function is at most n ( log n ) p .

How to cite

top

Le Gonidec, Marion. "Sur la complexité de mots infinis engendrés par des $q$-automates dénombrables." Annales de l’institut Fourier 56.7 (2006): 2463-2491. <http://eudml.org/doc/10210>.

@article{LeGonidec2006,
abstract = {On étudie, dans cet article, les propriétés combinatoires de mots engendrés à l’aide de $q$-automates déterministes dénombrables de degré borné, ou de manière équivalente, engendrés par des substitutions de longueur constante uniformément bornées sur un alphabet dénombrable. En particulier, on montre que la complexité de tels mots est au plus polynomiale et que, sur plusieurs exemples, elle est au plus de l’ordre de grandeur de $n (\log n)^p$.},
affiliation = {IML Campus de Luminy, case 907 13288 Marseille Cedex 09 (France)},
author = {Le Gonidec, Marion},
journal = {Annales de l’institut Fourier},
keywords = {Infinite words; complexity; substitutions; automata},
language = {fre},
number = {7},
pages = {2463-2491},
publisher = {Association des Annales de l’institut Fourier},
title = {Sur la complexité de mots infinis engendrés par des $q$-automates dénombrables},
url = {http://eudml.org/doc/10210},
volume = {56},
year = {2006},
}

TY - JOUR
AU - Le Gonidec, Marion
TI - Sur la complexité de mots infinis engendrés par des $q$-automates dénombrables
JO - Annales de l’institut Fourier
PY - 2006
PB - Association des Annales de l’institut Fourier
VL - 56
IS - 7
SP - 2463
EP - 2491
AB - On étudie, dans cet article, les propriétés combinatoires de mots engendrés à l’aide de $q$-automates déterministes dénombrables de degré borné, ou de manière équivalente, engendrés par des substitutions de longueur constante uniformément bornées sur un alphabet dénombrable. En particulier, on montre que la complexité de tels mots est au plus polynomiale et que, sur plusieurs exemples, elle est au plus de l’ordre de grandeur de $n (\log n)^p$.
LA - fre
KW - Infinite words; complexity; substitutions; automata
UR - http://eudml.org/doc/10210
ER -

References

top
  1. J.-P. Allouche, Sur la complexité des suites infinies, Bull. Belg. Math. Soc. Simon Stevin 1 (1994), 133-143 Zbl0803.68094MR1318964
  2. J.-P. Allouche, J. Shallit, Automatic sequences. Theory, applications, generalizations, (2003), Cambridge University Press, Cambridge Zbl1086.11015MR1997038
  3. J. Berstel, D. Perrin, Theory of codes, (1985), Academic Press Zbl0587.68066MR797069
  4. S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math. 24 (1989), 83-96 Zbl0683.20045MR1011264
  5. A. Cobham, Uniform-tag sequences, Math. Syst. Th. 6 (1972), 164-192 Zbl0253.02029MR457011
  6. A. Ehrenfeucht, K. P. Lee, G Rozenberg, Subword complexities of various classes of deterministic developmeltal languages without interactions, Math. Syst. Theoret. Comput. Science 63 (1975),  59-75 Zbl0316.68043MR388861
  7. S. Eilenberg, Automata, languages and machines, A (1974), Academic Press Zbl0317.94045
  8. S. Ferenczi, Substitution dynamical systems on infinite alphabets, (2006) Zbl1147.37007
  9. M. Lothaire, Combinatorics on words, 17 (1983), Cambridge University Press Zbl0874.20040MR675953
  10. M. Lothaire, Algebraic combinatorics on words, 90 (2002), Cambridge University Press Zbl1001.68093MR1905123
  11. C. Mauduit, Propriétés arithmétiques des substitutions et automates infinis, (2006) MR1476736
  12. C. Mauduit, A. Sárközy, On the arithmetic structure of the integers whose sum of digits is fixed, Acta Arithmetica LXXXI (1997),  145-173 Zbl0887.11008MR1456239
  13. B. Mossé, Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France 124 (1996),  329-346 Zbl0855.68072MR1414542
  14. J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, Automata, languages and programming (Antwerp, 1984) 172 (1984),  380-389, Springer, Berlin Zbl0554.68053MR784265
  15. D. Perrin, J.-E. Pin, Mots infinis. Technical report 93.40, (1997), Laboratoire Informatique Théorique et Programmation. Institut Blaise Pascal 
  16. D. Perrin, J.-E. Pin, Infinite words, Automata, Semigroups, Logic and Games, 141 (2004), Elsevier Zbl1094.68052
  17. N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, 1794 (2002), Springer-Verlag, Berlin Zbl1014.11015MR1970385
  18. M. Queffélec, Substitution dynamical systems-spectral analysis, 1294 (1987), Springer-Verlag, Berlin Zbl0642.28013MR924156
  19. G. Rozenberg, A. Salomaa (Eds), Handbook of formal language, (1997), Springer-Verlag Zbl0866.68057

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.