Word Problem

Word とは alphabet の有限列のことである。 群を生成元と関係式で表わしたとき, 生成元を alphabet として, 群の元はその word で表わされる。問題は, 二つの word が同じかどうかをどうやって判定するかである。

この word problem に関連が深い群の class として, automatic group がある。 この automatic という言葉は, オートマトン (automaton) から来ている。

• automatic group
• biautomatic group

Holt の [Hol98] によると, Cannon の仕事 [Can84] に基づき, Thurston により1986年に導入されたようである。 文献としては, Epstein らの [Eps+92] を挙げるべきだろうか。 歴史的視点からの解説として Sarah Rees の [Ree] もある。

この MathOverflow の質問で知ったのであるが, Thurston は, 群を調べるのに UNIX の utility grep が使えることに気がつき, それが automatic group の理論に発展したようである。Notices of the A.M.S. の記事 [GS16] の Mosher の文にある。

Turaev [Tur07c; Tur08] は, 群とは限らない集合の元を alphabet とする word について, トポロジーからのアイデアにより調べることを提唱していて興味深い。Move や linking や polynomial invariant など, 結び目を研究するための概念を word に導入している。 Cobordism や surgery などの言葉も登場する。Turaev は word については [Tur07a] という研究もしている。

解説としては, Turaev 自身による [Tur07b] がある。

群以外の代数的構造に対しても, word problem は考えられている。 例えば, Delpeuch は [Del20] で double category の場合, Vicary との共著 [DV] で braided monoidal category について考えている。

組み合せ論の視点からも色々調べられている。 Fici と Puzynina の [FP] では, 次のような文献が挙げられている: [AS03], [BR10], [CK97], [Lot97], [Lot02], [Lot05], [Fog02], [Rig14]

References

[AS03]

Jean-Paul Allouche and Jeffrey Shallit. Automatic sequences. Theory, applications, generalizations. Cambridge University Press, Cambridge, 2003, pp. xvi+571. isbn: 0-521-82332-3. url: https://doi.org/10.1017/CBO9780511546563.

[BR10]

Valérie Berthé and Michel Rigo, eds. Combinatorics, automata and number theory. Vol. 135. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2010, pp. xx+615. isbn: 978-0-521-51597-9. url: https://doi.org/10.1017/CBO9780511777653.

[Can84]

James W. Cannon. “The combinatorial structure of cocompact discrete hyperbolic groups”. In: Geom. Dedicata 16.2 (1984), pp. 123–148. url: https://doi.org/10.1007/BF00146825.

[CK97]

Christian Choffrut and Juhani Karhumäki. “Combinatorics of words”. In: Handbook of formal languages, Vol. 1. Springer, Berlin, 1997, pp. 329–438.

[Del20]

Antonin Delpeuch. “The word problem for double categories”. In: Theory Appl. Categ. 35 (2020), Paper No. 1, 1–18. arXiv: 1907.09927.

[DV]

Antonin Delpeuch and Jamie Vicary. The word problem for braided monoidal categories is unknot-hard. arXiv: 2105.04237.

[Eps+92]

David B. A. Epstein et al. Word processing in groups. Boston, MA: Jones and Bartlett Publishers, 1992, pp. xii+330. isbn: 0-86720-244-0.

[Fog02]

N. Pytheas Fogg. Substitutions in dynamics, arithmetics and combinatorics. Vol. 1794. Lecture Notes in Mathematics. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. Springer-Verlag, Berlin, 2002, pp. xviii+402. isbn: 3-540-44141-7. url: https://doi.org/10.1007/b13861.

[FP]

Gabriele Fici and Svetlana Puzynina. Abelian Combinatorics on Words: a Survey. arXiv: 2207.09937.

[GS16]

“William P. Thurston, 1946–2012”. In: Notices Amer. Math. Soc. 63.1 (2016). Ed. by David Gabai and coordinating editors Steve Kerckhoff, pp. 31–41. url: https://doi.org/10.1090/noti1324.

[Hol98]

Derek F. Holt. “Automatic groups, subgroups and cosets”. In: The Epstein birthday schrift. Vol. 1. Geom. Topol. Monogr. Geom. Topol. Publ., Coventry, 1998, pp. 249–260. arXiv: math/9810190. url: https://doi.org/10.2140/gtm.1998.1.249.

[Lot02]

M. Lothaire. Algebraic combinatorics on words. Vol. 90. Encyclopedia of Mathematics and its Applications. A collective work by Jean Berstel, Dominique Perrin, Patrice Seebold, Julien Cassaigne, Aldo De Luca, Steffano Varricchio, Alain Lascoux, Bernard Leclerc, Jean-Yves Thibon, Veronique Bruyere, Christiane Frougny, Filippo Mignosi, Antonio Restivo, Christophe Reutenauer, Dominique Foata, Guo-Niu Han, Jacques Desarmenien, Volker Diekert, Tero Harju, Juhani Karhumaki and Wojciech Plandowski, With a preface by Berstel and Perrin. Cambridge University Press, Cambridge, 2002, pp. xiv+504. isbn: 0-521-81220-8. url: https://doi.org/10.1017/CBO9781107326019.

[Lot05]

M. Lothaire. Applied combinatorics on words. Vol. 105. Encyclopedia of Mathematics and its Applications. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé, With a preface by Berstel and Perrin. Cambridge University Press, Cambridge, 2005, pp. xvi+610. isbn: 978-0-521-84802-2; 0-521-84802-4. url: https://doi.org/10.1017/CBO9781107341005.

[Lot97]

M. Lothaire. Combinatorics on words. Cambridge Mathematical Library. With a foreword by Roger Lyndon and a preface by Dominique Perrin, Corrected reprint of the 1983 original, with a new preface by Perrin. Cambridge University Press, Cambridge, 1997, pp. xviii+238. isbn: 0-521-59924-5. url: https://doi.org/10.1017/CBO9780511566097.

[Ree]

Sarah Rees. The development of the theory of automatic groups. arXiv: 2205.14911.

[Rig14]

Michel Rigo. Formal languages, automata and numeration systems. 1. Introduction to combinatorics on words, With a foreword by Valérie Bethé. ISTE, London; John Wiley & Sons, Inc., Hoboken, NJ, 2014, pp. xx+301. isbn: 978-1-84821-615-0.

[Tur07a]

Vladimir Turaev. “Coalgebras of words and phrases”. In: J. Algebra 314.1 (2007), pp. 303–323. arXiv: math/0408258. url: http://dx.doi.org/10.1016/j.jalgebra.2007.02.029.

[Tur07b]

Vladimir Turaev. “Lectures on topology of words”. In: Jpn. J. Math. 2.1 (2007), pp. 1–39. arXiv: math/0609516. url: http://dx.doi.org/10.1007/s11537-007-0634-2.

[Tur07c]

Vladimir Turaev. “Topology of words”. In: Proc. Lond. Math. Soc. (3) 95.2 (2007), pp. 360–412. arXiv: math/0503683. url: http://dx.doi.org/10.1112/plms/pdm014.

[Tur08]

Vladimir Turaev. “Cobordisms of words”. In: Commun. Contemp. Math. 10.suppl. 1 (2008), pp. 927–972. arXiv: math/0511513. url: http://dx.doi.org/10.1142/S0219199708003101.