Box-Ball Systems and Robinson-Schensted-Knuth Correspondence
Kaori Fukuda
DOI: 10.1023/B:JACO.0000022567.30060.3a
Abstract
We study a box-ball system from the viewpoint of combinatorics of words and tableaux. Each state of the box-ball system can be transformed into a pair of tableaux ( P, Q) by the Robinson-Schensted-Knuth correspondence. In the language of tableaux, the P-symbol gives rise to a conserved quantity of the box-ball system, and the Q-symbol evolves independently of the P-symbol. The time evolution of the Q-symbol is described explicitly in terms of the box-labels.
Pages: 67–89
Keywords: box-ball system; Robinson-Schensted-knuth correspondence; soliton cellular automaton; Young tableau; knuth equivalence
Full Text: PDF
References
1. K. Fukuda, M. Okado, and Y. Yamada, “Energy functions in box ball systems,” Internat. J. Modern Phys. A 15(9) (2000), 1379-1392.
2. W. Fulton, Young Tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, 1997.
3. G. Hatayama, A. Kuniba, and T. Takagi, “Soliton cellular automata associated with finite crystals,” Nulclear Phys. B 577 (2000), 619-645.
4. D.E. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, Addison-Wesley Series in Computer Science and Information Processing. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973.
5. I.G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edn., Oxford University Press, 1995.
6. D. Takahashi, “On some soliton systems defined by using boxes and balls,” in Proceedings of the International Symposium on Nonlinear Theory and Its Applications (NOLTA '93), 1993, pp. 555-558.
7. D. Takahashi and J. Matsukidaira, “Box and ball system with a carrier and ultradiscrete modified KdV equation,” J. Phys. A 30 (1997), L733-L739.
8. D. Takahashi and J. Satsuma, “A soliton cellular automaton,” J. Phys. Soc. Jpn. 59 (1990), 3514-3519.
9. T. Tokihiro, A. Nagai, and J. Satsuma, “Proof of solitonical nature of box and ball systems by means of inverse ultra-discretization,” Inverse Problems 15(6) (1999), 1639-1662.
10. M. Torii, D. Takahashi, and J. Satsuma, “Combinatorial representation of invariants of a soliton cellular automaton,” Physica D 92 (1996), 209-220.
2. W. Fulton, Young Tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, 1997.
3. G. Hatayama, A. Kuniba, and T. Takagi, “Soliton cellular automata associated with finite crystals,” Nulclear Phys. B 577 (2000), 619-645.
4. D.E. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, Addison-Wesley Series in Computer Science and Information Processing. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973.
5. I.G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edn., Oxford University Press, 1995.
6. D. Takahashi, “On some soliton systems defined by using boxes and balls,” in Proceedings of the International Symposium on Nonlinear Theory and Its Applications (NOLTA '93), 1993, pp. 555-558.
7. D. Takahashi and J. Matsukidaira, “Box and ball system with a carrier and ultradiscrete modified KdV equation,” J. Phys. A 30 (1997), L733-L739.
8. D. Takahashi and J. Satsuma, “A soliton cellular automaton,” J. Phys. Soc. Jpn. 59 (1990), 3514-3519.
9. T. Tokihiro, A. Nagai, and J. Satsuma, “Proof of solitonical nature of box and ball systems by means of inverse ultra-discretization,” Inverse Problems 15(6) (1999), 1639-1662.
10. M. Torii, D. Takahashi, and J. Satsuma, “Combinatorial representation of invariants of a soliton cellular automaton,” Physica D 92 (1996), 209-220.