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] を挙げるべきだろうか。

この 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] がある。

References

[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.

[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.

[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.

[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.