From combinatorial games to shape-symmetric morphisms

[en] Siegel suggests in his book on combinatorial games that quite simple games provide us with challenging problems: ``No general formula is known for computing arbitrary Grundy values of Wythoff's game. In general, they appear chaotic, though they exhibit a striking fractal-like pattern.''. This observation is the first motivation behind this chapter. We present some of the existing connections between combinatorial game theory and combinatorics on words. In particular, multidimensional infinite words can be seen as tiling of $N^d$. They naturally arise from subtraction games on $d$ heaps of tokens. We review notions such as $k$-automatic, $k$-regular or shape-symmetric multidimensional words. The underlying general idea is to associate a finite automaton with a morphism.

Disciplines :

Mathematics

Author, co-author :

Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

From combinatorial games to shape-symmetric morphisms

Publication date :

2020

Main work title :

Tiling Dynamical Systems: Introduction to Self-inducing Structures

Author, co-author :

Akiyama, Shigeki

Arnoux, Pierre

Publisher :

Springer

Collection name :

Lect. Notes in Mathematics 2273

Available on ORBi :

since 30 April 2018

Statistics

Number of views

90 (18 by ULiège)

Number of downloads

136 (12 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

M.H. Albert, R.J. Nowakowski (eds.), Games of no chance 3, in Mathematical Sciences Research Institute Publications, vol. 56 (Cambridge University Press, Cambridge, 2009). Papers from the Combinatorial Game Theory Workshop held in Banff, AB, June 2005
M.H. Albert, R.J. Nowakowski, D. Wolfe, Lessons in Play: An Introduction to Combinatorial Game Theory (A K Peters/CRC Press, 2007)
J.-P. Allouche, V. Berthé, Triangle de Pascal, complexité et automates. Bull. Belg. Math. Soc. Simon Stevin 4(1), 1–23 (1997). Journées Montoises (Mons, 1994)
J.-P. Allouche, F. von Haeseler, H.-O. Peitgen, A. Petersen, G. Skordev, Automaticity of double sequences generated by one-dimensional linear cellular automata. Theoret. Comput. Sci. 188(1–2), 195–209 (1997)
J.-P. Allouche, F. von Haeseler, Peitgen, H.-O., G. Skordev, Linear cellular automata, finite automata and Pascal’s triangle. Discrete Appl. Math. 66(1), 1–22 (1996)
J.-P. Allouche, J. Shallit, The ring of k-regular sequences. Theoret. Comput. Sci. 98(2), 163– 197 (1992)
J.-P. Allouche, J. Shallit, The ubiquitous Prouhet–Thue–Morse sequence, in Sequences and Their Applications (Singapore, 1998). Springer Series of Discrete Mathematics and Theoretical Computer Science (Springer, London, 1999), pp. 1–16
J.-P. Allouche, J. Shallit, Automatic Sequences, Theory, Applications, Generalizations (Cam-bridge University Press, Cambridge, 2003)
J.-P. Allouche, J. Shallit, The ring of k-regular sequences. II. Theoret. Comput. Sci. 307(1), 3–29 (2003)
R.B. Austin, Impartial and Partisan Games. Master’s thesis, Univ. of Calgary (1976)
A. Barbé, F. von Haeseler, Limit sets of automatic sequences. Adv. Math. 175(2), 169–196 (2003)
C. Berge, The Theory of Graphs (Dover Publications, Mineola, 2001)
E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways for Your Mathematical Plays, vol. 1, 2nd edn. (A K Peters, Natick, 2001)
U. Blass, A.S. Fraenkel, The Sprague–Grundy function for Wythoff’s game. Theoret. Comput. Sci. 75(3), 311–333 (1990)
C.L. Bouton, Nim, a game with a complete mathematical theory. Ann. Math. 3, 35–39 (1905)
V. Bruyère, G. Hansel, Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181(1), 17–43 (1997)
V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. Simon Stevin 1(2), 191–238 (1994)
A. Carpi, C. Maggi, On synchronized sequences and their separators. Theor. Inform. Appl. 35(6), 513–524 (2002) (2001). A tribute to Aldo de Luca
O. Carton, W. Thomas, The monadic theory of morphic infinite words and generalizations. Inf. Comput. 176, 51–65 (2002)
J. Cassaigne, E. Duchêne, M. Rigo, Non-homogeneous Beatty sequences leading to invariant games. SIAM J. Discret. Math. 30, 1798–1829 (2016)
J. Cassaigne, F. Nicolas, Factor complexity, in Combinatorics, Automata and Number Theory. Encyclopedia of Mathematics and Its Applications, vol. 135 (Cambridge University Press, Cambridge, 2010), pp. 163–247
É. Charlier, T. Kärki, M. Rigo, Multidimensional generalized automatic sequences and shape-symmetric morphic words. Discret. Math. 310(6–7), 1238–1252 (2010)
É. Charlier, J. Leroy, M. Rigo, Asymptotic properties of free monoid morphisms. Linear Algebra Appl. 500, 119–148 (2016)
É. Charlier, N. Rampersad, J. Shallit, Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comput. Sci. 23(5), 1035–1066 (2012)
É. Charlier, M. Rigo, W. Steiner, Abstract numeration systems on bounded languages and multiplication by a constant. Integers 8, #A35 (2008)
Ch. Choffrut, W. Goldwurm, Rational transductions and complexity of counting problems. Math. Syst. Theory 28(5), 437–450 (1995)
Ch. Choffrut, J. Karhumäki, Combinatorics of words, in Handbook of Formal Languages, vol. 1 (Springer, Berlin, 1997), pp. 329–438
G. Christol, T. Kamae, M. Mendès France, G. Rauzy, Suites algébriques, automates et substitutions. Bull. Soc. Math. France 108(4), 401–419 (1980)
A. Cobham, On the Hartmanis-Stearns problem for a class of tag machines, in IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory (1968), pp. 51–60. Also appeared as IBM Research Technical Report RC-2178, August 23 1968
A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata. Math. Syst. Theory 3, 186–192 (1969)
A. Cobham, Uniform tag sequences. Math. Syst. Theory 6, 164–192 (1972)
A. Dress, A. Flammenkamp, N. Pink, Additive periodicity of the Sprague–Grundy function of certain Nim games. Adv. Appl. Math. 22, 249–270 (1999)
E. Duchêne, A.S. Fraenkel, R.J. Nowakowski, M. Rigo, Extensions and restrictions of Wythoff’s game preserving its P positions. J. Combin. Theory Ser. A 117(5), 545–567 (2010)
E. Duchêne, M. Rigo, Cubic Pisot unit combinatorial games. Monatsh. Math. 155(3–4), 217– 249 (2008)
E. Duchêne, M. Rigo, A morphic approach to combinatorial games: the Tribonacci case. Theor. Inform. Appl. 42(2), 375–393 (2008)
E. Duchêne, M. Rigo, Invariant games. Theor. Comput. Sci. 411(34–36), 3169–3180 (2010)
J.M. Dumont, A. Thomas, Systèmes de numération et fonctions fractales relatifs aux substitutions. Theoret. Comput. Sci. 65 (1989)
F. Durand, Cobham’s theorem for substitutions. J. Eur. Math. Soc. 13(6), 1799–1814 (2011)
S. Eilenberg, Automata, Languages, and Machines, vol. A (Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York, 1974). Pure and Applied Mathematics, vol. 58
N.P. Fogg, in Substitutions in Dynamics, Arithmetics and Combinatorics, ed. by V. Berthé, S. Ferenczi, C. Mauduit A. Siegel. Lecture Notes in Mathematics, vol. 1794 (Springer, Berlin, 2002)
A.S. Fraenkel, The bracket function and complementary sets of integers. Can. J. Math. 21, 6–27 (1969)
A.S. Fraenkel, How to beat your Wythoff games’ opponent on three fronts. Am. Math. Mon. 89(6), 353–361 (1982)
N.P. Fogg, in Substitutions in Dynamics, Arithmetics and Combinatorics, ed. by V. Berthé, S. Ferenczi, C. Mauduit A. Siegel. Lecture Notes in Mathematics, vol. 1794 (Springer, Berlin, 2002)
A.S. Fraenkel, Complexity, appeal and challenges of combinatorial games. Theoret. Comput. Sci. 313(3), 393–415 (2004). Algorithmic combinatorial game theory
A.S. Fraenkel, Euclid and Wythoff games. Discret. Math. 304, 65–68 (2005)
A.S. Fraenkel, Complementary iterated floor words and the Flora game. SIAM J. Discret. Math. 24(2), 570–588 (2010)
Ch. Frougny, On the sequentiality of the successor function. Inf. Comput. 139(1), 17–38 (1997)
S.W. Golomb, A mathematical investigation of games of “take-away”. J. Combin. Theory 1, 443–458 (1966)
R.K. Guy, C.A. Smith, The G-values of various games. Proc. Camb. Philos. Soc. 52, 514–526 (1956)
F. von Haeseler, H.-O. Peitgen, G. Skordev, Self-similar structure of rescaled evolution sets of cellular automata. I. Internat. J. Bifur. Chaos Appl. Sci. Eng. 11(4), 913–926 (2001)
J. Honkala, Bases and ambiguity of number systems. Theoret. Comput. Sci. 31(1–2), 61–71 (1984)
J. Honkala, On unambiguous number systems with a prime power base. Acta Cybernet. 10(3), 155–163 (1992)
J. Honkala, On the simplification of infinite morphic words. Theoret. Comput. Sci. 410(8–10), 997–1000 (2009)
G. Katona, A theorem of finite sets, in Theory of Graphs (Proceedings of the Colloquium Tihany, 1966) (Academic Press, New York, 1968), pp. 187–207
Krebs, T.J.P.: A more reasonable proof of Cobham’s theorem. CoRR abs/1801.06704 (2018). http://arxiv.org/abs/1801.06704
H.A. Landman, More games of no chance, in Chap. A Simple FSM-Based Proof of the Additive Periodicity of the Sprague–Grundy Function of Wythoff ’s Game (Cambridge University Press, Cambridge, 2002)
U. Larsson, P. Hegarty, A.S. Fraenkel, Invariant and dual subtraction games resolving the Duchêne–Rigo conjecture. Theoret. Comput. Sci. 412(8–10), 729–735 (2011)
M.V. Lawson, Finite Automata (Chapman & Hall/CRC, Boca Raton, 2004)
P. Lecomte, M. Rigo, Abstract numeration systems, in Combinatorics, Automata and Number Theory. Encyclopedia of Mathematics and its Applications, vol. 135 (Cambridge University Press, Cambridge, 2010), pp. 108–162
P.B.A. Lecomte, M. Rigo, Numeration systems on a regular language. Theory Comput. Syst. 34(1), 27–44 (2001)
J. Leroy, M. Rigo, M. Stipulanti, Generalized Pascal triangle for binomial coefficients of words. Adv. in Appl. Math. 80, 24–47 (2016)
M. Lothaire, in Combinatorics on Words. Cambridge Mathematical Library (Cambridge University Press, Cambridge, 1997)
M. Lothaire, in Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 90 (Cambridge University Press, Cambridge, 2002)
A. Maes, Morphic predicates and applications to the decidability of arithmetic theories. Ph.D. thesis, UMH Univ. Mons-Hainaut (1999)
V. Marsault, J. Sakarovitch, The signature of rational languages. Theoret. Comput. Sci. 658, 216–234 (2017)
V. Marsault, J. Sakarovitch, Trees and languages with periodic signature. Indag. Math. 28(1), 221–246 (2017)
R.J. Nowakowski (ed.), Games of no chance 4, in Mathematical Sciences Research Institute Publications, vol. 63 (Cambridge University Press, New York, 2015). Selected papers from the Banff International Research Station (BIRS) Workshop on Combinatorial Games held in Banff, AB, 2008
K. O’Bryant, Fraenkel’s partition and brown’s decomposition. Integers 3 (2003)
D. Perrin, Finite automata, in Handbook of Theoretical Computer Science, vol. B (Elsevier, Amsterdam, 1990), pp. 1–57
M. Rigo, Generalization of automatic sequences for numeration systems on a regular language. Theoret. Comput. Sci. 244(1–2), 271–281 (2000)
M. Rigo, Numeration systems: a link between number theory and formal language theory, in Developments in Language Theory. Lecture Notes in Computer Science, vol. 6224 (Springer, Berlin, 2010), pp. 33–53
M. Rigo, Formal Languages, Automata and Numeration Systems 1. (ISTE/ Wiley, London/Hoboken, 2014). Introduction to Combinatorics on Words, With a foreword by Valérie Bethé
M. Rigo, Formal Languages, Automata and Numeration Systems 2. Networks and Telecommunications Series (ISTE/ Wiley, London/Hoboken, 2014). Applications to recognizability and decidability, With a foreword by Valérie Berthé
M. Rigo, Advanced graph theory and combinatorics, in Networks and Telecommunications Series. ISTE, London (Wiley, Hoboken, 2016)
M. Rigo, A. Maes, More on generalized automatic sequences. J. Autom. Lang. Comb. 7(3), 351–376 (2002)
M. Rigo, L. Waxweiler, A note on syndeticity, recognizable sets and Cobham’s theorem. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 88, 169–173 (2006)
E. Rowland, Binomial coefficients, valuations, and words, in Developments in Language Theory. Lecture Notes in Computer Science, vol. 10396 (Springer, Berlin, 2017), pp. 68–74
E. Rowland, R. Yassawi, A characterization of p-automatic sequences as columns of linear cellular automata. Adv. in Appl. Math. 63, 68–89 (2015)
J. Sakarovitch, Elements of Automata Theory (Cambridge University Press, Cambridge, 2009)
P.V. Salimov, On uniform recurrence of a direct product. Discret. Math. Theoret. Comput. Sci. 12, 1–8 (2010)
O. Salon, Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris Sér. I Math. 305(12), 501–504 (1987)
O. Salon, Suites automatiques à multi-indices, in Séminaire de Théorie des Nombres de Bordeaux (1986/1987), pp. 4.01–4.27. Followed by an appendix by J. Shallit
J. Shallit, A Second Course in Formal Languages and Automata Theory (Cambridge University Press, Cambridge, 2008)
J.O. Shallit, A generalization of automatic sequences. Theoret. Comput. Sci. 61, 1–16 (1988)
A.N. Siegel, in Combinatorial Game Theory. Graduate Studies in Mathematics, vol. 146 (American Mathematical Society, Providence, 2013)
T.A. Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science (Addison-Wesley, Reading, 2006)
W.A. Wythoff, A modification of the game of nim. Nieuw Arch. Wiskd. 7, 199–202 (1907)
É. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. Roy. Sci. Liège 41, 179–182 (1972)